devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 | 第三、四章 栈与队列_栈的运算特点是后进先出,元素a

作者：不正经 | 2024-05-01 01:29:20

赞

踩

栈的运算特点是后进先出,元素a

在这里插入图片描述

一、栈【后进先出】

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

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

  • 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
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122

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 


  • 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

运行结果
在这里插入图片描述

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

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

  • 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

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


  • 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

运行结果
在这里插入图片描述

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的值是____；

在这里插入图片描述

二、队列【先进先出】

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

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

  • 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
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

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


  • 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

运行结果
在这里插入图片描述

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

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

  • 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

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


  • 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

运行结果
在这里插入图片描述

3、队列的应用举例
3.1 对CPU的分配管理

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

3.2 队列的数据管理应用

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

3.3 队列的优先级

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/516298
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号