目录
（3）销毁队列DestroyQueue(LinkQuNode *&q)
从组成元素的逻辑关系看，栈和队列都属于线性结构。栈和队列与线性表的不同之处在于它们的相关运算具有一些特殊性。更准确地说，一般线性表的插入、删除运算不受限制，而栈和队列上的插入、删除运算均受某种特殊限制，因此栈和队列也成为操作受限的线性表。
本文介绍栈和队列的基本概念、存储结构、基本运算算法设计和应用实例。
栈是一种常用而且重要的数据结构之一，如用于保存函数调用时所需要的信息，通常在将递归算法转换成非递归算法时需要使用到栈。
栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，表的另一端称为栈底。栈顶的当前位置是动态的，栈顶的当前位置由一个被称为栈顶指针的位置指示器来指示。当栈中没有数据元素时称为空栈。栈的插入操作通常称为进栈或入栈(push)，栈的删除操作通常称为出栈或退栈(pop)。
栈的主要特点是“后进先出”，即后进栈的元素先出栈。每次进栈的数据元素都放在原来栈顶元素之前成为新的栈顶元素，每次出栈的数据元素都是当前栈顶元素。栈也成为后进先出表。
ADT Stack
{
数据对象：
D={
为ElemType类型} //ElemType是自定义类型标识符
数据关系：
R={
}
基本运算：
InitStack(&s)：初始化栈，构造一个空栈s
DestroyStack(&s)：销毁栈，释放栈s占用的存储空间
StackEmpty(s)：判断栈是否为空，若栈s为空，则返回真；否则返回假
Push(&s,e)：进栈，将元素e插入到栈s中作为栈顶元素
Pop(&s,&e)：出栈，从栈s中删除栈顶元素，并将其值赋给e
GetTop(s,&e)：取栈顶元素，返回当前的栈顶元素，并将其值赋给e
}
分配一块连续的存储空间来存放栈中元素，并用一个变量（如top）指向当前的栈顶元素以反映栈中元素的变化。采用顺序存储结构的栈称为顺序栈（sequential stack）。
假设栈的元素个数最大不超过正整数MaxSize，所有的元素都具有同一数据类型，即ElemType，可用下列方式来声明顺序栈的类型SqStack：
typedef struct
{
ElemType data[MaxSize]; //存放战中的数据元素
int top; //栈顶指针，即存放栈顶元素在data数组中的下标
}SqStack; //顺序栈类型 栈到顺序栈的映射过程如下，本节采用栈指针s(不同于栈顶指针top)的方式创建和使用顺序栈。
综上所述，对于s所指的顺序栈（即顺序栈s），初始时设置s->top=-1，可以归纳出对后面算法设计来说非常重要的4个要素。
该运算创建一个空栈，由s指向它。实际上就是分配一个顺序栈空间，并将栈顶指针设置为-1。
void InitStack(SqStack *&s)
{
s=(SqStack *)malloc(sizeof(SqStack)): //分配一个顺序栈空间，首地址存放在s中
s->top=-1; //栈顶指针置为-1
}该运算释放栈s占用的存储空间。
void DestroyStack(SqStack *&s)
{
free(s);
}该运算实际上用于判断s->top==-1是否成立。
bool StackEmpty(SqStack *s)
{
return(s->top==-1);
}在栈不满的条件下先将栈顶指针增1，然后在该位置上插入元素e，并返回真；否则返回假。
bool Push(SqStack *&s,ElemType e)
{
if(s->top==MaxSize-1)
return false;
s->top++;
s->data[s->top]=e;
return true;
}在栈不为空的条件下先将栈顶元素赋给e，然后将栈顶指针减1，并返回真；否则返回假。
bool Pop(SqStack *&s,ElemType &e)
{
if(s->top==-1)
return false;
e=s->data[s->top];
s->top--;
return true;
}在栈不为空的条件下将栈顶元素赋给e并返回真，否则返回假。
bool GetTop(SqStack *s,ElemType &e)
{
if(s->top==-1)
return false;
e=s->data[s->top];
return true;
}设计一个算法利用顺序栈判断一个字符串是否为对称字符串。所谓对称字符串指从左向右读和从右向左读的序列相同。
【注】n个元素连续进栈，产生的连续出栈序列和输入序列正好相反，本算法就是利用这个特点设计的。对于字符串str，从头到尾将其所有元素连续进栈，如果所有元素连续出栈产生的序列和str从头到尾的字符依次相同，表示str是一个对称串，返回真；否则表示str不是一个对称串，返回假
bool symmetry(ElemType str[]) //判断str是否为对称串
{
int i;ElemType e;
SqStack *st; //定义顺序栈指针
InitStack(st); //初始化栈
for(i=0;str[i]!='\0';i++) //将str的所有元素进栈
Push(st,str[i]);
for(i=0;str[i]!='\0';i++) //处理str的所有字符
{
Pop(st,e); //退栈元素e
if(str[i]!=e) //若e与当前串字符不同表示不是对称串
{
DestroyStack(st); //销毁栈
return false; //返回假
}
}
DestroyStack(st); //销毁栈
return true; //返回真
}
顺序栈才用一个数组存放栈中的元素。如果需要用到两个相同类型的栈，这时若为他们各自开辟一个数组空间，极有可能出现这样的情况：第一个栈已满，再进栈就溢出了，而另一个栈还有很多空闲存储空间。解决这个问题的方法是将两个栈合起来，用一个数组来实现这两个栈，这称为共享栈（share stack）。
在设计共享栈时，由于一个数组（大小为MaxSize）有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈的栈底为数组的末端，即下表为MaxSize-1，这样在两个栈中进栈元素时栈顶向中间伸展。
共享栈的4个要素如下：
在上述设置中，data数组表示共享栈的存储空间，top1和top2分别为两个栈的栈顶指针，这样该共享栈通过data、top1和top2来标识，也可以将它们设计为一个结构体类型：
typedef struct
{
ElemType data[MaxSize];
int top1,top2;
}DStack;
采用链式存储结构的栈称为链栈（linked stack）。链表有很多种，这里采用带头结点的单链表来实现。链栈的优点是不存在栈满上溢出的情况。规定栈的所有操作都是在单链表的表头进行。
链栈中结点类型LinkStNode的声明如下：
typedef struct linknode
{
ElemType data; //数据域
struct linknode *next; //指针域
}LinkStNode; //链栈结点类型在以s为头结点指针的链栈（简称链栈s）中，可以归纳出对后面算法设计来说非常重要的4个元素：
创建一个空链栈s，实际上是创建链栈的头结点，并将其next域置为NULL。
void InitStack(LinkStNode *&s)
{
s=(LinkStNode *)malloc(sizeof(LinkStNode));
s->next=NULL;
}释放链栈s占用的全部结点空间，和单链表的销毁算法完全相同。
void DestroyStack(LinkStNode *&s)
{
LinkStNode *pre=s,*p=s->next; //pre指向头结点，p指向首结点
while(p!=NULL) //循环到p为空
{
free(pre); //释放pre结点
pre=p; //pre、p同步后移
p=pre->next;
}
free(pre); //此时pre指向尾结点，释放其空间
}
判断s->next=NULL的条件是否成立。
bool StackEmpty(LinkStNode *s)
{
return(s->next==NULL);
}新建一个结点，用于存放元素e（由p指向它），然后将其插入到头结点之后作为新的首结点
void Push(LinkStNode *&s,ElemType e)
{
LinkStNode *p;
p=(LinkStNode *)malloc(sizeof(LinkStNode));
p->data=e;
p->next=s->next;
s->next=p;
}在栈不为空的条件下提取首结点的数据域赋给引用型参数e，然后将其删除。
bool Pop(LinkStNode *&s,ElemType &e)
{
LinkStNode *p;
if(s->next==NULL) //栈空的情况
return false; //返回假
p=s->next; //p指向首结点
e=p->data; //提取首结点值
s->next=p->next; //删除首结点
free(p); //释放被删结点的存储空间
return true; //返回真
}在栈不为空的条件下提取首结点的数据域赋给引用形参数e。
bool GetTop(LinkStNode *s,ElemType &e)
{
if(s->next==NULL)
return false;
e=s->next->data;
return true;
}设计一个算法判断输入的表达式中括号是否配对（假设只含有左、右圆括号）
【注】该算法在表达式括号配对时返回真，否则返回假。设置一个链栈st，扫描表达式exp，遇到左括号时进栈；遇到右括号时，若栈顶为左括号，则出栈，否则返回假。当表达式扫描完毕而且栈为空时返回真；否则返回假。
bool Match(char exp[],int n)
{
int i=0;char e;
bool match=true;
LinkStNode(st);
InitStack(st); //初始化链栈
while(i<n&&match) //扫描exp中的所有字符
{
if(exp[i]=='(') //当前字符为左括号，将其进栈
Push(st,exp[i]);
else if(exp[i]==')') //当前字符为右括号
{
if(GetTop(st,e)==true) //成功取栈顶元素e
{
if(e!='(') //栈顶元素不为'('时
match=false; //表示不匹配
else //栈顶元素为'('时
Pop(st,e); //将栈顶元素出栈
}
else match=false; //无法取栈顶元素时表示不匹配
}
i++; //继续处理其他字符
}
if(!StackEmpty(st)) //栈不空时表示不匹配
match=false;
DestroyStack(st); //销毁栈
return match;
}队列也有广泛的应用，特别是在操作系统的资源分配和排队论中大量地使用了队列。
队列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。把进行插入的一端称为队尾，把进行删除的一端称为队头或队首。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队，元素出队后，其直接的后继元素就成为队首元素。
由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序出队，所以又把队列称为先进先出表。
ADT Queue
{
数据对象：
D={
数据关系：
R={
基本运算：
InitQueue(&q)：初始化队列，构造一个空队列q
DestroyQueue(&s)：销毁队列，释放队列q占用的存储空间
QueueEmpty(s)：判断队列是否为空，若队列q为空，则返回真；否则返回假
enQueue(&s,e)：进队列，将元素e进队作为队尾元素
deQueue(&s,&e)：出队列，从队列q中出队一个元素，并将其值赋给e
}
分配一块连续的存储空间来存放队列中的元素，并用两个整型变量来反映队列中的元素变化，他们分别存储队首元素和队尾元素的下标位置，分别称为队首指针（队头指针）和队尾指针。采用顺序存储结构的队列称为顺序队。
假设队列中元素个数最多不超过整数MaxSize，所有的元素都具有ElemType数据类型，则顺序队类型SqQueue声明如下：
typedef struct
{
ElemType data[MaxSize]; //存放队中元素
int front,rear; //队头和队尾指针
}SqQueue; //顺序队类型队列到顺序队的映射过程如下图所示，并且约定在顺序队中队头指针front指向当前队列中队头元素的前一个位置，队尾指针rear指向当前队列中队尾元素的位置。本文采用队列指针q的方式建立和使用顺序队。
综上所述，对于q所指的顺序队（即顺序队q），初始时设置q->rear=q->front=-1，可以归纳出对后面算法设计来说非常重要的4个要素：
构造一个空队列q，将front和rear指针均设置成初始状态，即-1值。
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc(sizeof(SqQueue));
q->front=q->rear=-1;
}释放队列q占用的存储空间。
void DestroyQueue(&q)
{
free(q);
}若队列q为空，返回真；否则返回假。
bool QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}在队列q不满的条件下先将队尾指针rear增1，然后将元素e插入到该位置。
bool enQueue(SqQueue *&q,ElemType e)
{
if(q->rear==MaxSize-1)
return false;
q->rear++;
q->data[q->rear]=e;
return true;
}在队列q不为空的条件下先将队头指针front增1，并将该位置的元素赋给e。
bool deQueue(SqQueue *&q,ElemType &e)
{
if(q->front==q->rear)
return false;
q->front++;
e=q->data[q->front];
return true;
}在前面的顺序队操作中，元素进队时队尾指针rear增1，元素出队时队头指针front增1，当队满的条件（即rear==MaxSize-1）成立时，表示此时队满（上溢出）了，不能再进队元素。实际上，当rear=MaxSize-1成立时，队列中可能还有空位置，这种因为队满条件设置不合理导致队满条件成立而队列中仍然有空位置的情况称为假溢出（false overflow）。图3.17（c）就是假溢出的情况。
可以看出，再出现假溢出时队尾指针rear指向data数组的最大下标，而另外一端还有若干个空位置。解决的办法是把data数组的前端和后端连接起来，形成一个环形数组，即把存储队列元素的数组从逻辑上看成一个环，称为环形队列或者循环队列（circular queue）。
环形队列首尾相连后，当队尾指针rear=MaxSize-1后，再前进一个位置就到达0，于是就可以使用另一端的空位置存放队列元素了。实际上存储器中的地址总是连续编号的，为此次啊用数学上的求余运算（%）来实现：
队头指针front循环增1：front=(front+1)%MaxSize
队尾指针rear循环增1：rear=(rear+1)%MaxSize
环形队列的队头指针front和队尾指针rear初始化时都置为0，即front=rear=0。在进队元素和出队元素时，队尾指针和队头指针分别循环增1。
那么，环形队列q的队满和队空条件如何设置呢？显然队空条件是q->rear==q->front。当进队元素的速度快于出队元素的速度时，队尾指针会回过来很快赶上队首指针，此时可以看出环形队列的队满条件也是q->rear==q->front，也就是说无法仅通过这两个指针的当前位置区分开队空和队满。
那怎么区分队空和队满呢？改为以“队尾指针循环增1时等于队头指针”作为队满条件，也就是说尝试进队一次，若达到对头，就认为队满了，不能再进队了。这样环形队列少用一个元素空间，即该队列中在任何时刻最多只能有MaxSize-1个元素。
因此，在环形队列q中设置：
下图说明了环形队列操作的几种状态，这里假设MaxSize等于5。
构造一个空队列，将front和rear指针均设置成初始状态，即0值。
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc(sizeof(SqQueue));
q->front=q->rear=0;
}释放队列q占用的存储空间。
void DestroyQueue(SqQueue *&q)
{
free(q);
}若队列为空返回真；否则返回假。
bool QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}在队列不满的条件下先将队尾指针rear循环增1，然后将元素插入到该位置。
bool enQueue(SqQueue *&q,ElemType)
{
if((q->rear+1)%MaxSize==q->front)
return false;
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return true;
}在队列q不空的条件下将首指针front循环增1，取出该位置的元素并赋给e。
bool deQueue(SqQueue *&q,ElemType &e)
{
if(q->front==q->rear)
return false;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}【注】在环形队列中，队头指针front指向队中队头元素的前一个位置，队尾指针rear指向队中的队尾元素，队列中的元素个数=(rear-front+MaxSize)%MaxSize
采用链式存储结构的队列称为链队。链表有多种，这里采用单链表来实现链队。
在这样的链队中只允许在单链表的表头进行删除操作 （出队）和在单链表的表尾进行插入操作（进队），因此需要使用队头指针front和队尾指针rear两个指针，用front指向队首结点，用rear指向队尾结点。和链栈一样，链队中也不存在队满上溢出的情况。
链队中数据结点的类型DataNode声明如下：
typedef struct qnode
{
ElemType data; //存放元素
struct qnode *next; //下一个结点指针
}DataNode; //链队数据结点的类型链队头结点（或链队结点）的类型LinkQuNode声明如下：
typedef struct
{
DataNode *front;
DataNode *rear;
}LinkQuNode;
在以q为链队结点指针的链队（简称链队q）中，可以归纳出对后面算法设计来说非常重要的四个要素：
构造一个空队，即创建一个链表结点，其front和rear域均置为NULL。
void InitQueue(LinkQuNode *&q)
{
q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
q->front=q->rear=NULL;
}释放链队占用的全部存储空间，包括链队结点和所有数据结点的存储空间。
void DestroyQueue(LinkQuNode *&q)
{
DataNode *pre=q->front,*p;
if(pre!=NULL)
{
p=pre->next;
while(p!=NULL)
{
free(pre);
pre=p;p=p->next;
}
free(pre);
}
free(q);
}bool QueueEmpty(LinkQuNode *q)
{
return(q->rear==NULL);
}创建一个新结点用于存放元素e（由p指向它）。若原队列为空，则将链表结点的两个域均指向结点p，否则将结点p链接到单链表的末尾，并让链队结点的rear域指向它。
void enQueue(LinkQuNode *&q,ElemType)
{
DataNode *p;
p=(DataNode *)malloc(sizeof(DataNode));
p->data=e;
p->next=NULL;
if(q->rear==NULL)
q->front=q->rear=p;
else
{
q->rear->next=p;
q->rear=p;
}
}若原队列为空，则下溢出返回假；若原队列不空，则将首结点的data域值赋给e，并删除之，若原队列只有一个结点，则需将链队结点的两个域均置为NULL，表示队列已为空。
bool deQueue(LinkQuNode *&q,ElemType &e)
{
DataNode *t;
if(q->rear==NULL)
return false;
t=q->front;
if(q->front==q->rear);
q->front=q->rear=NULL;
else
q->front=q->front->next;
e=t->data;
free(t);
return true;
}