数据结构第三章栈和队列

Myth丶恋晨 2022-06-18 12:09 212阅读 0赞

**数据结构笔记链接：**

[第一章 绪论][Link 1]

[第二章 线性表][Link 2]

[第三章 栈和队列][Link 3]

[第四章 串][Link 4]

[第五章 数组和广义表][Link 5]

[第六章 树和二叉树][Link 6]

[第七章 图][Link 7]

[第八章 排序][Link 8]

[第九章 查找][Link 9]

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

*   *   *  3.1 栈
            
             *  3.1.1 栈的定义
             *  3.1.2 栈的顺序实现
                
                 *  3.1.2.1 结构定义
                 *  3.1.2.2 基本操作
                 *  3.1.2.3 两栈共享技术
             *  3.1.3 栈的链式实现
                
                 *  3.1.3.1 结构定义
                 *  3.1.3.2 基本操作
         *  3.2 队列
            
             *  3.2.1 队列的概念
             *  3.2.2 顺序队列
                
                 *  3.2.2.1 结构定义
                 *  3.2.2.2 假溢出
             *  3.2.3 链式队列
                
                 *  3.2.3.1 结构定义
                 *  3.2.3.2 基本操作
             *  3.2.4 循环队列
                
                 *  3.2.4.1 判断栈满
                 *  3.2.4.2 基本操作
         *  3.3 栈和队列的应用
            
             *  3.3.1 递归函数
             *  3.3.2 算法表达式求值
             *  3.3.3 括号匹配
             *  3.3.4 回文串判断
         *  3.4 例题
            
             *  3.4.1 例1
             *  3.4.2 例2
             *  3.4.3 例3
             *  3.4.4 例4
             *  3.4.5 例5
             *  3.4.6 例6

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

### 3.1 栈 ###

#### 3.1.1 栈的定义 ####

`栈`作为一种限定性线性表，是只允许在**同一端**进行**插入**和**删除**操作的线性表。

`栈顶`：通常将表中允许进行**插入**、**删除**操作的一端称为栈顶 (Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。

`栈底`：同时表的另一端被称为栈底 (Bottom)。

`空栈`：当栈中没有元素。

`满栈`：无法申请到栈区可用空间。

`上溢`：栈已满仍要入栈。

`下溢`：栈已空仍要出栈。

栈的插入操作被形象地称为`进栈`或`入栈`，删除操作称为`出栈`或`退栈`。具有**先进后出**（FILO）或**后进先出**（LIFO）的特点。

![栈的示意图][20171006190749123]

#### 3.1.2 栈的顺序实现 ####

##### 3.1.2.1 结构定义 #####

用一组**连续**的存储单元依次存放**自栈底到栈顶**的数据元素。设一个**位置指针top**（栈顶指针）动态指示栈顶元素在顺序栈中的位置，当`top=-1`时，表示空栈。

typedef int datatype;  
    # define MAXSIZE 100
    typedef struct{    
        datatype  data[MAXSIZE];
        int top; 
        } seqstack; 
    seqstack *s;

##### 3.1.2.2 基本操作 #####

（1）判断栈空

int EMPTY(seqstack *s) {
        return (!s–>top>=0);
    }

（2）置空栈

void SETNULL(seqstack *s) {
        s–>top=-1;
    }

（3）判断栈满

int FULL(seqstack  *s) {
        return (s–>top==MAXSIZE-1);
    }

（4）进栈

seqstack * PUSH(seqstack  *s，datatype x) {
        if (FULL(s)){ 
            printf(“stack overflow”); 
            return NULL; 
        }
        s–>top++; 
        s–>data[s–>top]=x; return s; }

（5）出栈

datatype POP(seqstack *s) {
        if (EMPTY(s)) { 
            printf(“stack underflow”);
            return NULL;
        }
        s–>top--; 
        return(s–>data[s–>top+1]);
    }

（6）取栈顶

datatype TOP(seqstack  *s) {
        if (EMPTY(s)) { 
            printf(“stack is empty”);
            return NULL;
        }
        return (s–>data[s–>top]);
    }

##### 3.1.2.3 两栈共享技术 #####

栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况。若使用顺序栈，会因为对栈空间大小难以准确估计，从而产生有的栈溢出、有的栈空间还很空闲的情况。

为了解决这个问题，可以让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使 其存储空间互相补充，这就是`多栈共享技术`。

在顺序栈的共享技术中最常用的是两个栈的共享技术即`双端栈`：它主要利用了“**栈底位置不变，而栈顶位置动态变化**”的特性。

首先为两个栈申请一个共享的一维数组空间`S[M]`， 将两个栈的栈底分别放在一维数组的两端，分别是 `0`，`M-1`。由于两个栈顶动态变化，这样 可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。

由此可见，两栈共享要比两个栈分别申请`M/2`的空间利用率要高。

两栈共享的数据结构定义如下：

#define M 100 
    typedef struct { 
        StackElementType Stack[M];   
        StackElementType  top[2]; /*top[0]和 top[1]分别为两个栈顶指示器*/
    }DqStack;

两个栈共享空间的示意如下图所示:

![双端栈][20171006211212933]

若栈1的底在v\[1\]，栈2的底在V\[N\]，则栈满的条件是`top[1]+1==top[2]`。

（1）初始化操作：

void InitStack(DqStack *S) {
        S->top[0]=-1; 
        S->top[1]=M; 
    }

（2）进栈操作：

int Push(DqStack *S, StackElementType x, int i) {
        /*把数据元素 x 压入 i 号堆栈*/  
        if(S->top[0]+1==S->top[1]) /*栈已满*/
               return(FALSE);  
        switch(i)  {  
            case 0:  
                S->top[0]++;
                S->Stack[S->top[0]]=x; 
                break;  
            case 1:   
                S->top[1]--;
                S->Stack[S->top[1]]=x;
                break;    
            default:
                /*参数错误*/             
                return(FALSE)   
        }  return(TRUE); 
    }

（3）出栈操作：

int Pop(DqStack *S, StackElementType *x, int i) {
        /* 从 i 号堆栈中弹出栈顶元素并送到 x 中 */  
        switch(i)  {
            case 0:
                if(S->top[0]==-1)
                    return(FALSE);
                *x=S->Stack[S->top[0]];
                S->top[0]--;
                break;
            case 1:
                if(S->top[1]==M)
                    return(FALSE);    
                *x=S->Stack[S->top[1]];
                S->top[1]++;
                break;
            default:
                return(FALSE);
        }
        return(TRUE);
    }

#### 3.1.3 栈的链式实现 ####

`链栈`即采用**链表**作为存储结构实现的栈。为便于操作，这里采用**带头结点的单链表**实现栈。

由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针，如下图所示：

![链栈][20171006212450653]

在上图中，`top`为栈顶指针，始终指向当前栈顶元素前面的头结点,它唯一地确定一个链栈。若`top->next=NULL`，则代表栈空,该链栈为**空栈**。

链栈中的结点是动态产生的，**无需考虑上溢问题**。

采用链栈时，栈的各种基本操作的实现与单链表的操作类似，对于链栈，在使用完毕时，应该**释放其空间**。

##### 3.1.3.1 结构定义 #####

typedef  int datatype;
    typedef struct node{    
        datatype  data;
        struct node * next;
        }linkstack;
    linkstack * top;

##### 3.1.3.2 基本操作 #####

（1）进栈

linkstack *PUSHLSTACK(linkstack *top, datatype x) { 
        linkstack *p;
        p＝(linkstack *)malloc(sizeof(linkstack));
        p->data＝x; 
        p->next＝top;
        return p;  //返回新栈顶指针
    }

（2）出栈

linkstack *POPLSTACK(linkstack *top, datatype *datap) { 
        linkstack *p;
        if (top==NULL) { 
            printf(“under flow”);
        }
        datap＝top->data; /*栈顶结点数据存入*datap */
         p=top;
         top＝ top->next;
         free(p);
        return top;  //返回新栈顶指针
     }

### 3.2 队列 ###

#### 3.2.1 队列的概念 ####

队列(Queue)也是一种**运算受限**的线性表。只允许在表的一端进行**插入**，而在另一端进行**删除**。允许删除的一端称为**队头**(front)，允许插入的一端称为**队尾**(rear)。具有**先进先出**（FIFO）的特点。

#### 3.2.2 顺序队列 ####

队列的一种顺序存储称为`顺序队列`。与顺序栈类似，在队列的顺序存储结构中，用一组 地址连续的存储单元依次存放从队头到队尾的元素，如一维数组`data[MAXSIZE]`。 由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针`front`和`rear`。

*  front:指示队头元素在数组中的位置
 *  rear:指示真实队尾元素相邻的下一个位置

##### 3.2.2.1 结构定义 #####

#define MAXSIZE 100
    typedef  struct{
        datatype data[MAXSIZE];
        int front;
        int rear;
    }sequeue;
    sequeue * sq;

##### 3.2.2.2 假溢出 #####

初始化队列时，令`front = rear =0`；入队时，直接将新元素送入尾指针`rear`所指的单元， 然后尾指针增1；出队时，直接取出队头指针`front`所指的元素，然后头指针增1。

显然，在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。当`rear==MAXSIZE`时，认为队满。

但此时不一定是真的队满，因为随着部分元 素的出队，数组前面会出现一些空单元，如下图(d)所示。由于只能在队尾入队，致使被删除元素的空间永远无法重新利用。

把这种现象称为`假溢出`，真正队满的条件是`rear - front=MAXSIZE`。

![假溢出][20171011192453568]

#### 3.2.3 链式队列 ####

##### 3.2.3.1 结构定义 #####

typedef struct queuenode{
        datatype  data;
        struct queuenode  *next;
    }QueueNode;
    
    typedef struct{
        QueueNode  *front;
        QueueNode  *rear;
    }LinkQueue;

##### 3.2.3.2 基本操作 #####

（1）置空

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

（2）判断队空

int QueueEmpty(LinkQueue  *Q) {
        return (Q.front->next= =NULL &&Q.rear->next= =NULL);
    }

（3）入队

void EnQueue(LinkQueue  *Q, datatype x){    
        QueueNode *p;
        p=(QueueNode * )malloc(sizeof(QueueNode));
        p–>data=x;
        p–>next=NULL;
        Q->rear–>next=p;
        Q->rear=p;
    }

（4）出队

DeQueue(linkqueue *Q) {
        linkqueue  *p;
        datatype x;
        if (EMPTY(Q))    
            return NULL;
        p = Q->front->next;      
        Q->front->next = p–>next;
        if (p->next==NULL) 
            Q->rear = Q->front;  
        x = p->data;
        free(p);
        return x;
    }

#### 3.2.4 循环队列 ####

为了解决假溢出问题，引入了`循环队列`的概念。在循环队列中进行**出队**、**入队**操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向**向量上界( MaxSize-1 )**时，其加1操作的结果是指向**向量的下界0**。

##### 3.2.4.1 判断栈满 #####

入队时：尾指针向前追赶头指针，出队时：头指针向前追赶尾指针，故队空和队满时头尾指针均相等，无法通过`sq->front == sq->rear`来判断队列“空”还是“满”。  
解决此问题的方法至少有两种：

*  另设一个布尔变量以区别队列的空和满；
 *  少用一个元素空间为代价，入队前，测试尾指针 **sq-> rear+1==sq->front ，若相等则认为队满**。

##### 3.2.4.2 基本操作 #####

**队空判断**： `sq->front == sq-> rear`

**队满判断**： `sq-> front ==(sq-> rear + 1) % maxSize`

**入队**： `sq-> rear = (sq-> rear + 1) % maxSize`

**出队**： `sq-> front = (sq-> front + 1) % maxSize`

**求队长**： `(sq-> rear - sq-> front+maxSize)%maxSize`

（1）入队

*  检查队列是否已满，若队满，则进行溢出错误处理。
 *  将队尾指针后移一个位置（即加1），指向下一单元。
 *  将新元素赋给队尾指针所指单元。

Status EnQueue (SqQueue *Q, ElemType  e){    
        if ( (Q->rear+1)%MAXQSIZE == Q->front )  
            return(ERROR);   //队满上溢
        Q->rear=(Q->rear+1)%MAXQSIZE;
        Q->data[Q->rear]=e;
        return(True);   
    }

（2）出队

*  检查队列是否为空，若队空，则进行下溢错误处理。
 *  将队首指针后移一个位置（即加1）。
 *  取队首元素的值。

Status DeQueue (SqQueue *Q) { 
        if (Q->rear== Q->front)  
            return(NULL);  //队空下溢
        Q->front=(Q->front+1)%MAXQSIZE;
        return(Q->data[Q->front]);
    }

（3）置空队

Q->front=Q->rear= MAXQSIZE-1;

（4）取队头

datatype  GetHead(SqQueue *Q ) { 
        if (Q->front==Q->rear)  
            return(NULL);  //队空
        return (Q->data[(Q->front+1)%MAXQSIZE] );
    }

（5）判断队空

int QueueEmpty(SqQueue *Q ){
        if (Q->front==Q->rear) 
            return (True);
        else 
            return (False);  
    }

### 3.3 栈和队列的应用 ###

#### 3.3.1 递归函数 ####

递归函数又称为自调用函数，它的特点：在函数内部可以直接或间接地调用函数自己。

C语言描述如下：

int  FACT(int n) { 
        if (n==1) 
            return (1);
         else
            return (n*FACT(n-1));
    }

#### 3.3.2 算法表达式求值 ####

计算机系统在处理表达式前，先设置两个栈：操作数栈(OPRD)：存放处理表达式过程中的操作数；运算符栈(OPTR)：存放处理表达式过程中的运算符。开始时，在运算符栈中先在栈底压入一个表达式的结束符“\#”。

（1）中缀表示法  
计算机系统在处理表达式时，从左到右依次读出表达式中的各个符号（操作数或运算符），每读出一个符号ch后，根据运算规则做如下处理：

*  如果ch是操作数，则将其压入操作数栈OPRD，并依次读取下一个符号。
 *  若ch是运算符，则：  
    若读出的运算符的优先级大于OPTR栈顶的运算符优先级，则将其压入OPTR，并依次读下一个符号。  
    若读出的是“\#”，且OPTR栈顶的运算符也是“\#”，则表达式处理结束，最后的计算结果在OPRD的栈顶位置。
 *  若读出的是“（”，则将其压入OPTR。
 *  若读出的是“）”，则：若OPTR栈顶不是“(”，则从OPRD连续退出两个操作数，从OPTR中退出一个运算符，然后作相应的运算，并将运算结果压入OPRD，然后返回a)，让ch继续与OPTR栈顶元素进行比较。  
    若OPTR栈顶为“(”，则从OPTR退出“(”，依次读下一个符号。
 *  若读出的运算符的优先级小于OPTR栈顶运算符的优先级，则从OPRD连续退出两个操作数，从OPTR中退出一个运算符，然后作相应的运算，将运算结果压入OPRD 。返回(2)继续OPTR栈顶元素进行比较。

（2）波兰表示法和逆波兰表示法

以5 + ( 6 – 4 / 2 ) \* 3为例：

波兰表示法：+ 5 * - 6 / 4 2 3  
    
    逆波兰表示法：5 6 4 2 / - 3 * +。

运算时按从左到右的顺序进行，不需要括号。在计算表达式时，可设置一个栈，从左到右扫描后缀表达式，每读到一个操作数就将其压入栈中；每读到一个运算符时，则从栈顶取出两个操作数运算，并将结果压入栈中，一直到后缀表达式读完。最后栈顶就是计算结果。

#### 3.3.3 括号匹配 ####

#include<stdio.h>
    #define maxsize 100
    typedef int datatype;
    
    typedef struct{
        datatype data[maxsize];
        datatype top;
    }seqstack;
    seqstack *s;
    
    void build();
    void push();
    void pop();
    int check(char ss[]);
    
    void main(){
        char ss[maxsize];
        build();
        printf("请输入要测试的算数表达式:");
        scanf("%s",ss);
        if(check(ss)==-1)
            printf("算数表达式不匹配!");
        else
            printf("算数表达式匹配!");
    }
    
    void build(){
        s=(seqstack*)malloc(sizeof(seqstack));
        s->top=-1;
    }
    int check(char ss[]){
        int i=0;
        while(ss[i] != '\0'){
            i++;
            if(ss[i] == '(')
                push();
            else if(ss[i] == ')')
                pop();
        }
        return s->top;
    }
    
    void push(){
        s->top++;
    }
    void pop(){
        s->top--;
    }

#### 3.3.4 回文串判断 ####

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define maxsize 100
    
    typedef struct {
        char data[maxsize];
        int top;
    } stack;
    
    typedef struct {
        char data[maxsize];
        int front;
        int rear;
    } queue;
    
    int isempty_queue(queue * stq){
        return stq->front == stq->rear;
    }
    
    int isfull_queue(queue *stq){
        return stq->rear >= maxsize -1 ;
    }
    
    queue * init_queue(){
        queue * tmp = (queue*) malloc(sizeof(queue));
        tmp->front = tmp->rear = 0;
        return tmp;
    }
    
    char dequeue(queue * stq){
        if( isempty_queue(stq) ) {
            printf("队列为空，无法出队\n");
            exit(0);
        }
        return stq->data[stq->front++];
    }
    
    void inqueue(queue *stq, char value) {
        if( isfull_queue(stq) ) {
            printf("队列已满，无法入队\n");
            exit(0);
        }
        stq->data[stq->rear++] = value;
    }
    
    stack * init_stack(){
        stack * tmp = (stack *) malloc( sizeof(stack) );
        tmp->top = 0;
        return tmp;
    }
    
    int isempty_stack(stack *stk) {
        return stk->top == 0 ? 1 : 0;
    }
    
    int isfull_stack(stack *stk) {
        return stk->top >= maxsize -1 ? 1: 0;
    }
    
    char pop(stack *stk) {
        if( isempty_stack(stk) ) {
            printf("堆栈为空，无法出栈\n");
            exit(0);
        }
        return stk->data[--stk->top];
    }
    
    void push(stack *stk, char value) {
        if( isfull_stack(stk) ) {
            printf("堆栈已满，无法入栈\n");
            exit(0);
        }
        stk->data[stk->top++] = value;
    }
    
    void compare(stack * stk, queue *stq, char str[], int len) {
        int i;
        int flag = 0;
        char temp_stack;
        char temp_queue;
    
        for(i = 0; i < len; i++){
            push(stk, str[i]);
            inqueue(stq, str[i]);
        }
    
        for(i = 0; i < len; i++){
            temp_stack = pop(stk);
            temp_queue = dequeue(stq);
    
            if(temp_stack != temp_queue) {
                printf("不是回文串\n");
                flag = 1;
                break;
            }
        }
    
        if( !flag )
            printf("是回文串\n");
    }
    
    int main(){
        queue * stq = init_queue();
        stack * stk = init_stack();
    
        char c[maxsize],s;
        int i=0;
        printf("请输入字符序列，以@结束\n");
        scanf("%c",&s);
        while(s!='@'){
            c[i]=s;
            scanf("%c",&s);
            i++;
        }
        c[i]='\0';
        compare(stk, stq, c, strlen(c)-1);
    
        return 0;
    }

### 3.4 例题 ###

#### 3.4.1 例1 ####

栈和队列是特殊的线性表，其特殊性体现在？为什么要引入循环队列？

> 和普通线性表相比，对插入、删除运算加以限制。一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，为了解决这种问题，就要引入循环队列。

#### 3.4.2 例2 ####

设一个栈的入栈序列为A、B、C、D，则可能的出栈序列有哪些？

> 共计14种，分别是：ABCD、ACBD、ACDB、ABDC、ADCB、BACD、BADC、BCAD、BCDA、BDCA、CBAD、CBDA、CDBA、DCBA。

#### 3.4.3 例3 ####

有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（C第一个出栈且D第二个出栈）的次序有哪几种？

> 共计3种，分别是：CDEBA、CDBEA、CDBAE。

#### 3.4.4 例4 ####

判定一个顺序栈ST（元素个数最多为StackSize）为空/满的条件是【 】。

> 空：ST->top=0，满：ST->top=MAXSIZE-1。

#### 3.4.5 例5 ####

判定一个循环队列Q（存放元素位置：0至QueueSize-1）队满的条件是【 】。

> sq-> front ==(sq-> rear + 1) % maxSize。

#### 3.4.6 例6 ####

若用一个大小为6的数组来实现环形队列，且当前rear和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是【 】和【 】。

> 2 ; 4

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

[Link 1]: http://blog.csdn.net/yuanlaijike/article/details/69442950
[Link 2]: http://blog.csdn.net/yuanlaijike/article/details/69451381
[Link 3]: http://blog.csdn.net/yuanlaijike/article/details/69472125
[Link 4]: http://blog.csdn.net/yuanlaijike/article/details/69480358
[Link 5]: http://blog.csdn.net/yuanlaijike/article/details/69486729
[Link 6]: http://blog.csdn.net/yuanlaijike/article/details/78070403
[Link 7]: http://blog.csdn.net/yuanlaijike/article/details/78074765
[Link 8]: http://blog.csdn.net/yuanlaijike/article/details/78078434
[Link 9]: http://blog.csdn.net/yuanlaijike/article/details/78078788
[20171006190749123]: /images/20220618/6060a984f93b4e44952d237393b1bc6d.png
[20171006211212933]: /images/20220618/528ffb2fc1034a0297ebc0e90a6bd2ec.png
[20171006212450653]: /images/20220618/07d83edd39ba4f74b68f5cea30ac314e.png
[20171011192453568]: /images/20220618/ee7fa8b6ca5644cf94c95ec3c16b5053.png