• 【408考研】数据结构 —— 第三章 栈、队列

    数据结构(第三章 :栈、队列)

    文章目录

    栈

    • 栈（Stack）是只允许一端进行插入或删除操作的线性表。

      • 栈顶（Top）：进行插入或删除操作的一端

      • 栈底（Bottom）：固定，不允许进行插入或删除的另一端

      • 空栈：即不含任何元素的空表

    • 栈的操作特性：后进先出（Last In First Out）

    Tips ：

    ​ 栈的数学特性: n n n个不同元素进栈，出栈元素的排列顺序不同个数为 1 n + 1 C 2 n n \frac{1}{n+1}C_{2n}^{n} n+11​C2nn​ ，也称为卡特兰（Catalan）数。

    基本操作

    • 初始化一个空栈 ： InitStack(&S)

    • 判栈内是否为空 : StackEmpty(S)

    • 进栈 : Push(&S,x)

    • 出栈 : Pop(&S,&x)

    • 读栈顶元素 : GetTop(S,&x)

    • 销毁栈 : DestroyStack(&S)

    存储结构

    因为栈本质就是一种操作受限的线性表, 所以它类似于线性表, 也有两种存储方式

    顺序存储

    • 顺序存储的栈——也称为顺序栈

      • 利用一组地址连续的存储单元存放从栈底到栈顶的数据元素,同时设置一个“指针”(top)指向当前的栈顶元素。

      • 顺序栈的空间是固定的，有满栈的风险

      • 用C语言来描述存储类型：

        #define MaxSize 100     //定义栈中元素最大个数
typedef struct{
    ElemType data[MaxSize];    //存放栈中元素
    int top;   //栈顶”指针“，这个不是指针型变量， 就一普通整型变量，主要用于记录数组下标的位置，即栈顶元素在数组中的位置
}SqStack;

        • 1
        • 2
        • 3
        • 4
        • 5

        请添加图片描述

        请添加图片描述

    • 顺序栈的实现

      • 栈顶指针：S.top,
        • 初始化栈时：S.top=-1;
        • 栈为空时：S.top==-1;
        • 栈顶元素： S.data[S.top];
      • 进栈操作：栈不满时，先栈顶指针加1，再送值到栈顶元素。
      • 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。

    顺序栈

    入栈过程：

    请添加图片描述

    出栈过程：

    请添加图片描述

    代码实现：

    1. 初始化顺序栈

      void InitStack(SqStack &S){
    S.top=-1;     //初始化栈顶"指针", 即赋值-1表示栈内为空
}

      • 1
      • 2
      • 3

    2. 判断栈是否为空

      bool StackEmpty(SqStack S){
    if(S.top==-1){
        return true;   //栈空
    }else{
        return false;   //栈不空
    }
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7

    tips : 传入函数的变量，什么时候用&，什么时候不用&?

    ​ 运算符&是地址运算符，在C/C++语言中是用于取变量地址的；&变量：获得变量的地址，它的操作数必须是变量。当要修改变量内容时，需要使用&符号才能进行修改，只是读变量的值时不需要使用&符号。

    1. 进栈

      bool Push(SqStack &S, ElemType x){
    if(S.top == Maxsize-1){
        return false;    //栈满, 报错
    }else{
    	S.data[++S.top]=x;   //指针先加1, 再入栈
    }
    return true;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8

    2. 出栈

      bool Pop(SqStack &S, ElemType &x){
    if(S.top == -1){
        return false;   //判断栈内是否为空
    }else{
        x = S.data[S.top--];  //将栈顶元素出栈, 再将栈顶指针减1
    }
    return true;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8

    3. 读栈顶元素

      bool GetTop(SqStack S, ElemType &x){
    if(S.top == -1){
        return false;  //判断栈内是否有元素
    }else{
        x = S.data[S.top];  //读出栈顶元素
    }
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7

    注意 : n++和++n的区别，n++是先使用n的数值再自加一；++n是先自加一后再使用n累加后的数值。

    即运算符放变量前面，先运算再使用；运算符放变量后面，先使用再运算。

    例如 :

    S.data[++S.top]=x;

    等价于

    S.top = S.top+1;

    S.data[S.top]=x;

    • 共享栈——两个顺序栈共用一个一维数组空间
      • 两个栈的栈底分别放数组两端
      • 请添加图片描述

    链式存储

    • 链式存储的栈也叫链栈

    • 不存在栈满上溢的问题，空间没有固定

    • 通常使用单链表实现，所有操作在链表的表头进行（一般没有和单链表那样的头结点，这样可以方便在表头进行进栈或出栈操作）

    • 请添加图片描述

    • 栈的链式存储类型

      typedef struct Linknode{    //一个名为Linknode的结构体
    ElemType data;     //数据域
    struct Linknode *next;   //指针域, 指向给结点的指针
} *ListStack   //链栈结点

      • 1
      • 2
      • 3
      • 4

    队列

    • 队列（Queue）—— 一种操作受限制的线性表
      • 只允许在表的一端进行插入（入队）， 另一端进行删除（出队）
      • 特点 ： 先进先出（First In First Out）
      • 请添加图片描述

    常见操作

    • InitQueue(&Q); 初始化队列，构造一个空队列（初始化）
    • QueueEmpty(Q); 判断队列是否为空
    • EnQueue(&Q,x); 入队操作 （增）
    • DeQueue(&Q,&x); 出队操作 （删）
    • GetHead(Q,&x); 读队头元素 （查）

    既然是受限的线性表， 那必然有一部分线性表的特性， 比如也有顺序存储和链式存储。但不能读取栈或者队列中间的元素。

    队列的顺序存储

    • 队列类型描述

      #define MaxSize 100
typedef struct{
    ElemType data[MaxSize]; //存放队列元素   
    int front, rear;     //队头"指针"和队尾"指针"
}SqQueue;

      • 1
      • 2
      • 3
      • 4
      • 5

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

    • 进队：队不满时，将值往队尾放，队尾指针加1 Q.rear+1

    • 出队：队不空时，将队首的值出队，队头指针加1 Q.front+1

    • 注意 ： 队尾指针可以有两种方式定义，一种是每次都指向队尾元素，另一种是每次指向队尾元素的下一个位置（两种方式定义的代码操作上会有区别）。而队头只指向队首元素。下面普遍采用队尾指针指向队尾元素的下一个位置

    因为顺序队列是从一端进另一端出，但出队后，后面的元素并没有往队头前面的空位移动， 这就会让队尾的元素越堆越多，最后Q.rear==MaxSize并不能作为队满的条件，因为出队后空出来的位置并没有存放元素。而出队时队头指针只会向后移动指向出队元素的后一个元素，入队时队尾指针也只能往后移动。

    请添加图片描述

    • 因此顺序队列存在“假溢出”，即队中还有多余空间，但却无法入队。
    循环队列

    循环队列能解决顺序队列的“假溢出”问题。

    • 循环队列只是将顺序队列变为逻辑上的“环”

    • 解决了顺序队列的“假溢出”问题

    • 在代码层面上使用取余运算符%来实现“循环”

      Q.front = Q.rear = 0;  //初始时, 队空
Q.front = (Q.front+1)%MaxSize; //队首指针向后移一位
Q.rear = (Q.rear+1)%MaxSize;  //队尾指针向后移一位
length = (Q.rear+MaxSize-Q.front)%MaxSize; //队列长度

      • 1
      • 2
      • 3
      • 4

      tips : why Q.rear+MaxSize-Q.front?

      因为在循环队列中Q.front有可能会在Q.rear的后面，那么在数值上做减法就有负值产生。而队列的长度必须要保证为非负整数，此时加上整个数组的长度再去取余就能保证结果为非负整数。

    计算机统考408试题刷题版
    pdf 0星 超过10%的资源 14.31MB
    下载

    请添加图片描述

    怎么区分队空还是队满？

    因为队满和队空都有一个特点就是Q.font == Q.rear, 因此要区分哪个是队满还是队空?

    三种处理方法 ：

    1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元

    ​ 当队头指针在队尾指针下一个位置时作为队满标志

    ​ 请添加图片描述

    2. 类型中增设表示元素个数的数据成员 Q.size, 通过计数方式：即入队Q.size加1；出队Q.size减1。

    队空 : Q.size == 0

    队满 : Q.size == MaxSize

    typedef struct{
    ElemType data[MaxSize]; //存放队列元素   
    int front, rear;     //队头"指针"和队尾"指针"
    int size; // 表示队中的元素个数
}SqQueue;

    • 1
    • 2
    • 3
    • 4
    • 5

    3. 类型中增加tag数据成员，用来区分队空还是队满

    typedef struct{
    ElemType data[MaxSize]; //存放队列元素   
    int front, rear;     //队头"指针"和队尾"指针"
    int tag; // 取值为0或1, 用标签来标识队满和队空,也可用bool类型来标识
}SqQueue;

    • 1
    • 2
    • 3
    • 4
    • 5

    • 队空：只有一种操作才会使队空——出队（删除）

      • 因此每次出队时将Q.tag 设置为 0

    • 队满：只有一种操作才会使队满——入队（插入/增加）

      • 因此每次入队时将Q.tag 设置为 1

    • 若有Q.rear == Q.front，则仅需判断Q.tag

      • if Q.tag == 0, 则队空
      • if Q.tag == 1, 则队满
    循环队列的操作
    //初始化
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;  //队尾加一后取余
    return true;
}
  
//出队
bool DeQueue(SqQueue &Q,ElemType &x){
    if (Q.rear == Q.front) 
        return false;   //队空则报错
    x = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize; //队头指针加一后取余
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    通常取模运算也叫取余运算，它们返回结果都是余数

    初始化、出队、入队都需要修改队列，因此传入的队列要用&地址符

    福州大学863考研初试资料
    zip 0星 超过10%的资源 168.94MB
    下载
    • 写个简单的循环队列的C语言程序:
    #include 
#define MaxSize 10   //数组最大容量 

typedef struct{
	int data[MaxSize];
	int front, rear; 
}SqQueue;

void InitQueue(SqQueue &Q);  //初始化 
bool isEmpty(SqQueue Q);   // 判空 
bool EnQueue(SqQueue &Q, int x);  //入队 
bool DeQueue(SqQueue &Q,int &x);  //出队 

int main(){
	
	SqQueue Q; //声明一个队列
	InitQueue(Q); //初始化队列
	printf("队列初始化成功。队首指针:%d;队尾指针:%d\n",Q.front,Q.rear); 	
	bool iE = isEmpty(Q); //判断队列是否为空 
	printf("此时队列是否为空? %d\n",iE); 
	int i=0;
	
	while(i!=-1){
		printf("入队请输入0, 出队请输入1,退出输入-1:"); 
		scanf("%d",&i); 
		if(i == 0){
			int x;
			printf("请输入入队元素值:");
			scanf("%d",&x); 
			EnQueue(Q,x);
		} else if (i==1){ 
			int x;
			int de = DeQueue(Q,x);
			if (de == false){
				printf("无出队元素\n"); 
			} else{ 
			printf("出队元素为%d\n",x); 
			} 
		} 
	}
	
	if(isEmpty(Q)) {
		printf("队中无元素\n"); 
	}else{
		//输出队中元素, 从队首到队尾依次读出, 仅读出队中元素, 这里只是为了展示队中的元素 
		//此做法不符合队列的规则, 正常情况下只能读到队头元素, 要想读完队里的元素就要逐个出队, 就和栈一样, 中间元素是不能直接读的。 
		int b = Q.front; 
		while(Q.rear!=b%MaxSize) {
			printf("%d ",Q.data[b]); 
			b=(b+1)%MaxSize; 
		}
	} 
	return 0;
}

//初始化队列 
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, int x){
	if ((Q.rear+1)%MaxSize==Q.front){
		return false;       //舍弃一个单位空间来判断队满 
	} 
	Q.data[Q.rear] = x;
	Q.rear=(Q.rear+1)%MaxSize;  //队尾加一后取余
    return true; 
} 

//出队
bool DeQueue(SqQueue &Q,int &x){
    if (Q.rear == Q.front) 
        return false;   //队空
    x = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize; //队头指针加一后取余
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87

    请添加图片描述

    队列的链式存储

    • 队列的链式存储——链队列
    • 操作受限制的线性表的链式存储
    • 头指针和尾指针才是真正的指针， 与顺序存储不一样

    请添加图片描述

    注意 ： 循环队列只有顺序存储， 它的存在只是解决顺序存储中空间没有占满的问题。而队列的链式存储就不存在这个问题，循环队列默认就是顺序存储。

    • 链式存储的类型

      typedef struct LinkNode{
    ElemType data;    //数据域
    struct LinkNode *next;  //指针域: 指向LinkNode结构体的指针
}LinkNode;  //链式队列的结点

typedef struct{
    LinkNode *front, *rear;  //指向队列结点的队首和队尾指针
}LinkQueue;  //链式队列, 包括队头和队尾指针

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8

      • 当 Q.front == NULL 且 Q.rear==NULL 时，链式队列为空

      • 出队：先判断队是否为空，若不空，则取出队头元素，将其从链表中删除， 并让头指针指向下一个结点

      • 入队：先建立一个新结点， 再将新结点插入到链表尾部， 并让尾指针指向新插入的结点

      • 没有带头结点的队列，在出队为空之后， 需要都将头指针和尾指针置空。但若带头结点，队为空时，头指针和尾指针都指向一个结点（即头结点），此时的队中只有一个元素出队时， 不需要同时置空头尾指针， 仅需将尾指针指向头结点即可。

        请添加图片描述

        ps：头指针仅需指向头结点即可， 因为头结点的指针域会指向队首元素，因此出队仅需改变头结点的指针域即可。

    • 基本操作

      1. 初始化

        void InitDueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode)); //建立头结点， 需要分配头结点的空间
    Q.front->next = NULL; //初始为空
}

        • 1
        • 2
        • 3
        • 4

      2. 判断队是否为空

        bool IsEmpty(LinkQueue Q){
    if (Q.front == Q,rear)  //带头结点的链队列
        return true;  //为空返回true
    else
        return false;
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6

      3. 入队

        void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));  //分配新的结点空间,并将s指针指向该空间
    s->data = x; // 数据域赋值, 即新增结点的数据
    s->next = NULL;  //因为入队操作都是在队尾进行操作, 所以该结点的指针域置空
    Q.rear->next = s; //先将最后结点的指针域指向新入队的结点
    Q.rear = s; //最后将尾指针指向该新结点即可完成入队
}

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7

        请添加图片描述

      4. 出队

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

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 8
        • 9
        • 10
        • 11

        请添加图片描述

        请添加图片描述

        注 : 在入队和出队的操作中需要注意的是结点空间分配以及结点空间释放的问题。

        入队需要新的结点插入，因此需要分配新的结点空间；而出队需要将旧的结点删除，此时需要释放原来分配的结点空间。

        小tips ： 声明指针是不需要使用malloc函数来分配空间的。而LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); 的意思是先声明一个指向LinkNode结点的指针，而后面的操作是(LinkNode *)malloc(sizeof(LinkNode))分配一个LinkNode大小的空间，然后转换成LinkNode *指针类型；本质就是把刚分配的空间地址给到s指针。

    双端队列

    • 双端队列——是指允许两端都可以进行入队和出队操作的队列
    • 逻辑结构是线性结构
    • 双端队列的队头称为前端，双端队列的队尾称为后端
    • 分三种双端队列
      • 第一种 ： 两端都可以进行出队和入队操作
      • 第二种 ： 输出受限的双端队列（有一端只能输入）
      • 第三种 ： 输入受限的双端队列 （有一端只能输出）

    请添加图片描述

    请添加图片描述

    主页 点赞 收藏 评论

    未完待续….

    参考资料 ：

    1. 23版王道408数据结构单科书
    2. 王道考点精讲视频课件
  • 相关阅读:
    Pytorch 自己搭建的一个神经网络
    有什么视频转文字软件？快把这些方法收好
    4-7再谈方法之重载
    八月份记录
    安卓Termux搭建web服务器【公网远程手机Android服务器】
    找出字符串中第一个匹配项的下标
    C++面试常见问题 — C++语言基础
    three.js学习-智慧城市
    STM32F4XX - 系统定时器（SysTick）设置
    spring boot 分布式session实现
  • 原文地址：https://blog.csdn.net/honorzoey/article/details/126338593