零 前言

继上篇用数组模拟链表，本篇讲一讲如何用数组模拟栈和队列。

原因其实也类似，实现方便，可以避免内存泄漏而且方便调试。最重要的效率原因，如果用 new 很容易超时。

提示：本文为C++实现，但所有语言通用，会省略部分与实现无关的代码。

一 栈

栈（stack）是一种受到限制的线性表，元素的插入和删除只能在同一端进行。

允许插入和删除的称为栈顶（top），另一端叫做栈底（bottom）。向一个栈中插入新元素称为入栈（push），从一个栈中删除元素称为出栈（pop）。

我们可以想象一堆摞着的盘子，我们每次拿要先从最上面的一个拿起，放也要放到最上面，这样的操作特性可以概括为后进先出（LIFO last in first out）。

实现

我们用一个 top 指针指向栈顶，初始时指向数组0号位，同时为了便于判空，0号位不存储数据。

代码非常简单，为了便于理解，我还是画了张图：

// stk为栈数组，N是一个常量
 int stk[N], top;
 // 插入和删除
 stk[++top] = x;     // push x
 top--;              // pop
 // 判断栈是否为空
 return top == 0;    
 // 查询栈顶元素
 return stk[top];
复制代码

栈的应用在计算机中到处可见，比如我们每天写代码调用函数都会用到程序调用栈，调用函数时我们会将下个指令的地址存在堆栈中，执行完后取出回到原来的程序。再比如表达式求值问题，二叉树的遍历，图的深度优先搜索，递归调用等等等等。

二 队列

同栈一样，队列（queue）同样受到限制，只允许在表的一段进行插入，而在另一端删除元素。

允许插入的一端叫队尾（rear），允许删除的一端叫队头（front）。向队列中插入元素称为入队（enqueue），删除元素称为出队（dequeue）。

可以想象一个排队出门的场景，排在前面的人就是最先出去的人，新来的则需要在队尾排队，可以概括为先进先出（FIFO first in first out）。

实现

用两个指针 front 和 rear 分别指向队头和队尾，初始值分别为0和-1，可用 front > rear来进行判空，同样画了张图便于理解：

int q[N], front, rear = -1;
 q[++rear] = x;      // enqueue
 front++;            // dequeue
 // 判断队列是否为空
 return front > rear;
 // 查询队头元素
 return q[front];
复制代码

队列其实就是生活中“先来后到”的理念，排队买东西，挂号系统等等都体现了队列的结构。计算机中常用于操作系统，在多用户环境下尤为重要。例如，多个用户同时申请打印机资源，但由于打印机一次只能打印一个文档，我们就需要一个队列来存储用户提交的打印作业。

三 总结

栈知识点题库 - 力扣（LeetCode） (leetcode-cn.com)

队列知识点题库 - 力扣（LeetCode） (leetcode-cn.com)

栈和队列我们只要记住它们存储数据的特点为后进先出和先进先出。算法实现上，为了提高效率，采用数组模拟栈和队列的方式。

二叉树遍历和表达式求值一般用栈实现，而队列最常见的算法题便是滑动窗口，这两天会更新有关滑动窗口的内容。