CLRS第10章 基本数据结构——栈和队列

·####算法导论的第10章内容—基本数据结构的总结和习题的解答。

10.1 栈和队列

栈和队列都是动态集合，且在其上进行的DELETE操作所移除的元素都是预先设定的。栈上DELETE的元素是最近插入的元素，队列是在集合中存在时间最长的元素。栈是一种后进先出的策略（LIFO），队列是一种先进先出的策略(FIFO)。 栈上的INSERT操作为PUSH，DELETE操作为POP。 队列的INSERT操作为ENQUEUE入队，DELETE操作为DEQUEUE.

以下使用C++用数组实现一个栈

栈的数组实现：数组是顺序结构，所以要在数组中显示栈，需要两个int型的变量来指示栈的位置。

//栈的实现

using namespace std; const int maxn = 100; template<class type> class STACK { public: STACK() :top(-1) {} bool empty() { return top == -1 ? true : false; } ` `void push(type x) { if (top == maxn - 1) { cout << "error,no enough room for it" << endl; return; } else { top++; a[top] = x; } } type pop() { if (top == -1) { cout << "error ,no element to pop\n"; exit(0); } else { type x = a[top]; top--; return x; } } private: type a[maxn]; int top; }; ` ` int main() { STACK<int> x; x.push(3); bool c = x.empty(); cout << c << endl; x.push(4); int d = x.pop(); cout << d << endl; return 0; } ` *队列的实现* ```template<class type> class QUEUE { public: QUEUE():top(-1),tail(-1){}; void ENQUEUE(type x) { if(top=-1) { top++; a[top]=x; return ; } if((top!=tail)&&(fabs(top-tail)<maxn-1) { if(top==maxn-1) top=0; else top++; a[top]=x; } else cout<<"no enough space to store"<<endl; } bool empty() { if(top==tail) return true; else return false; } type DEQUEUE() { type tem; if(top!=tail) { tem=a[tail]; if(tail==maxn-1) tail=0; else tail++; return tem; } else cout<<"empty queue,wrong behavior"<<endl; } private: type a[maxn]; int top; int tail; ``` #### *练习题答案* 10.1-2： 可以以数组两端作为栈底。然后栈中元素往中间走，这样并不会发生上溢，对于元素个数不超过n来说。 `template<class type> class stack { privete: int a[maxn]; int top1; //第一个栈从0开始 int top2; //第二个栈从n开始 public: stack():top1(-1),top2(n+1){}; .... .... .... ` 10.1-4 :见上述queue代码 10.1-5：双端队列的数组实现与上述队列的不同之处在于队尾插入元素，队头删除元素。类的私有变量还是top和tail，前两个方法都不用改变，需要新舔两个方法。 代码如下 <div class="se-preview-section-delimiter"></div> ``` type delete_top() { if(top!=tail) { type tem=a[top]; if(top==0) top=maxn-1; else top--; return tem; } else cout<<"error"<<endl; void insert_tail(type x) { if(tail!=top&&abs(tail-top)<maxn-1) { if(tail!=0) tail--; else tail=maxn-1; a[tail]=x; } else cout<<"wrong"<<endl; } { if(top!=tail) { type tem=a[top]; if(top==0) top=maxn-1; else top--; return tem; } else cout<<"error"<<endl; void insert_tail(type x) { if(tail!=top&&abs(tail-top)<maxn-1) { if(tail!=0) tail--; else tail=maxn-1; a[tail]=x; } else cout<<"wrong"<<endl; }

10.1-6 如何用两个栈实现一个队列？    一个栈当作入队操作，入队时，将元素压入栈1，一直有元素入队，就一直将元素压入栈1，出队时，将元素栈1中的所有元素，顺序出栈，压入栈2，此时，栈2的头顶元素出栈，就是出队。然后在把元素压回栈1. 

10.1-7  如何用两个队列实现一个栈？    对队列q1进行入队操作，此时相当于栈的push。要得到栈的pop元素，需要将队列q1中最后进队列前面的元素消除，将q1除最后一个元素外，进行dequeuer到q2中，然后对q1中的元素进行dequeuer便得到了出栈元素。如果要继续出栈，将q2中的最后一个元素之前的元素，进行dequeue进入q1，然后将q2中的元素dequeuer便得到出栈元素。如此循环进行，便可。 总体上来说，总是会使一个队列为空，然后将另一个非空队列的除最后一个元素外，都压入空队列。