数据结构（三）——栈和队列

一、栈和队列的定义和特点

栈：受约束的线性表，只允许栈顶元素入栈和出栈

对栈来说，表尾端称为栈顶，表头端称为栈底，不含元素的空表称为空栈

先进后出，后进先出

队列：受约束的线性表，只允许在队尾插入，在队头删除

先进先出，后进后出

二、栈的表示和操作的实现

1.顺序栈的表示：存储结构

#define MAXSIZE 100  //顺序栈存储空间的初始分配址
typedef struct{SElemType *base;  //栈底指针SElemType *top;  //栈顶指针int stacksize;  //栈可用的最大容址
}SqStack;

top指栈顶元素的后一个位置，栈空时top指向的索引定义为-1

S.top = = 0 时，栈空 

S.top == stacksize 时，栈满

2.顺序栈的操作

a.初始化

//初始化
Status InitStack(SqStack &S){//构造一个空栈SS.base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));if(!S.base) exit(OVERFLOW);  //存储分配失败，退出程序S.top = S.base;S.stacksize = MAXSIZE;return OK;
}

b.入栈

当 index = arr.length 时，用户要入栈，给用户抛出“栈已满”的异常（上图最右边的情况）

//入栈
Status Push(SqStack &S,SElemType e){//插入元素e为新的栈顶元素if(S.top - S.base >= S.stacksize) {  //栈满//追加存储空间S.base = (SElemType*)realloc(S.base,(S.stacksize+MAXSIZE) * sizeof(SElemType));if(!S.base){  //存储分配失败exit(OVERFLOW)  //退出程序}S.top = S.base + S.stacksize;S.stacksize += MAXSIZE;}*S.top ++ = e;return OK;
}

c.出栈

如果 index = 0 的时候，用户要弹栈，给用户抛出“栈为空”的异常（上图最右边的情况）

//出栈
Status Pop(SqStack &S,SElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top == S.base){  //栈为空return ERROR;}e = * --S.top;return OK;
}

d.顺序取栈顶元素

//顺序取栈顶元素
Status GetTop(SqStack S,SElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top == S.base){  //栈为空e = *(S.top - 1);  //top指向下面的位置即栈顶，然后指向e，即赋值给ereturn OK;}
}

三、循环队列的表示和操作的实现

1.循环队列的表示

在循环队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针 front 和 rear 分别指示队列头元素及队列尾元素的位置

初始化建立空队列时，令 front = rear = 0, 每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置

我们发现，在队列满时和空队列时，头指针和尾指针都指向同一个元素，那么如何分辨队列满和空队列？

1、少用一个元素空间， 即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，良D当头、尾指针的值相同时， 则认为队空;而当尾指针在循环意义上加1后是等于头指针，则认为队满。队空的条件:Q.front ==Q.rear
队满的条件:(Q.rear+ 1)%MAXQSIZE == Q.front
入队:Q.rear=(Q.rear +1)% MAXQSIZE
出队:Q.front=(Q.front +1)% MAXQSIZE

当前元素个数:(Q.rear-Q.front+MAXQSIZE)% MAXQSIZE

如上图所示，当J7、J8、J9 进入队列后，(Q.rear+ 1)%MAXQSIZE 的值等于 Q.front，此时认为队满。

2、另设一个标志位以区别队列是“空”还是“满"

2.循环队列的操作

（1）定义存储结构

#define MAXSIZE 100 
typedef struct{QElemType *base;  //初始化的动态分配存储空间int front;  //头指针，若队列不空，指向队列头元素int rear;  //尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

（2）初始化

//初始化
Status InitQueue(SqQueue &Q) {//构造一个空队列QQ.base = (QElemType *)malloc(MAXSIZE * sizeof(QElemType));if(!Q.base){exit(OVERFLOW);}Q.front = Q.rear = 0;return OK;
}

(3)求元素个数

//求元素个数
int QueueLength(SqQueue Q){//返回Q的元素个数return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

（4）插入新元素

//插入新元素
Status EnQueue(SqQueue &Q,QElemType e){//插入元素e为Q的新的队尾元素//判断队列是否为空if((Q.rear + 1) % MAXSIZE == Q.front){return ERROR;}Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXSIZE;return OK;
}

（5）删除元素

//删除元素
Status DeQueue(SqQueue %Q,QElemType &e){//若队列不空，则删除Q的对头元素，用e返回其值，并返回OK；否则返回ERRORif(Q.front == Q.rear){return ERROR;}e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXSIZE;return OK;
}

四、总结与习题

栈是限定仅在表尾进行插入或删除的线性表，又称为后进先出的线性表。栈有两种存储表示，顺序表示(顺序栈)和链式表示（链栈)。栈的主要操作是进栈和出栈，对于顺序栈的进栈和出栈操作要注意判栈满或栈空。

队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。队列也有两种存储表示顺序表示(循环队列)和链式表示(链队)

栈和队列的逻辑结构都和线性表一样，数据元素之间存在一对一的关系。

循环队列中少用一个元素判断队空或队满时：

队空的条件:：Q.front == Q.rear

队满的条件：(Q.rear+1)%MAXQSIZE == Q.front

答案：C

答案：C

解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…,n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，….pi=n-i+1

答案：D

解释:对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE(本题为n)，然后与MAXSIZE(本题为n)求余，即(n+r-f)%n

答案：B （方法同第一题）

元素出队序列默认就是元素的入队序列

答案：C

解释:初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V[1...n]中，所以进栈时top指针先下移变为n，之后将元素x存储在V[n]

答案：A

解释:x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。

答案：D

解释:一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。

答案：D

解释:数组A[0...m]中共含有m+1个元素，故在求模运算时应除以m+1

答案：B

答案：C