HelloWorld
登录

栈和队列

似梦清欢

2022-11-30

1404 1 0
栈原理

栈（stack）又名堆栈，是一种只能在表尾进行插入和删除操作的线性表。能够进行操作的这一端被称为栈顶，相对地，把另一端称为栈底。 ::: warning 栈内元素操作时先进后出，类似于电梯上下成员，最后进去的人最先出来。 ::: image 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 image 如上图，top代表栈顶，栈S是一个结构体。S.top=-1时栈为空，当入栈第一个元素时，S.data[++S.top]=1，S.top前置++后数组下标变为0，依次向下可以入栈后面的元素。 image 上图中x表示要出栈的值（栈顶的那个值），S.data[S.top]=4，出栈后元素下标-1，变为S.top- -，下次要出栈的值变为3，即S.data[S.top- -]=3。 image S.top是数组的下标，最大值为maxsize-1。

初始化栈及入栈出栈
1#include <stdio.h>
2#include <stdlib.h>
3#define MaxSize 50
4typedef int Elemtype;
5typedef struct
6{
7	Elemtype data[MaxSize];
8	int top;  //始终指向栈顶的变量
9}SqStack;
10
11//初始化栈
12void InitStack(SqStack& S)
13{
14	S.top = -1;  //使得栈为空即为初始化栈，栈空即为S.top = -1
15}
16
17//判断栈是否为空
18bool StackEmpty(SqStack S)
19{
20	if (-1 == S.top)  //定义指针时候才可以使用->
21	{
22		return true;
23	}
24	else
25	{
26		return false;
27	}
28}
29
30//入栈
31bool Push(SqStack& S, Elemtype x)  
32{
33	if (S.top == MaxSize - 1)  //栈满
34	{
35		return false;
36	}
37	S.data[++S.top] = x;
38	return true;
39}
40
41//获取栈顶元素
42bool GetTop(SqStack S, Elemtype &x)  //x需要引用&，原因是要对x赋值传递出去
43{
44	if (-1 == S.top)  //栈不能为空
45	{
46		return false;
47	}
48	/*或者使用嵌套调用如下：
49	if (StackEmpty(S))
50	{
51		return false;
52	}*/
53	x = S.data[S.top];  //拿到栈顶元素
54	return true;
55}
56
57//弹栈（即出栈）
58bool Pop(SqStack &S, Elemtype &x)
59{
60	if (StackEmpty(S))  //栈不能为空
61	{
62		return false;
63	}
64	x = S.data[S.top];  //拿到栈顶元素
65	x = S.data[S.top--];  //元素出栈
66	return true;
67}
68
69int main()
70{
71	SqStack S;  //定义一个栈
72	InitStack(S);
73	bool flag;
74	flag = StackEmpty(S);  //判断栈是否为空
75	if (flag)
76	{
77		printf("stack is empty\n");
78	}
79
80	Push(S, 3);  //入栈元素3
81	Push(S, 4);  //入栈元素4
82	Push(S, 5);  //入栈元素5
83	Elemtype m;
84	flag = GetTop(S, m);  //获取栈顶元素
85	if (flag)
86	{
87		printf("get top element %d\n", m);  //打印栈顶元素
88	}
89	flag = Pop(S, m);  //弹出栈顶元素
90	if (flag)
91	{
92		printf("pop element %d\n", m);  //打印弹出元素
93	}
94	return 0;
95}
1stack is empty
2get top element 5
3pop element 5

image 弹栈的作用是将S.top- -，上述代码中S.top指向4，即数组下标为1的位置，下次再有入栈的元素会覆盖掉数组下标为2的元素5。 image ::: warning 弹栈不改变栈元素，只是改变了栈顶指针S.top指向的位置。 :::

队列原理

FIFO：全称First in, First out，先进先出。 队列简称队，只允许在表的一端进行插入，另一端进行删除。队列中插入元素称为入队（进队），删除元素称为出队（离队）。 image

数组实现循环队列

image 循环队列可以使用数组或链表实现，这里使用数组。 image 如上图，Q.front=Q.rear时，队列为空。每次入队一个元素，rear+1；每次出队一个元素，front+1。 当放到元素f时，需要模上数组长度（(Q.rear)%MaxSize=Q.front），然后把数组下标Q.rear置为0。 如果f后继续放g，此时队列头Q.front和队列尾Q.rear相等，都指向下标为1的位置，相等会认为是循环队列为空，所以不能放入g。 循环每次空出一个位置，如果rear+1=front，表示rear追上front，判断循环队列已经放满。 image image ::: warning 循环队列为空时不一定下标为0，只要Q.front=Q.rear队列就为空。 ::: Q.front指向的元素就是要出队的元素。 上图中如果Q.front指向数组下标5的元素，Q.front+1变为6，Q.front%MaxSize变为0，即Q.front又从0开始向后循环。

队列链式存储 image 队列尾部插入，头部删除。 image front指向链表头第一个元素的位置，rear指向链表尾最后一个元素后面一个可以存放元素的位置。 有元素入队后rear向后+1，需要判断是否超出MaxSize，如果超过MaxSize，需要回到开头（位置0）。代码是：Q.rear = (Q.rear + 1) % MaxSize。

循环队列代码：

1#include <stdio.h>
2#include <stdlib.h>
3#define MaxSize 5
4
5typedef int Elemtype;
6typedef struct
7{
8	Elemtype data[MaxSize];
9	Elemtype front, rear;
10}SqQueue;
11
12//初始化循环队列
13void InitQueue(SqQueue &Q)
14{
15	Q.front = Q.rear = 0;  //循环队列初始化是将队列头尾都指向0号元素
16}
17
18//判断是否为空队列
19bool IsEmpty(SqQueue Q)
20{
21	return Q.front = Q.rear;
22}
23
24//入队
25bool EnQueue(SqQueue& Q, Elemtype x)
26{
27	if ((Q.rear + 1) % MaxSize == Q.front)  //判断队列是否已满，已满不能入队
28	{
29		return false;
30	}
31	Q.data[Q.rear] = x;  //入队。rear始终指向队尾可以存放元素的位置
32	Q.rear = (Q.rear + 1) % MaxSize;  //判断rear+1后是否超出MaxSize，如果超出rear要回到起始位置0
33	return true;
34}
35
36//出队
37bool DeQueue(SqQueue& Q, Elemtype& x)
38{
39	if (Q.rear == Q.front)  //判断队列是否为空
40	{
41		return false;  //队列为空时无法出队
42	}
43	x = Q.data[Q.front];  //队列从头部出队，尾部入队
44	Q.front = (Q.front + 1) % MaxSize;  //判断front+1后是否超出MaxSize，如果超出front要回到起始位置0
45}
46int main()
47{
48	SqQueue Q;
49	InitQueue(Q);  //初始化循环队列
50	bool ret;
51	ret = IsEmpty(Q);
52	if (ret)
53	{
54		printf("SqQueue is Empty\n");
55	}
56	else
57	{
58		printf("SqQuene is not Empty\n");
59	}
60	EnQueue(Q, 3);
61	EnQueue(Q, 4);
62	EnQueue(Q, 5);
63	ret = EnQueue(Q, 6);
64	ret = EnQueue(Q, 7);
65	if (ret)
66	{
67		printf("EnQueue success\n");
68	}
69	else
70	{
71		printf("EnQueue failed\n");
72	}
73	Elemtype element;  //存储出队元素
74	ret = DeQueue(Q, element);
75	if (ret)
76	{
77		printf("DeQueue success\n");
78	}
79	else
80	{
81		printf("DeQueue failed\n");
82	}
83	ret = EnQueue(Q, 7);
84	if (ret)
85	{
86		printf("EnQueue success\n");
87	}
88	else
89	{
90		printf("EnQueue failed\n");
91	}
92	return 0;

执行结果如下： image 上述代码第一次末尾入队元素7时，超出MaxSize值，无法入队，在出队队首的一个元素后，元素7入队成功，在主函数结束时打断点查看调试信息，可以看到元素7成功入队，front+1指向队列下标1处，rear模MaxSize后指向下标0处。此时(rear+1)%MaxSize=front，循环列表放满。

链表实现普通队列： 链表实现的普通队列可以有很长，不考虑链表填满的问题。 ::: tip 出队过程中，front从指向头节点开始，每次出队节点都是Q.front->next，即front指向出队节点的前一个，rear指向出队节点的后一个。 :::

::: warning front始终指向头节点，data域不放数据。rear始终指向链表尾，next域置为NULL。 ::: 链表实现的普通队列代码：

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef int Elemtype;
5typedef struct LinkNode
6{
7	Elemtype data;
8	struct LinkNode* next;
9}LinkNode;
10
11typedef struct
12{
13	LinkNode* front, * rear;  //链表头、链表尾（队头、队尾）
14}LinkQueue;  //队列先进先出（队头出队尾进）
15
16//队列初始化，使用带头节点的链表实现
17void InitQueue(LinkQueue& Q)
18{
19	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));  //开辟空间是头节点
20	Q.front->next = NULL;
21}
22
23//入队
24void EnQueue(LinkQueue& Q, Elemtype x)  //入队时从队列尾部入队，Q会改变
25{
26	LinkNode* pnew = (LinkNode*)malloc(sizeof(LinkNode));
27	pnew->data = x;
28	pnew->next = NULL;  //入队的节点next置为NULL，否则需要遍历链表时无法找到链表结束位置
29	Q.rear->next = pnew;  //队尾插入，原队列尾部节点的next指向新入队的节点
30	Q.rear = pnew;  //rear指向新的队列尾部
31}
32
33//出队
34bool DeQueue(LinkQueue& Q, Elemtype& x)  //元素出队时链表Q会改变，取出出队元素，x会改变，使用&
35{
36	if (Q.front == Q.rear)  //front和rear都指向头节点时队列为空
37	{
38		return false;
39	}
40	//Q.front->next = Q.front->next->next;
41	//free(Q.front->next);
42	//Q.front->next = NULL;
43	x = Q.front->next->data;
44	LinkNode* p = Q.front->next;
45	Q.front = p->next;
46	if (Q.rear == p)  //当链表中只剩下一个节点时，该节点被删除（出队）时要改变rear
47	{
48		Q.rear = Q.front;
49	}
50	free(p);
51	p = NULL;
52	return true;
53}
54
55int main()
56{
57	LinkQueue Q;
58	InitQueue(Q);  //初始化队列
59	EnQueue(Q, 3);
60	EnQueue(Q, 4);
61	EnQueue(Q, 5);
62	EnQueue(Q, 6);
63	EnQueue(Q, 7);
64	EnQueue(Q, 3);
65	EnQueue(Q, 9);
66	bool ret;
67	Elemtype element;
68	ret = DeQueue(Q, element);
69	if (ret)
70	{
71		printf("DeQueue success element = %d\n", element);
72	}
73	else 
74	{
75		printf("DeQueue falied");
76	}
77	return 0;
78}
题目解读

image 上图是一个空的循环队列，队列中的节点data域为空，next域指向自己，起始时front和rear都指向该空闲节点。（循环队列没有固定的头节点） image 当入队一个新节点pnew时，front指向空闲节点不变，rear的next域由指向空闲节点变为指向新节点pnew：rear->next=pnew，rear指向新的队列尾部节点：rear=pnew或rear=rear->next，新节点的next域指向空闲节点：rear->next=front，此时循环队列是填满状态。 要求出队元素的空间可重复使用，即每次malloc开辟的空间在使用完毕后不会free，使用循环队列。 要求占用空间只增不减，即不能使用数组形式，定义数组时数组所占空间就已经确定了。 （链式存储结构使用链表，顺序存储结构使用数组。） image image 入队时，先判断队列是否已满，已满则在rear后开辟新节点，rear->next由front指向新节点，入队元素保存在rear指向节点的data域，rear=rear->next。未满则在新节点放在rear->next位置上，rear指向新节点，rear=rear->next。 出队时，先判断队列是否为空，不为空时front指向的节点出队，front=front->next。 代码实现：

1#define _CRT_SECURE_NO_WARNINGS
2#include <stdio.h>
3#include <stdlib.h>
4
5typedef int Elemtype;
6typedef struct LNode {
7    Elemtype data;
8    struct LNode* next;
9}LNode, * LinkList;
10
11//入队
12void EnQueue(LinkList front, LinkList& rear, Elemtype value)
13{
14    LinkList pnew;
15    if (rear->next == front)  //队列已满
16    {
17        pnew = (LinkList)malloc(sizeof(LNode));  //申请空间存放入队元素
18        rear->data = value;  //根据题目要求将入队元素直接放在rear的data域中
19        rear->next = pnew;  //做分隔
20        //rear = rear->next;
21        //rear->next = front;
22        pnew->next = front;
23        rear = pnew;
24    }
25    else
26    {
27        rear->data = value;
28        rear = rear->next;
29    }
30}
31
32//出队
33void DeQueue(LinkList& front, LinkList rear)
34{
35    if (front == rear)
36    {
37        printf("队列为空\n");
38    }
39    else
40    {
41        //循环队列空间可以重复使用，出队时不会释放空间
42        printf("出队的值为%d\n", front->data);
43        front = front->next;
44    } 
45}
46
47//循环队列操作的总流程
48void CircleQueue(LinkList& front, LinkList& rear)
49{
50    //假设带头节点的链表
51    front = (LinkList)malloc(sizeof(LNode));  //申请空间使rear和front都指向这个头节点
52    rear = front;
53    rear->next = front;  //构建循环队列
54    //入队
55    EnQueue(front, rear, 3);
56    EnQueue(front, rear, 4);
57    //出队
58    DeQueue(front, rear);
59    DeQueue(front, rear);
60    DeQueue(front, rear);
61}
62
63int main()
64{
65    LinkList front, rear;
66    CircleQueue(front, rear);
67    return 0;
68}
1出队的值为3
2出队的值为4
3队列为空
点赞
收藏

评论区

加载中...

相关推荐

stack顺序存储结构

《偶刚开始学习数据结构，欢迎拍砖111》栈是只能通过访问它的一段来实现数据存储的一种线性数据结构，换句话来说就是先进后出的原则，FILO，与队列刚好相反哈，现在只说stack。栈包括以下几种基本运算（1）初始化（2）判断是否为空（3）push（4）pop（5）top其他的则根据这几种基本操作进行组合，即可实现。栈的实现同样

5 手写Java Stack 核心源码

Stack是Java中常用的数据结构之一，Stack具有"后进先出(LIFO)"的性质。只能在一端进行插入或者删除，即压栈与出栈栈的实现比较简单，性质也简单。可以用一个数组来实现栈结构。1.入栈的时候，只在数组尾部插入2.出栈的时候，只在数组尾部删除我们来看一下Stack的用法：如下publicstaticvoidmai

Java实现顺序栈

一、分析　　栈是限定仅在表的一端进行插入或删除操作的线性表，对于栈来说，操作端称为栈顶，另一端则称为栈底，栈的修改是按照后进先出的原则进行的，因此又称为后进先出的线性表。　　顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。　　一个标准的顺序栈

C语言利用va_list、va_start、va_end、va_arg宏定义可变参数的函数

在定义可变参数的函数之前，先来理解一下函数参数的传递原理：1、函数参数是以栈这种数据结构来存取的，在函数参数列表中，从右至左依次入栈。2、参数的内存存放格式：参数的内存地址存放在内存的堆栈段中，在执行函数的时候，从最后一个（最右边）参数开始入栈。因此栈底高地址，栈顶低地址，举个例子说明一下：voidtest(inta,floatb,ch

JVM 字节码指令表

字节码助记符指令含义0x00nop什么都不做0x01aconst\_null将null推送至栈顶0x02iconst\_m1将int型1推送至栈顶0x03iconst\_0将int型0推送至栈顶0x04iconst\_1将int型1推送至栈顶0x05ic

C++栈和队列

使用标准库的栈和队列时，先包含相关的头文件include<stackinclude<queue定义栈如下：stack<intstk;定义队列如下：queue<intq;栈提供了如下的操作s.empty()如果栈为空返回true，否则返回fals