---

用C++实现的栈和队列，在实际的编程应用中经常被使用，事实上队列和栈本身作为重要的数据结构，在程序设计中使用频繁。在朋友们，尤其是应届生朋友们面试过程中，面官让你写一个栈和队列的C++实现也不算什么让人觉得奇怪的事，因为这既考查了C++的面向对象知识，又考查了数据结构中的堆栈知识。

 

下面就来看看如何用C++实现栈和队列：

 

//栈的定义声明

template <class T>

class Stack

{

public:

     Stack();

     ~Stack();

     void Push(T data);

     T Pop();

protected:

     typedef struct elementT

{

         struct elementT *next;

         T data;

     } element;

     element *firstE1;

};

template <class T>

//入栈函数

void Stack<T>::Push(T data)

{

     element *element = new element;

     element->data = data;

     element->next = firstE1;

     firstE1 = element;

     return;

}

//出栈函数

T Stack<T>::Pop()

{

     element *popElement = firstE1;

     T data;

     //需要考虑栈为空的情况

     if (firstE1 == NULL)

         return NULL;

     data = firstE1->data;

     firstE1 = firstE1->next;

     delete popElement;

     return data;

}

//队列的定义声明

template <class T>

class Queue:

{

public:

     Queue();

     ~Queue();

     void Enqueue(T data);

     T Dequeue();

protected:

     typedef struct elementT

     {

         struct elementT *next;

         T data;

     } element;

     element *front;

     element *rear;

}

template <class T>

//入队操作

void Queue<T>::Enqueue(T data)

{

     //入队需要考虑队列为空情况

     if(rear==NULL)

     {

         element * elm = malloc(sizeof (element));

         elm->data = data;

         elm->next = NULL;

         front = rear = elm;

     }

     //队列非空

     else

     {

         element * elm = malloc(sizeof (element));

         elm->data =data;

         elm->next = NULL;

         rear->next = elm;

         rear = elm;

     }

     return;

 }

//出队操作

T Queue<T>::Dequeue()

{

     element  *elm;

     T        data;

     //出队需要考虑队列空的情况

     if (front ==NULL && rear == NULL)

         return NULL;

     element *elm = front;

     front = front->next;

     data = elm->data;

     free(elm);

     return data;

 }