下载文档原格式
数据结构第三章数据结构堆栈和队列在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和操作这些数据。
在数据结构的众多类型中，堆栈和队列是两种非常重要且常用的结构。
首先，让我们来了解一下堆栈。
堆栈就像是一个垂直堆放的容器，遵循着“后进先出”（Last In First Out，简称LIFO）的原则。
想象一下，你有一堆盘子，每次你把新盘子放在最上面，而当你要取盘子时，也只能从最上面拿。
这就是堆栈的工作方式。
在编程中，堆栈有着广泛的应用。
比如，函数调用就是一个典型的例子。
当一个函数调用另一个函数时，新函数的信息被压入堆栈。
当被调用的函数执行完毕后，其信息从堆栈中弹出，程序回到原来的函数继续执行。
此外，表达式求值也常常会用到堆栈。
例如，计算一个复杂的算术表达式时，可以将操作数和运算符依次压入堆栈，然后按照特定的规则进行计算。
堆栈的实现可以通过数组或者链表来完成。
如果使用数组实现，需要注意堆栈的大小可能会有限制。
而链表实现则相对灵活，但其操作的复杂度可能会略高一些。
接下来，我们再看看队列。
队列则像是一条排队的队伍，遵循“先进先出”（First In First Out，简称 FIFO）的原则。
就好比在银行排队办理业务，先来的人先得到服务并离开队伍。
在实际应用中，队列也非常有用。
例如，打印机的打印任务队列就是一个典型的例子。
新的打印任务被添加到队列的末尾，而打印机按照任务进入队列的顺序依次处理。
还有操作系统中的任务调度，也常常会用到队列来管理等待执行的任务。
队列同样可以通过数组或者链表来实现。
使用数组实现时，可能会面临队列前端元素删除后空间浪费的问题。
而链表实现虽然可以避免这个问题，但需要额外的指针操作。
那么，堆栈和队列在操作上有哪些不同呢？对于堆栈，主要的操作是入栈（push）和出栈（pop）。
入栈就是将元素添加到堆栈的顶部，出栈则是从堆栈的顶部取出元素。
而对于队列，主要的操作是入队（enqueue）和出队（dequeue）。
1第3章栈和队列3.1 栈3.2 队列2栈和队列是两种特殊的线性表，其特殊性在于插入和删除运算的限制上。
这两种线性结构在程序设计中经常使用。
33.1 栈3.1.1 栈的抽象数据类型3.1.2 顺序栈3.1.3 链式栈3.1.4 栈的应用举例3.1.5 栈与递归43.1 栈(stack)栈是一种限定仅在一端进行插入和删除操作的线性表。
插入：入栈（压栈） 删除：出栈（退栈） 插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）。
特征：后进先出(LIFO表，Last-In First-Out)。
k 0k 1k 2k 3栈底栈顶出栈入栈53.1.1 栈的抽象数据类型template <class ELEM> class Stack {public:void clear(); // 清空bool push(const T item); // 入栈bool pop(T& item); // 出栈bool top(T& item); // 返回栈顶内容bool is Empty(); //判栈是否空bool isFull(); // 判栈是否满};6栈的实现顺序栈采用顺序存储结构表示的栈链式栈采用链式存储结构表示的栈7template <class T>class arrStack : public Stack<T> {private:int mSize; // 栈容量int top; // 栈顶指针，初始为-1T *st; // 存放栈内容的连续空间public:arrStack(int size) { mSize=size; top=-1; st=new T[mSize];}arrStack() {mSize = 0; top = -1; st = null;}~arrStack() { delete[] st; }void clear() { top = -1;}bool push(const T item);bool pop(T& item);bool top(T& item);};3.1.2 顺序栈8template <class T>bool arrStack<T>::push(const T item) {if (top==mSize-1){cout<<"栈满"<endl;return false;}else {st[++top]=item;return true;}}k 0k 1k 2k 3top top栈空9自动解决栈溢出的入栈操作template <class T>bool arrStack<T>::push(const T item) {if (top==mSize-1){ // 扩展存储空间T * new2St = new T[mSize*2];for (i=0;i<top ;i++) newst[i]=st[i];delete [] st;st=newSt;mSize *=2;}st[++top]=item;return true;}10template <class T>bool arrStack<T>::pop(T& item) {if (top==-1){cout<<“栈为空，不能执行出栈操作"<endl;return false;}else {item = st[top--];return true;}}11template <class T>bool arrStack<T>::top(T& item) {if (top==-1){cout<<“栈为空，不能读取栈顶元素"<endl;return false;}else {item = st[top ];return true;}}123.1.3 链式栈\top13template <class T>class lnkStack : public Stack<T>{private:Link<T>*top; // 头指针int size; // 结点个数public:lnkStack(int defSize) { top=NULL; size=0; }~lnkStack() { clear(); }void clear();bool push(const T item);bool pop(T& item);bool top(T& item);}；14template <class T>void lnkStack::clear(){while (top!=NULL) {Link<T>* temp = top;top = top->next;delete temp;}size=0;}template <class T>bool lnkStack::push(const T item){Link<T>* tmp=new Link<T >(item, top );top=tmp;size++;return true;}template <class T>bool lnkStack::pop(T& item) {Link<T>* item;if (size==0){cout<<"栈空"<<endl;return false;}item=top->data;tmp=top->next;delete top;top=tmp;size--;return true;}153.1.4 栈的应用举例数制转换 迷宫问题表达式括号匹配检验 表达式求值 背包问题161.数制转换（1348）10=（2504）8==========================N N/8 N%81348 168 416821 021 2 52 0 2while (N) {N%8入栈；N/8=>N;}while (栈非空）{出栈；输出；}17//将非负十进制整数转换成八进制输出void conversion( ){Stack s;cin>>N;while (N){s.push( N%8); N=N/8;}while (!s.isEmpty()){s.pop(e); cout<<e;}}182.迷宫问题1234567891011121314151617181213141516171819201419*1234o o o o oo o o o o o oo o o o o o入口出口20*1234入口出口0 1 2 3 4 5 6 7 8 9 10 1112345687109OO21算法基本思路“穷举求解”，即从入口出发，沿某一方向向前试探，若能走通，则继续往前走；否则原路退回，换一个方向再继续试探，直到走到出口或确定无路可走为止。
