零前言

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

原因其实也类似，实现方便，可以避免内存泄漏而且方便调试。最重要的效率原因，如果用 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];