本文主要包含以下内容：
一.栈以及栈的实现
二.队列以及队列的两种实现方式
三.总结
一.栈以及栈的两种实现
1.什么是栈？
入口和出口是同一个，遵循先进后出FILO的原则
2.栈的两种实现
顺序表方式：
template<typename E> class AStack { private: int top; int maxsize; E* alist; public: AStack(int size=defaultsize){ maxsize = size; top = 0; alist = new E(maxsize); } ~AStack() { delete[] alist; } void clear() { top = 0; } const E& topValue() const{ assert(top > 0, "There is no element."); return alist[top - 1]; }; void push(const E&item) { assert(top < maxsize, "数组越界"); alist[top] = item; top++; }; void pop() { assert(top > 0, "There is no element."); top--; }; int length()const { return top; } };链表方式： class node { public: E element; node* next; node(const E&Element,node*Next=NULL){ element = Element; next = Next; } node() { next = NULL; } ~node() { delete next; } }; template<typename E> class lstack { private: node<E>*top; int length; public: lstack() { top = NULL; length = 0; } ~lstack() { node<E>*temp; while (top != NULL) { temp = top; top = top->next; delete temp; } length = 0; } const E&topValue()const { assert(top != NULL, "There is no element."); return top->element; } void push(const E&it) { top = new node<E>(it, top); length++; } void pop() { node<E>* temp = top; if (top != NULL) { top = top->next; delete temp; length--; } } }; 3.说明两种实现方式都是对之前线性表实现的一个简化。
只需想清楚一个问题就可以了：入口和出口是位于表头还是表尾。
对于顺序表实现的栈，因位要方便的push 和pop元素，如果这个口位于表头，每次push pop时都要把数组整体移动，时间为o(n)
如果位于表尾，直接push pop就可以了，时间O(1)，因此位于表尾。
对于链表，如果这个口位于表头，push pop的时间为O(1). 如果位于表尾，push pop的时间为O（n）.因此链表的栈口位于表头。
除此之外，链表不需要一个单独的头指针。
二.队列以及队列的两种实现方式
1.什么是队列？
简单来说，队列有两个口，一个口出，一个口入。遵循先进先出FIFO的原则。
2.实现
省略
3.说明
对于顺序队列，应该处理成一个循环数组。因为，如果不是循环数组，假设从表头入队表尾出队，则入队时间为O(N);
假设从表尾入队表头出队，则出队时间为O（n）。而设为循环数组，一个指针指向表头，一个指针指向表尾即可(size-1视为小与0）。
但是循环数组会遇到新的问题，及不能区分空队列和满队列。假设头指针和尾指针指向同一个元素的时候表示队列中有一个元素，尾指针小与头指针。
如果数组是满的，则尾指针仍然小与头指针。
解决方法：
a.用n+1大小的数组去存放n个元素
b.引入一个bool变量去区分这两种情况
三、总结
顺序队列实现时，遇到了空满队列不能区分的问题。
上述的解决思想很重要。 ’
