备案控制台
开发者社区 开发与运维 文章 正文

数据结构 第三章 栈和队列

2022-11-22 106
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构 第三章 栈和队列

栈

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

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

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

空栈：当栈中没有元素。

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

上溢：栈已满仍要入栈。

下溢：栈已空仍要出栈。

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

栈的顺序实现

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

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

基本操作

（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]);
}

两栈共享技术

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

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

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

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

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

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

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

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

若栈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);
}

栈的链式实现

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

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

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

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

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

结构定义

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

基本操作

（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;  //返回新栈顶指针
 }

队列

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

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

front:指示队头元素在数组中的位置

rear:指示真实队尾元素相邻的下一个位置

结构定义

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

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

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

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

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

链式队列

结构定义

typedef struct queuenode{
    datatype  data;
    struct queuenode  *next;
}QueueNode;

typedef struct{
    QueueNode  *front;
    QueueNode  *rear;
}LinkQueue;

基本操作
（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;
}

循环队列

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

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

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

少用一个元素空间为代价，入队前，测试尾指针 sq-> rear+1==sq->front ，若相等则认为队满。

基本操作
队空判断： 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);  
}

栈和队列的应用

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

C语言描述如下：

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

算法表达式求值

计算机系统在处理表达式前，先设置两个栈：操作数栈(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 * +。

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

括号匹配

#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--;
}

回文串判断

#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;
}

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

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

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

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

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

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

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

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

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

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

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

2 ; 4

文章标签：
云数据库 ClickHouse
C语言
算法
存储
关键词：
数据结构栈
数据结构队列
数据结构栈队列
数据结构栈和队列
TwcatL_tree
目录
相关文章
热爱嵌入式的小佳同学
|
1天前
|
存储 NoSQL C语言
数据结构——顺序栈与链式栈的实现-2
数据结构——顺序栈与链式栈的实现
热爱嵌入式的小佳同学
15 1
数据结构——顺序栈与链式栈的实现-2
热爱嵌入式的小佳同学
|
1天前
|
存储 C语言
数据结构——顺序栈与链式栈的实现-1
数据结构——顺序栈与链式栈的实现
热爱嵌入式的小佳同学
17 0
数据结构——顺序栈与链式栈的实现-1
toKeep
|
1天前
栈的基本应用
栈的基本应用
toKeep
12 3
toKeep
|
1天前
栈与队列理解
栈与队列理解
toKeep
13 1
Bigcrab__
|
1天前
|
存储 算法
数据结构与算法 栈与队列
数据结构与算法 栈与队列
Bigcrab__
12 0
数据结构与算法 栈与队列
天玑y
|
1天前
|
C++
数据结构（顺序队列 循环队列
数据结构（顺序队列 循环队列
天玑y
10 0
天玑y
|
1天前
|
C++
数据结构（共享栈
数据结构（共享栈
天玑y
8 0
天玑y
|
1天前
|
C++
数据结构（顺序栈
数据结构（顺序栈
天玑y
13 2
叫我龙翔
|
1天前
|
容器
【栈与队列】栈与队列的相互转换OJ题
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
叫我龙翔
10 0
闻缺陷则喜何志丹
|
1天前
|
机器学习/深度学习 算法 测试技术
【单调栈】3113. 边界元素是最大值的子数组数目
【单调栈】3113. 边界元素是最大值的子数组数目
闻缺陷则喜何志丹
16 0