数据结构 | 第三、四章栈与队列

我会带着你远行 2022-10-17 05:27 397阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70]

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

### 一、栈【后进先出】 ###

#### 1、基本概念 ####

##### 1.1 概念【`LIFO`】 #####

> 首先它是一个线性表，也就是说，栈元素具有线性关系，即`前驱后继关系`。只不过它是一种特殊的线性表而已。定义中说是在线性表的`表尾进行插入和删除操作`，这里`表尾`是指`栈顶`,而不是`栈底`。

##### 1.2 特性 #####

> 它的特殊之处在于限制了这个线性表的`插入`和`删除`的位置，它仅限于插入和删除数据元素的操作在`栈顶`，另一端为`栈底`。

##### 1.3 操作 #####

> 栈的`插入`操作，叫做`进栈`，也成压栈。  
> 栈的`删除`操作，叫做`出栈`，也有的叫做弹栈，退栈。

##### 1.4 应用实例 #####

>  *  `建筑房子时砌砖`。一个一个砌上去，一个一个取下来。
>  *  `访问浏览器`。在点击页面加载，或者后退返回。

#### 2、栈的存储 ####

##### 2.1 顺序存储 #####

> 顺序栈是一个预设的足够长度的`一维数组`和一个记录栈`顶位置`的变量。

##### 2.2 栈操作 #####

>  *  `空栈`：top=-1；
>  *  `入栈`：top-1，栈顶指针指针移动至栈顶；
>  *  `出栈`：top+1，栈顶指针移动至原栈顶的下一个元素；
>  *  `满栈`：top=栈长度-1。

##### 2.3 基本操作 #####

**`main.c`**

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include "stackList.h"
    
    int main()
    { 
    	SeqStack* Stack = Init_SeqStack();
    	int i1 = 3, i2 = 6, i3 = 9, i4=10;
    	Push_SeqStack(Stack, &i1);
    	Push_SeqStack(Stack, &i2);
    	Push_SeqStack(Stack, &i3);
    	Push_SeqStack(Stack, &i4);
    
    	Display(Stack);
    	Pop_SeqStack(Stack);
    	Display(Stack);
    
    	int data = *(int *)Get_SeqStack(Stack);
    	printf("栈顶元素为：%d", data);
    
    	return 0;
    }

**`stackList.c`**

#include "stackList.h"
    
    /* 功能：初始化栈 */
    SeqStack* Init_SeqStack()
    { 
    	SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack*)*MAXLEN);
    
    	if (stack == NULL)
    		return NULL;
    
    	memset(stack, 0, sizeof(SeqStack*)*MAXLEN);
    	stack->size = -1;
    
    	return stack;
    }
    
    /* 功能：判断栈空 返回值： · NULL：该栈不存在； · 0：为空栈； · 1：不为空。 */
    int Judge_SeqStackNull(SeqStack* Stack)
    { 
    	if (Stack == NULL)
    		return NULL;
    
    	if (Stack->size == -1)
    		return 0;
    
    	return 1;
    }
    /* 功能：判断栈满 返回值： · NULL：该栈不存在； · 0：为满栈； · 1：栈不为满栈。 */
    int Judge_SeqStackFull(SeqStack* Stack)
    { 
    	if (Stack == NULL)
    		return NULL;
    
    	if (Stack->size == MAXLEN - 1)
    		return 1;
    
    	return 0;
    }
    
    /* 功能：进栈 */
    void Push_SeqStack(SeqStack* Stack, void* data)
    { 
    	if (Judge_SeqStackFull(Stack))
    	{ 
    		printf("满栈，不能进栈！");
    		return;
    	}
    	Stack->size++;
    	Stack->data[Stack->size] = data;
    
    }
    
    /* 功能：出栈 */
    void Pop_SeqStack(SeqStack* Stack)
    { 
    	if (Stack == NULL)
    		return;
    
    	if (!Judge_SeqStackNull(Stack))
    	{ 
    		printf("空栈，不能出栈！");
    		return;
    	}
    
    	Stack->data[Stack->size] = NULL;
    	Stack->size--;
    }
    
    /* 功能：去栈顶 */
    void* Get_SeqStack(SeqStack* Stack)
    { 
    
    	if (Stack == NULL)
    		return NULL;
    
    	if (Stack->size == -1)
    		return NULL;
    
    	void* x = Stack->data[Stack->size];
    	
    	return x;
    }
    
    void Display(SeqStack* Stack)
    { 
    	int i;
    	for (i = 0; i < Stack->size+1; i++)
    	{ 
    		printf("%5d", *(int *)Stack->data[i]);
    	}
    
    	printf("\n");
    }
    
    
    void Destroy_SeqStack(SeqStack *Stack)
    { 
    	if (Stack != NULL)
    	{ 
    		free(Stack);
    	}
    }

**`stack.h`**

#pragma once
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #ifdef __cplusplus
    extern "C" { 
    #endif 
    
    #define MAXLEN 1024
    
    	typedef struct SeqStack
    	{ 
    		void* data[MAXLEN];	// 存储数据
    		int size;		// 存储数据个数
    	};
    	// 初始化栈
    	SeqStack* Init_SeqStack();
    	// 判断栈空
    	int Judge_SeqStackNull(SeqStack*);
    	// 判断栈满
    	int Judge_SeqStackFull(SeqStack*);
    	// 进栈
    	void Push_SeqStack(SeqStack*, void*);
    	// 出栈
    	void Pop_SeqStack(SeqStack*);
    	// 取栈顶
    	void* Get_SeqStack(SeqStack*);
    	// 打印栈
    	void Display(SeqStack*);
    	// 销毁释放内存
    	void Destroy_SeqStack(SeqStack*);
    #ifdef __cplusplus
    }
    #endif

**运行结果**  
![在这里插入图片描述][20210602145828982.png]

#### 3、栈的链式存储 ####

##### 3.\` 基本操作 #####

**`main.c`**

#include<stdio.h>
    #include<stdlib.h>
    #include "StackLink.h"
    
    int main()
    { 
    	StackLink* stack = Init_StackLink();
    	stack = Push_StackLink(stack, 1);
    	stack = Push_StackLink(stack, 2);
    	stack = Push_StackLink(stack, 3);
    
    	printf("栈内元素为：\n");
    	Display(stack);
    	int top = Get_Top(stack);
    	printf("栈顶元素为：%d", top);
    	Distory(stack);
    
    	return 0;
    }

**`StackLink.c`**

#include "StackLink.h"
    
    
    StackLink* Init_StackLink()
    { 
    	StackLink* stack;
    	stack = NULL;
    
    	return stack;
    }
    
    // 判断栈空
    int Judge_isNull(StackLink* stack)
    { 
    	if (stack == NULL)
    		return 1;
    
    	return 0;
    }
    
    // 进栈
    StackLink* Push_StackLink(StackLink* stack, int data)
    { 
    	StackLink* temp = (StackLink*)malloc(sizeof(StackLink*));
    	temp->data = data;
    	temp->next = stack;		
    	stack = temp;		
    
    	return stack;
    }
    // 出栈
    StackLink* Pop_StackLink(StackLink* stack)
    { 
    	if (Judge_isNull(stack))
    		return NULL;
    
    	stack = stack->next;
    	
    	return stack;
    }
    //取栈顶
    int Get_Top(StackLink* stack)
    { 
    	if (Judge_isNull(stack))
    		return NULL;
    
    	int x = stack->data;
    
    	return x;
    }
    //显示函数
    void Display(StackLink* stack)
    { 
    	if (Judge_isNull(stack))
    		return ;
    
    	while (stack != NULL)
    	{ 
    		printf("%5d", stack->data);
    		stack = stack->next;
    	}
    
    	printf("\n");
    }
    // 链表销毁
    void Distory(StackLink* stack)
    { 
    	if (stack != NULL)
    	{ 
    		free(stack);
    	}
    }

**`StackLink.h`**

#pragma once
    
    #include<stdio.h>
    #include<stdlib.h>
    
    
    typedef struct LinkNode
    { 
    	int data;
    	struct LinkNode* next;
    }StackLink;
    
    #ifdef __cplusplus
    extern "C" { 
    #endif // __cplusplus
    
    	// 初始化
    	StackLink* Init_StackLink();
    	// 判断栈空
    	int Judge_isNull(StackLink*);
    	// 进栈
    	StackLink* Push_StackLink(StackLink*, int data);
    	// 出栈
    	StackLink* Pop_StackLink(StackLink*);
    	//取栈顶
    	int Get_Top(StackLink*);
    	//显示函数
    	void Display(StackLink*);
    	// 链表销毁
    	void Distory(StackLink*);
    
    #ifdef __cplusplus
    }
    #endif // __cplusplus

**运行结果**  
![在这里插入图片描述][20210602161840229.png]

#### 4、栈使用案例 ####

##### 4.1 子程序调用 #####

>  *  子程序的调用以及返回地址就是利用`堆栈`来完成；
>  *  例如C中，主函数对无参子函数的嵌套调用过程。先将返回地址保存到`堆栈`中，才去执行子程序。当执行完成后才从栈中弹出来，继续执行程序。
>  *  例如：在多层调用函数中，`主函数调用a函数`，`a调用b函数`，`b调用c函数`。即可形成`cba`，c为栈顶。即先进后出，c先执行后从栈弹出返回地址，回到b，b执行弹出返回地址，回到a…

#### 5、栈的课后练习 ####

##### 一、选择题 #####

> **1. 对于栈操作数据的原则是**  
> A. 先进先出 B.后进先出 C.后进先出 D.不分顺序

> **2. 有6个元素按6,5,4,3,2,1的顺序进栈, 问下列()不是合法的出栈序列?**  
> A.543612 B.453126 C.346521 D.234156

> **3.插入和删除只能在一端进行的线性表，称为()**  
> A.队列 B.循环队列 C.栈 D.循环栈

> **4.输入序列为ABC，可变为CBA时，经过的栈操作为()**  
> A.push,pop,push,pop,push,pop B.push,push,push,pop,pop,pop  
> C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop

> **5.没有编号为1,2,3,4 的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为()**  
> A.1234 B.1243 C.1324 D.1423

> **6.如果以链表作为栈的存储结构，则出栈操作时()。**  
> A.必须判别栈是否满  
> B.必须判别栈是否空  
> C.必须判别栈元素类型  
> D.队栈可不做任何判别

> **7.顺序栈存储空间的实现使用( )存 储栈元素。**  
> A.链表  
> B.数组  
> C.循环链表  
> D.变量

> **8.在C语言中，一个顺序栈一旦被声明，其占用空间的大小()。**  
> A.已固定  
> B.不固定  
> C.可以改变  
> D.动态变化

> 9.**从一个栈顶指针为top的链栈中删除一一个结点时， 用x保存被删除的结点，应执行下列( )命令。**  
> A. x=top;top=top->next;  
> B. top-top->next;x-top->data;  
> C. x-top->data;  
> D. x=top->data;top=top- >next;

> **10.4个元素按A,B,C,D顺序进S栈，执行两次Pop(S,x)运算后，栈顶元素的值是()**  
> A. A  
> B. B  
> C. C  
> D. D

> **11.在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列( ) 命令。**  
> A. HS->next= S;  
> B. S->next=HS->next;HS->next=S;  
> C. S->next= HS- next;HS=S;  
> D. S->next=HS;HS=HS~>next;

> **12.向顺序栈中压入元素时( )。**  
> A.先存入元素，后移动栈顶指针  
> B.先移动栈顶指针，后存入元素  
> C.谁先谁后无关紧要  
> D.同时进行

> **13. 一个栈的入栈次序ABCDE,则栈的不可能的输出序列是()。**  
> A. EDCBA  
> B. DECBA  
> C. DCEAB  
> D. ABCDE

> **14.设有一个顺序栈s,元素A.B.C,D,EF依次进栈，如果6个元素出栈的顺序是B,D,C,F.E,A,则栈的容量至少应是()**  
> A.3  
> B.4  
> C.5  
> D.6

#### 二、填空题 ####

**1.对于栈只能在\_\_\_\_下位置插入和删除元素；**  
**2.在顺序栈中，当栈项指针top=-1时，表示\_\_\_\_；**  
**3.在有n个元素的栈中，进栈操作的时间复杂度为\_\_\_\_；**  
**4.在栈中，出栈操作的时间复杂度为:\_\_\_\_；**  
**5.在一个链栈中，若栈顶指针等于NULL，则表示\_\_\_\_；**  
**6.向一个栈顶指针为top的链栈插入一一个新结点\*p时，应执行\_\_\_\_和\_\_\_\_操作；**  
**7.已知顺序栈S，在对s进行进栈操作之前首先要判断\_\_\_\_；**  
**8.已知顺序栈S，在对S进行出栈操作之前首先要判断\_\_\_\_；**  
**9. 4个元素按A,B,C,D顺序进S栈，执行两次Pop (S, X)运算后，x的值是\_\_\_\_；**

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 1]

### 二、队列【先进先出】 ###

#### 1、基本概念 ####

>  *  队列是一种特殊的`受限制`的线性表。
>  *  队列( queue )是只允许在`一端`进行`插入`操作，而在`另一端`进行`删除`操作的线性表。
>  *  队列是一种先进先出的( First In First Out )的线性表，简称`FIFO`。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=(a1，a2， … ,an )，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是a2。那么a1就是队头元素，而和是队尾元素.这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

**几种术语**

>  *  `入队`：在队尾插入操作；
>  *  `出队`：在队头删除操作；
>  *  `空队`：没有任何元素。

#### 2、存储方式 ####

##### 2.1 顺序存储 #####

> 队列中的顺序存储使用的较少。存在一个缺陷【`假溢出`】：在每次出队的时候front指针都会像前移动，导致前面被取出数据的空间造成假溢出的现象。

> 在队列中，入队 - `rear`、出队 - `front`。

##### 2.2 循环队列 #####

**`main.c`**

#include<stdio.h>
    #include<stdlib.h>
    #include "QueuList.h"
    
    int main()
    { 
    	SeqQueue* Queue = Init_SeqQueue();
    	Entry_SeqQueue(Queue, 1);
    	Entry_SeqQueue(Queue, 4);
    	Entry_SeqQueue(Queue, 5);
    	Entry_SeqQueue(Queue, 7);
    	Entry_SeqQueue(Queue, 9);
    
    	Display(Queue);
    	Delete_SeqQueue(Queue);
    	Display(Queue);
    
    
    
    	//Destroy(Queue);
    	return 0;
    }

**`CirqueueList.c`**

#include "QueuList.h"
    
    
    
    // 初始化
    SeqQueue* Init_SeqQueue()
    { 
    	SeqQueue* Queue = (SeqQueue*)malloc(sizeof(SeqQueue*)*MAXLEN);
    	Queue->front = Queue->rear = 0;
    
    	return Queue;
    }
    
    // 判断是否为空
    int Judge_isNull(SeqQueue* Queue)
    { 
    	if (Queue == NULL || Queue->front == Queue->rear)
    	{ 
    
    		return 1;
    	}
    
    	return 0;
    }
    
    // 入队
    void Entry_SeqQueue(SeqQueue* Queue, int data)
    { 
    	if (Queue == NULL || data == NULL)
    	{ 
    		return;
    	}
    
    	// 队是否满
    	if (Queue->front == (Queue->rear + 1) % MAXLEN)
    	{ 
    		printf("队满...");
    		return;
    	}
    
    	Queue->rear = Queue->rear + 1;
    	Queue->data[Queue->rear] = data;
    }
    
    // 出队
    void Delete_SeqQueue(SeqQueue* Queue)
    { 
    	if (Judge_isNull(Queue))
    	{ 
    		printf("队空...");
    		return;
    	}
    
    	Queue->front = Queue->front + 1;
    	int x = Queue->data[Queue->front];
    }
    
    // 取队头
    int Get_Head(SeqQueue* Queue)
    { 
    	if (Judge_isNull(Queue))
    	{ 
    		printf("对空...");
    		return NULL;
    	}
    
    	int x = Queue->data[Queue->front + 1];		// 取出数据
    
    	return x;
    }
    
    // 显示
    void Display(SeqQueue* Queue)
    { 
    	int temp = Queue->front;	// 用来暂存front指向，保证在循环中指向不被改变
    	if (Judge_isNull(Queue))
    	{ 
    		return;
    	}
    
    	while (temp != Queue->rear)
    	{ 
    		printf("%5d", Queue->data[temp+1]);
    		temp++;
    	}
    	printf("\n");
    }
    
    // 释放内存
    void Destroy(SeqQueue* Queue)
    { 
    	if (Queue != NULL)
    	{ 
    		free(Queue);
    		Queue = NULL;
    	}
    }

**`CirQueueList.h`**

#pragma once
    
    #include<stdio.h>
    #include<stdlib.h>
    
    /* 循环队列中的几种情况： 空队：rear = front = 0 满队：(rear+1)%MAXLEN = front */
    
    #define MAXLEN 100
    typedef struct
    { 
    	int data[MAXLEN];
    	int front;
    	int rear;
    }SeqQueue;
    
    #ifdef __cplusplus
    extern "C" { 
    #endif // __cplusplus
    	
    	// 初始化
    	SeqQueue* Init_SeqQueue();
    
    	// 判断是否为空
    	int Judge_isNull(SeqQueue*);
    
    	// 入队
    	void Entry_SeqQueue(SeqQueue*, int);
    
    	// 出队
    	void Delete_SeqQueue(SeqQueue*);
    
    	// 取队头
    	int Get_Head(SeqQueue*);
    
    	// 显示
    	void Display(SeqQueue*);
    	
    	// 释放内存
    	void Destroy(SeqQueue*);
    
    #ifdef __cplusplus
    }
    #endif // __cplusplus

**运行结果**  
![在这里插入图片描述][20210604075341941.png]

##### 2.3 链式队列 #####

**`main.c`**

#include<stdio.h>
    #include<stdlib.h>
    #include "QueueLink.h"
    
    int main()
    { 
    	QueueLink* queue = Init_QueueLink();
    	Entry_QueueLink(queue, 3);
    	Entry_QueueLink(queue, 4);
    	Entry_QueueLink(queue, 1);
    	Entry_QueueLink(queue, 7);
    	
    	printf("入队后\n:");
    	Display(queue);
    	int x = Get_Head(queue);
    	printf("队头为：%d\n", x);
    	Delete_QueueLink(queue);
    
    	printf("出队后\n:");
    	Display(queue);
    	//Distory(queue);
    	return 0;
    }

**`QueueLink.c`**

#include "QueueLink.h"
    
    // 初始化
    QueueLink* Init_QueueLink()
    { 
    	// 创建头结点
    	QueueLinkQ* head;
    	QueueLink* queue;
    	head = (QueueLinkQ*)malloc(sizeof(QueueLinkQ*));
    	queue = (QueueLink*)malloc(sizeof(QueueLink*));
    	queue->front = head;
    	queue->rear = head;
    
    	return queue;
    }
    
    // 判断对空
    int Judge_isNull(QueueLink *queue)
    { 
    	if (queue->front == queue->rear)
    	{ 
    		return 1;
    	}
    
    	return 0;
    }
    
    // 出队
    void Delete_QueueLink(QueueLink* queue)
    { 
    	if (Judge_isNull(queue))
    	{ 
    		return;
    	}
    
    	/* * 注意队头是指向队头的前一个结点 * 头结点 != 队头；头结点为队头的前一个结点 */
    	QueueLinkQ* q;	// 用来保存原来的头结点
    	q = queue->front->next;	// 取出对头结点
    	int x = q->data;		
    	queue->front->next = q->next;	// 将头结点的下一个结点指向对头的下一个结点
    }
    
    // 入队
    void Entry_QueueLink(QueueLink*queue, int data)
    { 
    	QueueLinkQ* q = (QueueLinkQ*)malloc(sizeof(QueueLinkQ*));
    	q->data = data;
    	q->next = NULL;
    	queue->rear->next = q;
    	queue->rear = q;	// 此时不是赋值，而是将队尾指针移动到队尾
    
    }
    
    // 取对头 
    int Get_Head(QueueLink* queue)
    { 
    	int x = queue->front->next->data;
    
    	return x;
    }
    
    // 显示
    void Display(QueueLink* queue)
    { 
    	if (queue == NULL)
    		return;
    	QueueLinkQ *temp = queue->front->next;
    	while (temp != NULL)
    	{ 
    		printf("%5d", temp->data);
    		temp = temp->next;
    	}
    	printf("\n");
    }
    
    // 释放空间 
    void Distory(QueueLink* queue)
    { 
    	if (queue != NULL)
    	{ 
    		free(queue);
    		queue = NULL;
    	}
    }

**`QueueLink.h`**

#pragma once
    #include<stdio.h>
    #include<stdlib.h>
    
    // 用来生成新节点
    typedef struct QueueNode
    { 
    	int data;
    	struct QueueNode* next;
    }QueueLinkQ;
    
    // 链表
    typedef struct
    { 
    	QueueLinkQ* front;
    	QueueLinkQ* rear;
    }QueueLink;
    
    #ifdef __cplusplus
    extern "C" { 
    #endif // __cplusplus
    	// 初始化
    	QueueLink* Init_QueueLink();
    
    	// 判断对空
    	int Judge_isNull(QueueLink, int);
    
    	// 出队
    	void Delete_QueueLink(QueueLink*);
    
    	// 入队
    	void Entry_QueueLink(QueueLink*, int);
    
    	// 取对头
    	int Get_Head(QueueLink*);
    
    	// 显示
    	void Display(QueueLink*);
    
    	// 释放空间 
    	void Distory(QueueLink*);
    
    
    #ifdef __cplusplus
    }
    #endif // __cplusplus

**运行结果**  
![在这里插入图片描述][20210604101932833.png]

#### 3、队列的应用举例 ####

##### 3.1 对CPU的分配管理 #####

> 在系统中，多个`进程`满足运行条件，即可用队列来管理。若需要运行该进程，则插入队列。等待运行。

##### 3.2 队列的数据管理应用 #####

> 可设定一个`队列缓冲区`用来缓冲数据，将数据切块添加到该缓冲区，可保证数据的次序。

##### 3.3 队列的优先级 #####

> 任务队列的优先级，可根据`权值大小`来定。通过权值来确定谁先入队，从而进行操作。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70]: /images/20221014/36b3e9881c5a4c8287ce1ae3aaaed5fb.png
[20210602145828982.png]: /images/20221014/bdac7017a398444a8532dc8d6141253a.png
[20210602161840229.png]: /images/20221014/16dd634673f04bd7912815175547ccab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 1]: /images/20221014/8a0d288c4bac49b4bbf0fed4ff70689a.png
[20210604075341941.png]: /images/20221014/94414722c4434a149fd8f587791efb02.png
[20210604101932833.png]: /images/20221014/efde1976734d4ca9b6d1257aaacb757e.png