关于栈和队列的一些思考

    首先，我想就数据结构的概念做一个陈述，这样便于我们从大局上对一些具体的数据结构进行把握。所谓数据结构，是指数据元素（或称之为数据对象）的集合以及元素之间的相互关系（需要注意的是，这里的“关系”所包含的含义是比较广的，包括元素位置上的关系、元素所携带的value在大小上的关系等等）。元素之间的相互关系是数据集合的逻辑结构，而这种逻辑结构在具体的存储空间中的表达则称之为数据集合的存储结构（或物理结构）。总的来说，对于一个数据结构，我们必须对它有两个维度上的理解，一个是它的逻辑结构是什么样子的，另一个就是它可以用什么样的物理存储结构来实现。
   
    从大体上来讲，数据结构可分为线性结构和非线性结构。线性结构的特点是数据元素之间呈现一种线性关系。这里，我们引入一个概念，那就是“线性表”，线性表是最简单、最基本、也是最常用的一种线性结构。它有两种存储方法：顺序存储和链式存储。数组则是作为线性表的顺序存储的代表，那么链式存储的代表呢？那当然是链表了。基于上面所讨论的，个人认为可以采用分层的思想来理解数据结构，大体上而言，一种数据结构可分为物理层和逻辑层。数组和链表都属于物理层上的数据结构，它们在逻辑层上的性质我们暂且不去讨论。
   
    接着，我们就要引出本文所要讨论的两大主角了，栈与队列。前面谈到了线性表，那么本文的主角跟线性表究竟是什么关系呢？实际上，栈与队列的逻辑结构和线性表是相同的，都是线性结构，只是它们在对所包含的元素的操作上有所限制。栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，所以可称之为操作受限的线性表。

    对于栈，我想大家应该都不会陌生，即便是在现实生活中我们也见过不少栈结构的东西，比如弹匣，我想我们应该都在电影或者现实生活中见过的。实际上，弹匣就是一种栈结构的东西，我们在脑海中试想一下，弹匣中首先被发射的子弹是最先进去的还是最后进去的。如果有人回答是最先进去的，那么我想，这个人该回家好好地看看警匪片了，呵呵。好了，那么，我想以后大家在提到栈时，脑海中就会冒出弹匣的图像了。对于栈，大家该记住的一点就是“后进先出”。还有，要提到的一点就是，栈可以理解为是逻辑层的数据结构，它的物理层可以由数组和链表来实现，也就是说，它可以有顺序存储和链式存储两种存储方式。关于栈的其它一些属性和特点，在这里我们就不再讨论了。在这里，我想讨论的是，关于栈的一些稍微深入一点的问题，另外还有一些个人的理解和思考。首先，大家是否想过一点，栈是动态的一种数据结构，而数组则是呈静态的，因为数组一旦被创建，就没法改变它的大小了。既然这样，那么，用数组是如何实现栈的呢？实际上，用数组实现栈时，栈的动态性是通过top指针来实现的，而数组自身的性质并没有变。甚至在弹栈后，数组中的元素也并没有改变，我们所做的操作只是将top指针往前移了一个数组单元。压栈时，我们是将top指针往后移了一个数组单元，然后用即将压入的元素覆盖掉原先存放于该数组单元的元素。top指针所存放的地址实际上也只需是数组的下标就可以了。与此同理的是，数组对于队列的实现。接着，我想引入几个问题，我们可以一起思考一下（答案的提示我将在文章的末尾给出）：
（1）如何用一个数组来实现两个栈，使得两个栈中的元素总数不到n时，两者都不会发生上溢。注意push和pop操作的时间应为O(1)
（2）如何用两个栈来实现一个队列
（3）如何用两个队列实现一个栈

    对于队列，我们可以联想一下现实生活中的排队，索性我们就假设排队买火车票的场景，我想这个对于大家应该都不会陌生的。这里我们有一个前提，就是不存在插队的现象。那么，首先能买到票离开队伍的是不是第一个去排队的人呢？是不是先排队的人就先买到票呢？我想答案是显然的。于是乎，队列的“先进先出”特性，我想我们是很容易理解的了。这里，我想提的一点是，实际上，队列的动态性是通过head指针和tail指针的移动来实现的，正如我上面所说的那样。那么如何判断一个循环队列是空的或者是满的呢？其实是这样的，我们先来看一下对于队列的入队出队操作，head、tail指针是如何移动的。首先，初始化队列时，将队列的head指针和tail指针同时指向队列的第一个元素，此时队列为空,head=tail=null。当我们执行入队操作时，tail指针向后移动一个单元，head指针不变，此时，head指针正好指向了刚刚入队的元素,tail指针指向了第二个元素（是一个不存放任何数据的单元）；而出队时是head指针向后移动一个单元，tail指针不变，此时排在队列第二前的元素就变成队头元素了。当队列满时，head=tail+1。对于上面描述的，建议大家可以在纸上画一下，那样会比较清晰点。也就是说，判断循环队列为空的条件是：head=tail=null；判断循环队列为满的条件是：head=tail+1（这里的1是指一个存储单元）。

    （对于上面提出的三个问题，在这里给出一些提示信息：（1）用环形数组实现 （2）取两个栈，一个栈专门用来模拟队列的队头，即实现出队，另一个用来模拟队列的队尾，实现入队，每次要入队时，就将考虑模拟队头的栈中是否有元素，如果有，就将里面的元素弹出并压入用来模拟队尾的栈，然后再压入即将要入队的元素；出队时，则将队尾栈中的元素弹出再压入队头栈中，然后再对队头栈弹栈，即实现了出队（3）取两个队列，命名为队列A和队列B，第一次压栈时，将元素放入队列A中，第二次压栈时则将元素放入队列B中，然后再队列A中的元素出队放入队列B中，就这样交互进行着，就实现了将“先进先出”转化为“后进先出”了）