数据结构 第三章 栈和队列

3.1栈的顺序存储结构顺序栈的实现共享栈 栈的链式存储结构习题3.1 3.2队列的顺序存储结构队列的顺序存储循环队列 队列的链式存储结构队列的链式存储链式队列的基本操作 双端队列习题3.2 3.3栈和队列的应用栈在括号匹配中的应用栈在表达式求值中的应用栈在递归中的应用队列在层次遍历中的应用队列在计算机系统中的应用 习题3.3 3.4数组的存储结构矩阵的存储压缩对称矩阵三角矩阵三对角矩阵 稀疏矩阵

3.1

栈的顺序存储结构

顺序栈的实现

顺序存储

# define MaxSize 50 typedef struct{ Elemtype data[MaxSize]; int top; //栈顶指针 }SqStack;

栈顶指针：S.top，初始时设置S.top=-1； 栈顶元素：S.data[S.top]； 进栈操作：栈不满时，栈顶指针先加1，再赋值到栈顶元素； 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1； 栈空条件：S.top==-1； 栈满条件：S.top==MaxSize-1； 栈长：S.top+1

初始化

void InitStack(SqStack &S){ S.top=-1; }

判断栈空

bool StackEmpty(SqStack S){ return S.top==-1 }

进栈

bool Push(SqStack &S, ElemType x){ if(S.top==MaxSize-1) return false; S.data[++S.top]=x; return true; }

出栈

bool Pop(SqStack &S, ElemType &x){ if(S.top==-1) return false; x=S.data[S.top--] return true; }

读栈顶元素

bool GetTop(SqStack S, ElemType &x){ if(S.top==-1) return false; x=S.data[S.top]; return true; }

共享栈

栈底位置相对不变，两个顺序栈共享一个一维数组，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间中间延伸。 top0=-1 0号栈为空；top1=MaxSize 1号栈为空 当top1-top0=1时，栈满。 0号栈进栈，top0先+1后赋值；1号栈进栈，top1先-1再赋值。

栈的链式存储结构

定义

typedef struct Linknode{ ElemType data; struct Linknode *next; }*LiStack;

习题3.1

CDEBA CDBEA CDBAE

BCAED可，其操作为A进、B进、C进、C出、B出、D进、E进、E出、D出、A出 DBACE不可，因为D最先出，说明栈内已经有ABC，则B和A不可能在C前出。

1）A、C、D合法 2）

int judge(ElemType A, int n){ int count = 0; for(int i=0;i<n;i++){ if(A[i]=='I') count++; else count--; if(count < 0) return 0; } return 1; }

int dc(LinkList L, int n){ int i; char s[n/2]; p=L->next; for(i=0;i<n/2;i++){ s[i]=p->data; p=p->next; } i--; //恢复最后的i值 if(n%2==1) p=p->next; while(p!=NULL&&s[i]==p->data){ i--; p=p->next; } if(i==-1) return 1; else return 0; }

入栈

int push(int i, elemtp x){ if(i<0||i>1){ printf("栈号输入不对"); exit(0); } if(s.top[1]-s.top[0]==1){ printf("栈已满\n"); return 0; } switch(i){ case 0: s.stack[++s.top[0]]=x; return 1; break; case 1: s.stack[--s.top[1]]=x; return 1; } }

出栈

int pop(int i, elemtp x){ if(i<0||i>1){ printf("栈号输入不对"); exit(0); } switch(i){ case 0: if(s.top[0]==-1){ printf("0栈空\n"); return -1; } else return s.stack[s.top[0]--]; break; case 1: if(s.top[1]==maxsize){ printf("1栈空\n"); return -1; } else return s.stack[s.top[1]++] } }

3.2

队列的顺序存储结构

队列的顺序存储

队列的顺序实现：分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置。

#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int front, rear; }SqQueue;

初始状态（队空条件）：Q.frontQ.rear0； 进队操作：队不满时，先送值到队尾元素，再将队尾指针+1； 出队操作：队不空时，先取队头元素，再将队头指针+1；

单纯的队列会导致假溢出，明明有存储空间，但因为指针指向队尾，无法再向队列中存放元素

循环队列

初始状态：Q.frontQ.rear0； 队首指针进1：Q.front=(Q.front+1)%MaxSize； 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize； 队列长度：（Q.rear+MaxSize-Q.front)%MaxSize 出队入队时：指针都按顺时针方向进1 由于队空和队满有三种处理方式：

牺牲一个单元来区分队空和队满，入队时少用一个队列单元，约定以“队头指针在队尾指针的下一位置作为队满的标志”， 队满条件：(Q.rear+1)%MaxSizeQ.front 队空条件：Q.frontQ.rear 队列中元素的个数：(Q.rear-Q.front+MaxSize) %MaxSize类型中增设一个元素个数。这样队空条件为Q.size0；队满的条件为Q.sizeMaxSize.（都可能出现Q.front==Q.rear）类型中增设tag，区分队满队空，tag=0时，若因删除导致Q.frontQ.rear，则为队空；tag=1时，若因插入导致Q.frontQ.rear，则为队满。

初始化

void InitQueue(SqQueue &Q){ Q.rear=Q.front=0; }

判断队空

bool isEmpty(SqQueue Q){ if(Q.rear=Q.front) return true; else return false; }

入队

bool EnQueue(SqQueue &Q, ElemType x){ if((Q.rear+1)%MaxSize==Q.front) return false; Q.data[Q.rear]=x' Q.rear=(Q.rear+1)%MaxSize }

出队

bool DeQueue(SqQueue &Q, ElemType &x){ if(Q.rear==Q.front) return false; x=Q.data[front]; Q.front=(Q.front+1)%MaxSize; return true; }

队列的链式存储结构

队列的链式存储

队列的链式表示是一个同时带有队头指针和队尾指针的单链表。

typedef struct{ ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ LinkNode *front, *rear; }LinkQueue;

当Q.frontNULL&&Q.rearNULL时，链式队列为空。

单链表的链式队列表示适合于数据元素变动比较大的情形，且不存在列满溢出的情况。

链式队列的基本操作

初始化

void InitQueue(LinkQueue &Q){ Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL; }

判队空

bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false; }

入队

void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL; Q.rear->next=s; Q.rear=s; }

出队

bool DeQueue(LinkQueue &Q, ElemType &x){ //带头结点的单链表队列 if(Q.front==Q.rear) return false; LinkNode *p=Q.front->next; x=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return true; }

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列。将队列的两段分别称为前端和后端。 **输出受限的双端队列：**允许在一段进行插入和删除，但在另一端只允许插入的双端队列。

**输入受限的双端队列：**允许在一端进行插入和删除，但在另一端只允许删除的双端队列。若限定从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相接的栈。

习题3.2

入队

int EnQueue(SqQueue &Q, ElemType x){ if(Q.rear==Q.front&&tag==1) return 0; Q.data[Q.rear]=x; Q.rear =(Q.rear+1)%MaxSize; if(Q.rear==Q.front) Q.tag=1; return 1; }

出队

int DeQueue(SqQueue &Q, ElemType &x){ if(Q.rear==Q.front&&tag==0) return 0; x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; if(Q.rear==Q.front) Q.tag==0; return 1; }

每次将队列的Top压入S，全部压入后，再依次弹出S，进入队列。

void Reverse(SqQueue &Q, Stack &S){ while(!QueueEmpty(Q)){ x=DeQueue(Q); Push(S,x); } while(!StackEmpty(S)){ Pop(S,x); EnQueue(Q,x); } }

S1用来入队，S2用来出队。 入队 1）若S1不满，则直接压入S1； 2）若S1满且S2不空，则返回（无法入栈，因为这样会破坏输出顺序） 3）若S1满且S2空，则将S1的所有东西都压入S2，新数据再压入S1

void EnQueue(Stack &S1, Stack &S2, ElemType x){ if(!StackOverflow(S1)){ //判断是否栈满，否则直接压入S1 Push(S1, e); return 1; } if(StackOverflow(S1&&!StackEmpty(S2)){ return 0; //队满 } if(StackOverflow(S1)&&StackEmpty(S2)){ while(!StackEmpty(S1)){ Pop(S1,x); Push(S2,x); } Push(S1,e); return 1; } }

出队 1）若S2不空，则将S2全部出队。 2）若S2空，则将S1压入S2再出队

void DeQueue(Stack &S1, Stack &S, ElemType &x){ if(!StackEmpty(S2)){ Pop(S2,x); } else if(StackEmpty(S1)){ printf("队列为空"); } else{ while(!StackEmpty(S1)){ Pop(S1,x); Push(S2,x); } Pop(S2,x); } }

判空

int QueueEmpty(Stack S1, Stack S2){ if(StackEmpty(S1)&&StackEmpty(S2)) return 1; else return 0; }

1）②顺序无法开辟新空间；③出队后结点不释放，用队头指针指向新队头结点，入队直接赋值在尾后第一个空结点，尾指针指向新队尾，需要一个首尾相接的循环单链表。 2）牺牲一个单元来判断队空或队满。初始时，创建只有一个空闲结点的循环单链表，头指针和尾指针均指向空闲结点。 队空：frontrear 队满：frontrear->next

3） 4） 入队

若(front==rear->next) //队满 则在rear后插一个新建的空闲结点； 入队元素保存到rear所指的结点中； rear=rear->next;

出队

若(front==rear) 则出队失败，返回； 取front所指结点的元素赋值到x； front=front->next; 返回x；

3.3

栈和队列的应用

栈在括号匹配中的应用

算法思想： 1）初始设置一个空栈，顺序读入括号。 2）若是右括号，则或者是与栈顶相符左括号匹配；或者括号序列不合法，退出程序。 3）若是左括号，则压入栈。算法结束时，栈为空，否则括号序列不匹配。

栈在表达式求值中的应用

中缀表达式：我们平时使用的表达式，依赖运算符的优先级，需要括号处理。 后缀表达式：运算符在操作数后，已考虑了运算符的优先级，没有括号。

后缀表达式计算值 1）顺序扫描表达式的每一项 2）若该项是操作数，则压入栈中； 3）若是操作符，则连续从栈中弹出两个操作数$X$和$Y$，进行$X<op>Y$，并将结果重新压入栈； 4）当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。

中缀表达式转后缀表达式 1）从左向右扫描中缀表达式，遇到数字，直接输出（加入后缀表达式） 2）遇到运算符： a）若为’(’，入栈； b）若为’)’，则依次把栈中运算符加入后缀表达式，直到出现’(’，删除’(’； c）若为其他运算符，则优先级高于’(‘的直接入栈，否则从栈顶开始，依次弹出比当前处理的运算符优先级高和相等的运算符，直到第一个比它优先级低或遇到一个’(’后入栈顶。

栈在递归中的应用

递归模型必须满足以下两个条件：

递归表达式（递归体）边界条件（递归出口） 递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。 其效率不高的原因是递归过程中包含很多重复计算，优点是代码简单，容易理解。 递归算法可转换为非递归算法，通常需要借助栈来实现这种转换。

队列在层次遍历中的应用

二叉树层次遍历 1）根节点入队。 2）若队空（即所有结点都处理完毕），则结束遍历；否则重复（3） 3）队列中的第一个结点出队，并访问。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回（2）。

队列在计算机系统中的应用

解决主机与外部设备之间速度不匹配问题 主机与打印机之间速度不匹配： 主机输出数据速度比打印机打印数据速度快得多，因此需要设置一个打印缓冲区，主机把要打印输出的数据依次写入该缓冲区，写满后暂停输出，转去做其他事。打印机从缓冲区按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。

解决由多用户引起的资源竞争问题 CPU资源竞争： 多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，分别通过各自的中断向操作系统提出占用CPU的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列。每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU分配给新队首用户使用。

习题3.3

int bracket(char* str){ int i=0; Stack S; char p; InitStack(S); //这边漏了 while(str[i]!="\0"){ if(str[i] == '{' || str[i] == '(' || str[i] == '[') S.push(str[i]）; else{ S.GetTop(p); switch(s[i]){ case '}': if(p == '{') S.pop(); else return 0; case ')': if(p == '(') S.pop(); else return 0; case ']': if(p == '[') S.pop(); else return 0; } } } if(IsEmpty(S)) return 1; else return 0; }

void SFHL(int n, char *str){ int i; Stack S; for(i=0;i<n;i++){ if(str[i]=='H') S.push(str[i]); else printf("%c", s[i]); } while(!IsEmpty(S)){ S.pop(); } }

答案

void Train_Arrange(char *train){ char *p=train, *q=train, c; stack s; InitStack(s); while(*p){ if(*p=='H'){ Push(s, *p); //若是H压栈，p指针直接向后移动 } else *(q++)=*p; //若是S，把S移到当前S之后的第一个位置，然后 p++; } while(!StackEmpty(s)){ Pop(s,c); *(q++)=c; } }

答案 设置一个栈用于保存$n$和对应的$P_n(x)$值，栈中相邻元素的$P_n(x)$有题中关系。然后边出栈边计算$P_n(x)$，栈空后该值就算出来了。

double p(int n, double x){ struct stack{ int no; double val; }st[MaxSize]; int top=-1, i; //top为栈st的下标值变量 double fv1=1, fv2=2*x; //n=0,n=1时的初值 for(i=n;i>=2;i--){ top++; st[top].no=i; } while(top>=0){ st[top].val=2*xfv2-2*(st[top].no-1)fv1; fv1=fv2; fv2=st[top].val; top--; } if(n==0){ return fv1; } return fv2; }

答案

Queue q; //渡口 Queue q1; //客车 Queue q2; //货车 void manager(){ int i=0,j=0; //j表示渡船上车数 while(j<10){ if(!QueueEmpty(q1)&&i<4){ //客车不为空，则上四辆车 DeQueue(q1,x); EnQueue(q,x); i++; j++; } else if(i==4 && !QueueEmpty(q2)){ //客车上完4辆，货车上一辆 DeQueue(q2,x); EnQueue(q,x); j++; i=0 } else{ while(j<10&&i<4&&!QueueEmpty(q2)){ //客车队空且客车不足4辆 DeQueue(q2,x); EnQueue(q,x); i++; j++; } i=0; } if(QueueEmpty(q1)&&QueueEmpty(q2)) //货车和客车均已出队 j=11; } }

3.4

数组的存储结构

一维数组$A[0...n-1]$为例，其存储结构关系式为$LOC(a_i)=LOC(a_0)+i\times L(0\le i\le n)$，其中$L$是每个数组元素所占的存储单元。

多维数组有两种映射方法：按行优先和按列有限。 按行优先的二维数组存储结构关系式$LOC(a_{i,j})=LOC(a_{0,0}+[i\times (h_2+1)+j]\times L)$，其中$h_2$是列下标的范围。 按列优先的二维数组存储结构关系式$LOC(a_{i,j})=LOC(a_{0,0}+[i\times (h_1+1)+j]\times L)$，其中$h_1$是行下标的范围。

矩阵的存储压缩

存储压缩：多个值相同的元素只分配一个存储空间，零元素不分配存储空间。 特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见有对称矩阵，上下三角矩阵，对角矩阵等。

对称矩阵

定义：n阶方阵 $a_{i,j}=a_{j,i}$ 特殊存储方法：将对称矩阵$A[1...n][1...n]$存放在一维数组$B[n(n+1/2)]中$，即$a_{i,j}$存放在$b_k$中，其中$k=1+2+\dots +(i-1)+j-1=i(i-1)/2+j-1(i\ge j)$，$k=1+2+\dots +(i-1)+j-1=j(j-1)/2+i-1(i<j)$。

三角矩阵

下三角矩阵$A[1...n][1...n]$存放在一维数组$B[n(n+1/2)+1]中$，其下标对应关系为$k=1+2+\dots +(i-1)+j-1=i(i-1)/2+j-1(i\ge j)$,$k=n(n+1)/2(i<j)$

上三角矩阵$A[1...n][1...n]$存放在一维数组$B[n(n+1/2)+1]中$，下标对应关系为

$k=n(n+1)/2(i\ge j)$，$k=1+2+\dots +(i-1)+j-1=j(j-1)/2+i-1(i<j)$。

三对角矩阵

对角矩阵也称带状矩阵。 对于n阶方阵A中的任一元素$a_{i,j}$，当$|i-j|>1时$，有$a_{i,j}=0$，则成为三对角矩阵。 特殊存储方法：将3条对角线上的元素按行优先方式存储在一维数组B中，且$a_{1,1}$存放于$B[0]$中，下标对应关系为$k=2i+j-3$。 若已知三对角线矩阵中某元素$a_{i,j}$存放于一维数组B的第$k$个位置，则可得$i=\lfloor (k+1)/3+1\rfloor ,j=k-2i+3$，

稀疏矩阵

将非零元素及其行和列构成一个三元组（行标，列标，值），但压缩存储后便失去了随机存取特性。