数据结构 3 栈和队列

本文最后更新于：2023年12月23日晚上

根据b站王卓老师的课程记录的学习笔记📕

现在已经实现顺序栈的各种操作，

还有链栈、队列

3.1 栈和队列的定义和特点

栈和队列是两种重要的线性结构。栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

由于栈的操作具有后进先出的固有特性，使栈成为程序设计中有用的工具。另外，如果问题求解过程中具有“后进先出”的天然特性，则求解的算法中必须利用栈

数制转换表达式求值括号匹配的检验八皇后问题行编辑程序函数调用迷宫求解递归调用的实现

由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具。

脱机打印输出按申请的先后顺序依次输出

多用户系统中多个用户排成队，分时地循环使用CPU和主存

按用户的优先级排成多个队，每个优先级一个队列

实时控制系统中信号按接收的先后顺序依次处理

网络电文传输按照到达时间的先后顺序依次进行

栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。

3.1.1 栈的定义和特点

1. 栈的定义

栈(stack)：是一个特殊的线性表，是限定仅在一端（通常是表尾）进行插入或删除操作的线性表。

又称后进先出（Last In First Out）的线性表，简称LIFO结构

2. 栈的相关概念

栈是仅在表尾进行插入、删除操作的线性表

表尾 (即\(a_n\)端) 称为栈顶 Top；表头 (即\(a_1\)端) 称为栈底Base

例如：栈 s = (a, a2, a3,....., an-1, an)，a1称为栈底元素，an称为栈顶元素

插入元素到栈顶 (即表尾) 的操作，称为入栈或进栈或压栈

从栈顶 (即表尾) 删除最后一个元素的操作，称为出栈或弹栈

入 = 压入 = PUSH (x)，出 = 弹出 = POP (y)

栈的小结：

定义：限定只能在表的一端进行插入和删除操作运算的线性表（只能在栈顶操作）
逻辑结构：同线性表一样栈元素具有线性关系即前驱后继关系(一对一)
存储结构：顺序栈和链栈均可，顺序栈更常见
运算规则：只能在栈顶运算，且访问结点时依照后进先出的原则(LIFO)
实现方式：关键是编写入栈和出栈函数，具体实现依顺序栈和链栈的不同而不同

栈和线性表唯一的区别在于运算规则。线性表插入删除位置任意而栈只能对表尾(栈顶)的元素进行插入和删除操作。

3.1.2 队列的基本概念

1. 队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队头（Front）：允许删除的一端，又称队首。

队尾（Rear）：允许插入的一端。

2. 队列的相关概念

队列的总结：

定义：只能在表的一端进行插入运算在表的另一端进行删除操作运算的线性表（头删尾插）
逻辑结构：同线性表一样，仍为一对一关系
存储结构：顺序队和链队均可，以循环顺序队列更常见
运算规则：只能在队首和队尾运算，且访问结点时依照先进先出的原则（FIFO）
实现方式：关键是掌握入队和出队操作，具体实现依顺序队和链队的不同而不同

3.2 案例引入

进制转换

括号匹配的检验

表达式求值

舞伴问题

3.3 栈的表示和操作的实现

3.3.1 栈的抽象数据类型的定义

ADT Stack{
  数据对象：D = {ai|ai ∈ ElemSet, i=1,2,…n;n≥0}
  数据关系：R1 = {<ai-1,ai>|ai-1,ai∈D，i=2,…n}，约定an端为栈顶，a1端为栈底
  基本操作：初始化、入栈、出栈、取栈顶元素等
}ADT Stack

InitStack(&S) 初始化操作
操作结果: 构造一个空栈 S。
DestroyStack(&S) 销毁栈操作
初始条件: 栈 S 已存在。
操作结果: 栈 S 被销毁
StackEmpty(S) 判定S是否为空栈
初始条件: 栈 S 已存在
操作结果: 若栈 S 为空栈，则返回TRUE，否则 FALSE
StackLength(S) 求栈的长度
初始条件: 栈 S 已存在
操作结果: 返回 S 的元素个数，即栈的长度
GetTop(S, &e) 取栈顶元素
初始条件: 栈 S 已存在且非空
操作结果: 用 e 返回 S 的顶元素
ClearStack(&S) 置空操作
初始条件: 栈 S 已存在
操作结果: 将 S 清为空栈。
Push(&S, e)  入栈操作
初始条件: 栈 S 已存在
操作结果: 插入元素 e 为新的栈顶元素
Pop(&S, &e)  出栈操作
初始条件: 栈 S已存在且非空
操作结果: 删除 S的栈顶元素an，并用e 返回其值。

由于栈本身就是线性表，于是栈也有顺序栈和链栈两种实现方式

栈的顺序存储——顺序栈

栈的链式存储——链栈

3.3.2 顺序栈的表示和实现

1. 顺序栈的概述

存储方式：同一般的线性表的顺序存储结构完全相同，

利用一组地址连续的存储单元（数组）依次存放自栈底到栈顶的数据元素，栈底一般在低地址端

附设top指针，指示栈顶元素在顺序栈的位置

但是为了方便操作，通常top指针指向栈顶元素之上的下标地址，指向线性表中的\(a_{n+1}\)
另设base指针，指示栈底元素在顺序栈的位置
另外用stacksize表示栈可使用的最大容量，C语言中下标不能越界否则就有语法错误

空栈：base == top 是栈空标志

栈满：top-base==stacksize

栈满时的处理方法：

报错,返回操作系统
分配更大的空间，作为栈的存储空间,将原栈的内容移入新栈

使用数组作为顺序栈存储方式的特点：简单、方便、但易产生溢出（数组大小固定）

上溢(overflow)：栈已经满，又要压入元素

下溢(underflow)：栈已经空，还要弹出元素

注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。

2. 顺序栈的实现

#define MAXSIZE 100
typedef struct{
    SElemType *base;  //栈底指针
	SElemType *top; //栈顶指针
    int stacksize; //栈可用最大容量
}SqStack;

top和base可以定义为整型存储数组的下标或者定义为指针（指针相减的前提是两指针指向同一数组）

3. 顺序栈的初始化

//初始化栈,构造一个空栈S
Status InitStack(SqStack &S){
    S.base = new SElemType[MAXSIZE];
    //或S.base = (SElemType *)malloc(MAXSIZE*sizeof(SElemType));
    if (!S.base) exit(OVERFLOW); //存储分配失败
    S.top = S.base; //栈顶指针等于栈底指针
    S.stacksize = MAXSIZE;
    return OK;  
}

4. 判断顺序栈是否为空

//判断是否为空栈
Status StackEmpty(SqStack S){
	if (S.top==S.base)
        return TRUE;//栈为空返回TRUE
    else
        return FALSE;//栈不为空返回FALSE
}

5. 求顺序栈的长度

1
2
3

int StackLength(SqStack S){
    return S.top - S.base;
}

6. 清空、销毁顺序栈

//清空顺序栈
Status ClearStack(SqStack &S){ //这里应该加上&，不加上的话相当于没对栈进行操作
    if(S.base) S.top = S.base;
    return OK;
}

//销毁了之后空间豆释放了
//
Status DestroyStack(SqStack &S){
    if(S.base){
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
   	return OK;
}

7. 顺序栈的入栈

判断是否栈满，若满则出错（上溢）
元素e压入栈顶
栈顶指针加1

//进栈(插入新元素e)
Status Push(SqStack &S, SElemType e){
    if (S.top - S.base == S.Stacksize) return ERROR;  //栈满
    //给top所指的位置赋值
    *S.top = e;
    top++;
    
    return OK;
} 
//上面栈满之后也可以扩大栈的大小：
	S.base = (ElemType *)realloc(S.base, (S.Stacksize+STACKINCREME) *sizeof(ElemType));
    if (!S.base) exit(OVERFLOW);
    S.top = S.base + S.Stacksize;
    S.Stacksize = S.Stacksize + STACKINCREMENT;

8. 顺序栈的出栈

判断是否栈空，若空则出错（下溢）
栈顶指针减1
获取栈顶元素e

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

9. ⭐小结

以下代码是在Vscode上实现的顺序栈的操作

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

#define MAXSIZE 100

typedef int Status;
typedef int SElemType;   // ElemType的类型根据实际情况而定，这里假定为int

typedef struct {
    SElemType *base;  // 栈底指针
    SElemType *top;   // 栈顶指针
    int stacksize;    // 栈可用最大容量
} SqStack;


// 初始化栈,构造一个空栈S
Status InitStack(SqStack &S) {
    S.base = new SElemType[MAXSIZE];
    // 或S.base = (SElemType *)malloc(MAXSIZE*sizeof(SElemType));
    if (!S.base) exit(OVERFLOW); // 存储分配失败
    S.top = S.base; // 栈顶指针等于栈底指针
    S.stacksize = MAXSIZE;
    return OK;
}

// 判断是否为空栈
Status StackEmpty(SqStack S) {
    if (S.top == S.base)
        return TRUE; // 栈为空返回TRUE
    else
        return FALSE; // 栈不为空返回FALSE
}

// 获取栈的长度
int StackLength(SqStack S){
    return S.top - S.base;
}

//清空顺序栈
Status ClearStack(SqStack &S){ //这里应该加上&
    if(S.base) S.top = S.base;
    return OK;
}  

//销毁了之后空间豆释放了
Status DestroyStack(SqStack &S){
    if(S.base){
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
   	return OK;
}



//进栈(插入新元素e)
Status Push(SqStack &S, SElemType e){
    if (S.top - S.base == S.stacksize) return ERROR;  //栈满
    //给top所指的位置赋值
    *S.top = e;
    S.top++;
    
    return OK;
} 

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

// 输出栈中的内容，为空输出当前栈为空，不存在输出当前栈不存在
void PrintStack(SqStack S) {
    if (!S.base) {
        printf("当前栈不存在\n");
    } else if (StackEmpty(S)) {
        printf("当前栈为空\n");
    } else {
        printf("栈中的内容为：\n");
        SElemType *p = S.base;
        while (p != S.top) {
            printf("%d ", *p);
            p++;
        }
        printf("\n");
    }
}

// 主函数
int main() {
    SqStack S;
    printf("----初始化一个栈----\n");
    InitStack(S);
    printf("----输出栈中的内容----\n");
    PrintStack(S);

    // 入栈操作
    printf("\n----入栈操作----\n");
    int e = 1;
    Push(S, e);
    e = 2;
    Push(S, e);
    e = 3;
    Push(S, e);
    e = 8;
    Push(S, e);
    printf("----输出栈中的内容----\n");
    PrintStack(S);

    int length = StackLength(S);
    printf("栈当前的长度为：%d\n",length);


    // 出栈操作，直到栈为空
    printf("\n----出栈操作----\n");
    while (!StackEmpty(S)) {
        SElemType e2 = 0;  // 初始化e2，就是一个值来存储一下出栈的元素
        Pop(S, e2);
        printf("出栈元素：%d\n", e2);
    }
    printf("栈已为空\n");

    // int e2;
    // Pop(S,e2);
    // Pop(S,e2);
    // printf("出栈元素：%d\n", e2);
    // PrintStack(S);

    // 清空栈
    printf("\n----清空栈----\n");
    ClearStack(S);
    PrintStack(S);

    // 销毁栈
    printf("\n----销毁栈----\n");
    DestroyStack(S);
    PrintStack(S);

    return 0;
}

3.3.3 链栈的表示和实现

链栈是运算受限的单链表，只能在链表头部进行操作

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
} StackNode，*LinkStack;
LinkStack S;

链表的头指针就是栈顶
不需要头结点
基本不存在栈满的情况（内存中有空间就行）
空栈相当于头指针指向空
插入和删除仅在栈顶处执行

1. 链栈的初始化

void InitStack(LinkStack &S){
    //构造一个空栈，栈顶指针置为空
    S = NULL;
    return OK;
}

2. 判断链栈是否为空

Status StackEmpty(LinkStack S){
    if (S==NULL) return TRUE;
    else return FALSE;
}

3. 链栈的入栈

Status Push(LinkStack &S, SElemType e){
    LinkStack p;
    p = new StackNode;  //生成新结点p
    p->data = e;  //将新结点数据域置为e
    p->next = S;  //将新结点插入栈顶
    S = p;  //修改栈顶指针
    return OK;
}

4. 链栈的出栈

Status Pop (LinkStack &S,SElemType &e){
    if(S==NULL) return ERROR;
    e = S-> data;
	p = S;
	S = S-> next;
	delete p;
	return OK:
}

5. 取栈顶元素

1
2
3

SElemType GetTop(LinkStack S) {
    if (S!=NULL) return S->data;
}

3.4 栈与递归

递归的定义

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的
若一个过程直接地或间接地调用自己，则称这个过程是递归的过程

\(f(g(x))\)

3.5 队列的表示和操作实现

3.5.1 队列抽象数据类型的定义

3.5.2 队列的顺序表示和实现

1. 队列的顺序表示

队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应的，队列的存储方式也分为两种，即顺序队列和链式队列。

队列的顺序表示：用一维数组base[MAXQSIZE]

#define MAXQSIZE 100 //最大队列长度
typedef struct{
    QElemType *base;//初始化的动态分配存储空间
    int front; //头指针
    int rear; //尾指针
}SqQueue;

初始状态（队空条件）：Q.front == Q.rear == 0。

进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。

出队操作：队不空时，先取队头元素值，再将队头指针加1。

如图d，队列出现“上溢出”，然而却又不是真正的溢出，所以是一种“假溢出”。

解决假上溢的方法：

1、将队中元素依次向队头方向移动。缺点：浪费时间，每移动一次，队中元素都要移动

2、将队空间设想成一个循环的表即分配给队列的m个存储单元可以循环使用，当rear为maxqsize时，若向量的开始端空着，又可从头使用空着的空间。当front为maxqsize时，,也是一样

怎么实现呢，想到了模运算，循环实现

3.5.3 循环队列

解决假上溢的方法——引入循环队列

base[0]接在base[MAXQSIZE -1]之后，若rear+1==M，则令rear=0

实现方法：利用模(mod，C语言中: %) 运算

插入元素

1 2	`Q.base[Q.rear]=x; Q.rear=(Q.rear+1) % MAXQSIZE;`

删除元素

1 2	`x = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE;`

循环队列：循环使用为队列分配的存储空间。

队空：front==rear 队满：front==rear

解决方案：

另外设一个标志以区别队空、队满
另设一个变量，记录元素个数
少用一个元素空间（这里我们用这个

1. 循环队列的类型定义

//类型定义
#define MAXQSIZE 100

typedef struct{
    QElemType *base;  //这里是动态分配存储空间，或 QElemType base[MAXQSIZE];
    int front; // 头指针，若队列不空，指向队列头元素
    int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;
//SqQueue是普通类型，普通类型在引用成员的时候是加.，
//如果是*SqQueue，它是指针类型，引用的话是用->，  详细见下面的程序

2. 循环队列的初始化

//构造一个空队列
Status InitQueue(SqQueue &Q){
    Q.base = new QElemType[MAXQSIZE]
    // 或者用c语言的语法：Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
    if (!Q.base) exit(OVERFLOW);//存储分配失败
    Q.front = Q.rear = 0; //头指针尾指针置为0，队列为空
    return OK;
 }

//这里后面函数调用写成：、
SqQueue Q;
InitQueue(Q);

/*初始化一个空队列Q*/
Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}
//这里用的就是->

//⭐但是注意这里后面的函数调用要写成：
SqQueue Q;
InitQueue(&Q);

3. 求队列的长度

//求队列的长度
int QueueLength(SqQueue Q){
   L = (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
   return (L);
 }

左间的图：rear是5，front是0，5-0+6=11，11%6=5

中间的图：rear是0，front是4，0-4+6=2，2%6=2

右边的图：rear是3，front是4，3-4+6=5，5%6=5

4. 循环队列入队

//插入元素(入队)
Status EnQueue(SqQueue &Q, QElemType e){
    if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满
    Q.base[Q.rear] = e; //新元素加入队尾
    Q.rear = (Q.rear+1) % MAXQSIZE; //队尾指针加1
    return OK;
}

5. 循环队列出队

//删除元素(出队)
Status DeQueue(SqQueue &Q, QElemType &e){
   if (Q.front == Q.rear) return ERROR;//队空
   e = Q.base[Q.front];  //保存队头元素 
   Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
   return OK;
}

6. 取队头元素

SElemType GetHead(SqQuere Q){ //建议SElemType直接改成int
    if(Q.front!=Q.rear) //队列不为空
        return Q.base[Q.front]; //返回队头指针元素的值，队头指针不变
}

3.5.3 队列的链式表示和实现

若用户无法估计所用队列的长度，则宜采用链队列

队列的链式存储结构表示为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已。

空队列时，front和real都指向头结点。

1. 链队列的类型定义

#define MAXQSIZE 100 //最大队列长度
typedef struct Qnode {
    QElemType data;
    struct Qnode *next;
}QNode,*QuenePtr; //ptr：pointer
//QNode 表示 struct Qnode，QuenePtr 表示指向 struct Qnode 的指针。

typedef struct{
    QueuePtr front; // 队头指针
    QueuePtr rear; //队尾指针
} LinkQueue;

2. 链队列初始化

//构造一个空队列
Status InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(Qnode)); //?
    if (!Q.front) exit(OVERFLOW));
    Q.front->next=NULL;
    return OK;
}

解释一下Q.front = Q.rear = (QueuePtr)malloc(sizeof(Qnode));

这行代码的效果是创建了一个包含一个节点的链式队列，并将队列的前端和尾端指针都指向这个节点。

sizeof(Qnode)：这里使用 sizeof 运算符来获取 Qnode 结构体的大小，单位是字节。sizeof(Qnode) 返回的是 Qnode 结构体所占用的内存大小。

malloc(sizeof(Qnode))：malloc 函数用于动态分配内存。它接受一个参数，即要分配的字节数，然后返回一个指向新分配内存区域起始位置的指针。在这里，malloc(sizeof(Qnode)) 分配了足够大小的内存以容纳一个 Qnode 结构体，并返回一个指向这块内存的指针。

(QueuePtr)：这是类型转换操作符，将前面 malloc 返回的指针转换为 QueuePtr 类型。这是为了保证类型匹配，因为 malloc 返回的是 void* 类型的指针，而 QueuePtr 是指向 struct Qnode 的指针类型。

Q.front = Q.rear = (QueuePtr)malloc(sizeof(Qnode));：这行代码将刚刚分配的内存地址赋给 Q.front 和 Q.rear。这两个指针都指向同一个新分配的节点，这也表示队列目前只有这一个节点。

这个节点的 data 成员和 next 成员的值在这个时候尚未初始化。

3. 销毁链队列

算法思想：从队头结点开始，依次释放所有结点

//销毁队列Q
Status DestroyQueue(LinkQueue &Q){
    while (Q.front){
        p = Q.front->next; //或者p用Q.rear
        free(Q.front);
        Q.front = p;
    }
    return OK;
 }

4. 链队列的入队

//插入元素e为Q的队尾元素(入队)
Status EnQueue(LinkQueue &Q, QElemType e){
    p = (QueuePtr)malloc(sizeof(Qnode));
    if (!p) exit(OVERFLOW);
    p->data=e;
    p->next=NULL;
    
   	Q.rear->next = p;  //将新结点接在尾部
   	Q.rear = p;  //把当前的p设置为新的队尾结点
    return OK;
}

5. 链队列的出队

//删除Q的队头元素(出队)
Status DeQueue(LinkQueue &Q, QElemType &e){
    if (Q.front= =Q.rear) return ERROR;
   	p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    
   	if (Q.rear == P)  Q.rear=Q.front;
    
    free(P); 
   	return OK;
 }

6. 求链队列的队头元素

Status GetHead (LinkQueue Q QElemType &e){
    if(Q.front==Qrear) return ERROR;
    e = Q.front->next->data;
    return OK;
}

参考：

节点和结点有什么区别？ (baidu.com)

数据结构：栈和队列(Stack & Queue)【详解】-CSDN博客

数据结构

#数据结构

数据结构 3 栈和队列

http://viper2383.github.io/2023/12/22/数据结构 3 栈和队列/

作者

w1per3

发布于

2023年12月22日

许可协议

数据结构 4 串、数组和线性表上一篇

操作系统 3 内存管理下一篇