浅谈栈与队列
摘要：首先介绍了栈与队列二者的具体含义。其次，具体的描述了栈与队列的逻辑结构以及两者顺序、链接存储结构及实现方法。之后，又列出了栈和队列两者的分类及其分类之间的比较。最后，为栈和队列的应用分别寻找了一个实例来加以阐释，通过C语言的代码实现二者的应用。
关键词：逻辑结构；顺序存储；链接存储；C语言；应用实现
Talk about Stack and Queue
Abstrac t：First, it introduces the specific meaning of stack and queue. And it explains the connection between them. Second, it has s pecific description of the stack and queue logic structure and both sequence, link storage structure and realization method. Later, it lists the stack and queue the classification and comparison between the classification.Finally, stack and queue for the application of looking for a respectively to elaborate examples to, through the C language code realize their application.[2]
Key words：Logical Structure; Sequential Storage; Link Storage; C Lanuage; Application
0 引言
所谓的栈和队列，其实是一种技术，有时候需要特殊的存储方式，然后在必要的时候还原该元素，就会利用到栈或者队列，例如在ARM操作的一些裸机代码中，需要保持状态寄存器中的值，根据需要可以利用栈或者队列来存储，用起来很方便安全，所以在涉及到存储数据之类的操作时候，要想到这两个技术。[1]
1 栈与队列
1.1 两者的含义
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候，从栈顶开始弹出数据（最后一个数据被第一个读出来）。
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列中没有元素时，称为空队列。[3]
1.2 两者的相同处与不同处
栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。队列（Queue）是定只能在表的一端进行插入和在另一端进行删除操作的线性表。从“数据结构”的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"限定"。[4]
栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。
2栈
2.1 栈的存储
2.1.1 栈的顺序存储结构
栈的顺序存储结构称为顺序栈。
顺序栈的本质上是顺序表的简化，唯一需要确定的是用数组的哪一段表示栈底。通常把数组中下标为0的一端作为栈底，同时附设指针top指示栈顶元素在数组中的位置。设存储栈元素的数组长度为stacksize，则栈空时栈顶指针top=-1；栈满时栈顶指针top=stacksiza-1.入栈时，栈顶指针top加1，出栈时，栈顶指针top减1。
2.1.2栈的链接存储结构
栈的链接存储结构称为链栈。
通常链栈用单链表表示，因此其节点结构与单链表的结点结构相同。因为只能在栈顶执行插入和删除操作，显然以单链表的头部做栈顶是最为方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。[5]
2.2 顺序栈和链栈的比较
顺序栈的实现在于使用了数组这个基本数据结构，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用光而引起的溢出问题，二在系统将内存分配给数组后，则这些内存对于其他任务就不可用；而对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间开始，另外当某个项不使用时也可将内存返还给系统。
3 队列
3.1队列的存储
3.1.1 队列的顺序存储结构
队列是特殊的线性表，从这个出发点来考虑队列的顺序存储问题。
假设线性表有n个数据元素，顺序表要求把表中的所有元素都存储在数组的前n个单元。假设队列有n个元素，顺序存储的队列也应该把队列的所有元素都存储在数组的前n 个单元。如果把队头元素放在数组下标为0的一端，则入队操作的时间开销为O（n），因为
要保证剩下的n-1个元素仍然存储在数组的前n-1个单元，所有元素都要向前移动一个位置。
3.1.2队列的链接存储结构
队列的链式存储结构称为链队列。
链队列是在单链表的基础上做了简单的修改，为了使空队列和非空队列的操作一致，链队列也加上头结点。根据队列的先进先出的特征，为了操作上的方便，设置队头指针指向链队的头结点，队尾指向终端结点。
3.2 循环队列和链队列的比较
实现循环队列和链队列的基本操作的算法都需要常数时间O(1)。循环队列和链队列的空间性能的比较与顺序栈和链栈的空间性能的比较类似，只是循环队列不能像顺序栈那样共享空间，通常不能在一个数组中存储两个循环队列。[7]
4 栈和队列的实现方式
4.1 栈的实现方式
将栈的抽象数据类型定义在顺序栈存储结构下用C++中的类实现，由于栈元素的数据类型不确定，因此采用C++的模版机制。[6]
Const int StackSize=10;
Template
Class SeqStack
{
public:
SeqStack(){top=-1;}
~SeqStack(){}
Void Push(DataType x);
DataType Pop();
DataType GetTop(){if(top!=-1)return data[top];}
int Empty(){top==-1?return 1:return 0;}
private:
DataType data[StackSize];
int top;
}
4.2 队列的实现方式
将队列的抽象类型定义在循环队列存储结构下用C++中的类实现，因为队列元素的数据类型不确定，所以采用C++的模版机制。
const int QueueSize=100;
template
class CirQueue
