栈和队列在程序设计中的作用

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，

故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。

栈的定义及基本运算

1、栈的定义

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。

(2)当表中没有元素时称为空栈。

(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO 表。

栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入

（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

【示例】元素是以a1，a2，…，an 的顺序进栈，退栈的次序却是an，an-1，…，a1。

2、栈的基本运算

（1）InitStack（S）

构造一个空栈S。

（2）StackEmpty（S）

判栈空。若S 为空栈，则返回TRUE，否则返回FALSE。

（3）StackFull（S）

判栈满。若S 为满栈，则返回TRUE，否则返回FALSE。

注意：

该运算只适用于栈的顺序存储结构。

（4）Push（S，x）

进栈。若栈S 不满，则将元素x 插入S 的栈顶。

（5）Pop（S）

退栈。若栈S 非空，则将S 的栈顶元素删去，并返回该元素。

（6）StackTop（S）

取栈顶元素。若栈S 非空，则返回栈顶元素，但不改变栈的状态。

顺序栈

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

1、顺序栈的类型定义

#define StackSize 100 //假定预分配的栈空间最多为100 个元素

typedef char DataType;//假定栈元素的数据类型为字符

typedef struct{

DataType data[StackSize];

int top;

}SeqStack;

注意：

①顺序栈中元素用向量存放

②栈底位置是固定不变的，可设置在向量两端的任意一个端点

③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top 为栈顶指针）来指示

当前栈顶位置

2、顺序栈的基本操作

前提条件：

设S 是SeqStack 类型的指针变量。若栈底位置在向量的低端，即S-＞data[0]是栈底元素。

（1） 进栈操作

进栈时，需要将S-＞top 加1

注意：

①S-＞top==StackSize-1 表示栈满

②"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。

上溢是一种出错状态，应设法避免。

（2） 退栈操作

退栈时，需将S-＞top 减1

注意：

①S-＞top<0 表示空栈

②"下溢"现象——当栈空时，做退栈运算产生的溢出现象。

下溢是正常现象，常用作程序控制转移的条件。

顺序栈在进栈和退栈操作时的具体变化情况【参见动画演示】

3、顺序栈的基本运算

（1） 置栈空

void InitStack（SeqStack *S）

{//将顺序栈置空

S->top=-1;

}

（2） 判栈空

int StackEmpty（SeqStack *S）

{

return S->top==-1;

}

（3） 判栈满

int StackFull（SeqStack *SS）

{

return S->top==StackSize-1;

}

（4） 进栈

void Push（S，x）

{

if (StackFull(S))

Error("Stack overflow"); //上溢，退出运行

S->data[++S->top]=x;//栈顶指针加1 后将x 入栈

}

（5） 退栈

DataType Pop（S）

{

if(StackEmpty(S))

Error("Stack underflow"); //下溢，退出运行

return S->data[S->top--];//栈顶元素返回后将栈顶指针减1

}

（6） 取栈顶元素

DataType StackTop（S）

{

if(StackEmpty(S))

Error("Stack is empty");

return S->data[S->top];

}

4、两个栈共享同一存储空间

当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。

当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的

部分存储空间。

只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长

度为m 的向量空间和两个栈分别占用两个长度为└ m/2┘和┌m/2┐的向量空间比较，前者发生上溢的概

率比后者要小得多。

链栈

栈的链式存储结构称为链栈。

1、链栈的类型定义

链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。

链栈的类型说明如下：

typedef struct stacknode{

DataType data

struct stacknode *next

}StackNode;

typedef struct{

StackNode *top; //栈顶指针

}LinkStack;

注意：

①LinkStack 结构类型的定义是为了方便在函数体中修改top 指针本身

②若要记录栈中元素个数，可将元素个数属性放在LinkStack 类型中定义。

2、链栈的基本运算

（1） 置栈空

Void InitStack(LinkStack *S)

{

S->top=NULL;

}

（2） 判栈空

int StackEmpty(LinkStack *S)

{

return S->top==NULL;

}

（3） 进栈

void Push(LinkStack *S,DataType x)

{//将元素x 插入链栈头部

StackNode *p=(StackNode *)malloc(sizeof(StackNode));

p->data=x;

p->next=S->top;//将新结点*p 插入链栈头部

S->top=p;

}

（4） 退栈

DataType Pop(LinkStack *S)

{

DataType x;

StackNode *p=S->top;//保存栈顶指针

if(StackEmpty(S))

Error("Stack underflow."); //下溢

x=p->data; //保存栈顶结点数据

S->top=p->next; //将栈顶结点从链上摘下

free(p);

return x;

}

（5） 取栈顶元素

DataType StackTop(LinkStack *S)

{

if(StackEmpty(S))

Error("Stack is empty.")

return S->top->data;

}

注意：

链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull 运算。

--------------------------------------------------------------------------------------------

-----------------

队列的定义及基本运算

1、定义

队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表

（1）允许删除的一端称为队头（Front）。

（2）允许插入的一端称为队尾（Rear）。

（3）当队列中没有元素时称为空队列。

（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO 表。

队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的

成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。

【例】在队列中依次加入元素a1，a2，… ，an 之后，a1 是队头元素，an 是队尾元素。退出队列的次序

只能是a1，a2，… ，an。

2、队列的基本逻辑运算

（1）InitQueue（Q）

置空队。构造一个空队列Q。

（2）QueueEmpty（Q）

判队空。若队列Q 为空，则返回真值，否则返回假值。

（3） QueueFull（Q）

判队满。若队列Q 为满，则返回真值，否则返回假值。

注意：

此操作只适用于队列的顺序存储结构。

（4） EnQueue（Q，x）

若队列Q 非满，则将元素x 插入Q 的队尾。此操作简称入队。

（5） DeQueue（Q）

若队列Q 非空，则删去Q 的队头元素，并返回该元素。此操作简称出队。

（6） QueueFront（Q）

若队列Q 非空，则返回队头元素，但不改变队列Q 的状态。

顺序队列

1、顺序队列

（1）顺序队列的定义

队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

（2） 顺序队列的表示

①和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。

②由于队列的队头和队尾的位置是变化的，设置两个指针front 和rear 分别指示队头元素和队尾元素

在向量空间中的位置，它们的初值在队列初始化时均应置为0。

（3） 顺序队列的基本操作

①入队时：将新元素插入rear 所指的位置，然后将rear 加1。

②出队时：删去front 所指的元素，然后将front 加1 并返回被删元素。

注意：

①当头尾指针相等时，队列为空。

②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。

顺序队列基本操作【参见动画演示】

（4）顺序队列中的溢出现象

① "下溢"现象

当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

② "真上溢"现象

当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

③ "假上溢"现象

由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中

实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。

该现象称为"假上溢"现象。

【例】假设下述操作序列作用在初始为空的顺序队列上：

EnQueue，DeQueue，EnQueue，DeQueue，…

尽管在任何时刻，队列元素的个数均不超过1，但是只要该序列足够长，事先定义的向量空间无论多大

均会产生指针越界错误。

链队列

1、链队列的定义

队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。

2、链队列的结构类型说明

注意：

增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作。

链队列示意图见上图，图中Q 为LinkQueue 型的指针。

3、链队列的基本运算

（1） 置空队

void InitQueue(LinkQueue *Q)

{

Q->front=Q->rear=NULL;

}

（2） 判队空

intQueueEmpty(LinkQueue *Q)

{

return Q->front==NULL&&Q->rear==Null;

//实际上只须判断队头指针是否为空即可

}

（3） 入队

void EnQueue(LinkQueue *Q,DataType x)

{//将元素x 插入链队列尾部

QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点

p->data=x; p->next=NULL;

if(QueueEmpty(Q))

Q->front=Q->rear=p; //将x 插入空队列

else { //x 插入非空队列的尾

Q->rear->next=p; //*p 链到原队尾结点后

Q->rear=p; //队尾指针指向新的尾

}

}

（4） 出队

DataType DeQueue (LinkQueue *Q)

{

DataType x;

QueueNode *p;

if(QueueEmpty(Q))

Error("Queue underflow");//下溢

p=Q->front; //指向对头结点

x=p->data; //保存对头结点的数据

Q->front=p->next; //将对头结点从链上摘下

if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空

Q->rear=NULL;

free(p); //释放被删队头结点

return x; //返回原队头数据

}

（5） 取队头元素

DataType QueueFront(LinkQueue *Q)

{

if(QueueEmpty(Q))

Error("Queue if empty.");

return Q->front->data;

}

注意：

①和链栈类似，无须考虑判队满的运算及上溢。

②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，

故删去此结点时亦需修改尾指针，且删去此结点后队列变空。

③以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点

前也可附加一个头结点，增加头结点的链队列的基本运算【参见练习】

循环队列

为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这

种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。

（1） 循环队列的基本操作

循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界

（QueueSize-1）时，其加1 操作的结果是指向向量的下界0。这种循环意义下的加1 操作可以描述为：

① 方法一：

if(i+1==QueueSize) //i 表示front 或rear

i=0;

else

i++;

② 方法二--利用"模运算"

i=(i+1)%QueueSize；

（2） 循环队列边界条件处理

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时

头尾指针均相等。因此，无法通过条件front==rear 来判别队列是"空"还是"满"。【参见动画演示】

解决这个问题的方法至少有三种：

① 另设一布尔变量以区别队列的空和满；

② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1 后是否等于头指针，若相等则认

为队满（注意：rear 所指的单元始终为空）；

③使用一个计数器记录队列中元素的总数（即队列长度）。

（3） 循环队列的类型定义

#define Queur Size 100 //应根据具体情况定义该值

typedef char Queue DataType; //DataType 的类型依赖于具体的应用

typedef Sturet{ //头指针，队非空时指向队头元素

int front; //尾指针，队非空时指向队尾元素的下一位置

int rear; //计数器，记录队中元素总数

DataType data[QueueSize]

}CirQueue;

（4） 循环队列的基本运算

用第三种方法，循环队列的六种基本运算：

① 置队空

void InitQueue(CirQueue *Q)

{

Q->front=Q->rear=0;

Q->count=0; //计数器置0

}

② 判队空

int QueueEmpty(CirQueue *Q)

{

return Q->count==0; //队列无元素为空

}

③ 判队满

int QueueFull(CirQueue *Q)

{

return Q->count==QueueSize; //队中元素个数等于QueueSize 时队满

}

④ 入队

void EnQueue(CirQueuq *Q,DataType x)

{

if(QueueFull((Q))

Error("Queue overflow"); //队满上溢

Q->count ++; //队列元素个数加1

Q->data[Q->rear]=x; //新元素插入队尾

Q->rear=(Q->rear+1)%QueueSize; //循环意义下将尾指针加1

⑤ 出队

DataType DeQueue(CirQueue *Q)

{

DataType temp;

if(QueueEmpty((Q))

Error("Queue underflow"); //队空下溢

temp=Q->data[Q->front];

Q->count--; //队列元素个数减1

Q->front=(Q->front+1)&QueueSize; //循环意义下的头指针加1

return temp;

}

⑥取队头元素

DataType QueueFront(CirQueue *Q)

{

if(QueueEmpty(Q))

Error("Queue if empty.");

return Q->data[Q->front];

}