链表（Linked List）、栈（Stack）、队列（Queue）是数据结构中最基础的三大结构（还有一个是数组）。熟悉并掌握数据结构和算法是合格程序员基本功之一，不同的结构在不同的应用场景中往往会带来不一样的处理效率。之前文章中已经介绍了链表，本文将介绍栈和队列，以及这三种结构的实现方法。

栈和队列

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈，通俗地说，就像我们往一个杯子里面放东西一样，先放进去的放在最下面，只有把上面的东西拿出来后才能拿出下面压着的东西。

栈，具有很多用处，计算机中很多处理都是通过栈这种数据结构来进行的，比如算术运算，准备两个栈，一个栈存储数字，一个栈存储符号，从头开始依次把字符对应压入到这两个栈中，当所有字符都放入栈之后，依次从数字栈中取出两个元素，并从符号栈中取出一个元素，进行计算，结果压回数字栈，继续以此运行，直到符号栈为空，或者数字栈只剩下一个元素为止，弹出这个数字即为最后的结果。

这么说很抽象，后面以实际题目进行讲解。

实现方法

可以用数组（连续的内存空间，按索引取值）来实现栈。

栈的基本方法只有两个，分别为入栈（Push）元素和出栈（Pop）。

以 Lab3 作为例题，题目如下：