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

数据结构——栈和队列_3.2.6

作者：Li_阴宅 | 2024-06-25 09:50:25

赞

踩

3.2.6

fe594ea5bf754ddbb223a54d8fb1e7bc.gif

目录

 一.前言

二.前文回顾

三.栈

3.1 栈的概念及结构

3.2 栈的实现

3.2.1 初始化函数

3.2.2 销毁函数

3.2.3 入栈函数

3.2.4 出栈函数

3.2.5 计算大小函数

3.2.6 空栈函数

3.2.7 获取栈顶函数

 3.2.8 小测试

3.3 全部代码

四.栈的练习

4.1 有效的括号

五.队列

5.1队列的概念及结构

5.2 队列的实现

5.2.1 初始化函数

5.2.2 入队列函数

5.2.3 出队列函数

5.2.4 获取头队列函数

5.2.5 获取尾队列函数

5.2.6 判空（队列）函数

5.2.7 计算队列大小函数

5.2.8 销毁函数

 5.2.9 小测试

5.3 全部代码 

六.队列的练习

6.1选择题

6.2用队列实现栈

6.2.1 整体思路：

6.2.2 Push函数（入队列）：

6.2.3 Pop函数(出队列）：

6.2.4 Top函数（取栈顶）：

6.2.5 Empty函数（判空）:

6.2.6 Free（释放空间）函数：

6.2.7 全部代码

6.3用栈实现队列

6.3.1 整体思路：

6.3.2 Push（入栈）函数

6.3.3 Peek(取头)函数

6.3.4 Pop（出栈）函数

6.3.5 Empty（判空）函数

6.3.6 Free（释放空间）函数

6.3.7 全部代码

6.4 设计循环队列

6.4.1 整体思路：

6.4.2 判空与判满函数（Is(Empty)/(Full))

6.4.3 EnQueue(插入)函数

6.4.4 DeQueue（删除）函数

6.4.5 Front（取头）函数

6.4.6 rear（取尾）函数

6.4.7 Free（释放空间）函数

6.4.8 全部代码

七.结语

8fb442646f144d8daecdd2b61ec78ecd.png 一.前言

如果有友友看了我上一篇文章：数据结构——单链表，那么本篇的队列和栈你会发现到处是单链表的影子，所以我们的重心是在关于队列和栈的OJ题上。本文干货满满，高能不断，一定不要错过！码字不易，希望大家多多支持我呀！（三连＋关注，你是我滴神！）

二.前文回顾

顺序表和链表的区别

三.栈

3.1 栈的概念及结构

  • 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out)的原则。
  • 压栈: 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
  • 出栈：栈的删除操作叫做出栈，出数据也在栈顶。

3.2 栈的实现

其实数组或者链表都是可以实现栈的，二者区别无法就是实现的方式有所不同，效率各有千秋。

  • 要想用数组实现的话，那数组尾部就可以作为栈顶（尾插尾删方便）。
  • 要想用链表实现的话，那链表头部得作为栈顶，然后进行多次头插入栈（这样出栈时方便，用头删即可）。想想如果是栈顶是在1的位置，那到时候出栈删除1时还得找到2进行重新链接，要用到双链表。所以我们的原则是能用单链表实现就用单链表~

相对而言，数组更合适实现栈~

3.2.1 初始化函数

这里有一点需要注意，当top一开始是0的时候，入栈完top++指向下一位.这样当我们打算输入（入栈）最后一个数据时，真正的栈顶并非top所指向的数据，而是top-1的指向。

  1. //初始化函数
  2. void STInit(ST* ps)
  3. {
  4. 	assert(ps);
  5. 	ps->top = 0;
  6. 	ps->a = NULL;
  7. 	ps->capacity = 0;
  8. }

3.2.2 销毁函数

  1. //销毁函数
  2. void STDestroy(ST* ps)
  3. {
  4. 	assert(ps);
  5. 	free(ps->a);
  6. 	ps->a = NULL;
  7. 	ps->top = ps->capacity = 0;
  8. }

3.2.3 入栈函数

在准备扩容的时候一开始空间是0为什么这里可以用realloc来代替malloc呢？realloc不是只能在已有空间基础上扩容吗？

如果一开始没有空间，那么realloc在这时候是可以代替malloc来作出对于功能的。（为空可当成malloc，不为空就realloc）

  1. //入栈函数
  2. void STPush(ST* ps, STDataType x)
  3. {
  4. 	assert(ps);
  5. 	//扩容准备
  6. 	if (ps->top == ps->capacity)
  7. 	{
  8. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  9. 		STDataType* tmp = (STDataType*)relloc(ps->a, sizeof(STDataType)*newCapacity);
  10. 		if (tmp == NULL)
  11. 		{
  12. 			perror("relloc fail");
  13. 			exit(-1);
  14. 		}
  15. 		ps->a = tmp;
  16. 		ps->capacity = newCapacity;
  17. 	}
  18. 	//入栈准备
  19. 	ps->a[ps->top] = x;
  20. 	ps->top++;
  21.  
  22. 	
  23. 	
  24. }

3.2.4 出栈函数

出栈挺简单，唯一要注意的就是当栈为空的时候，就不要继续出栈了。

  1. //出栈函数
  2. void STPop(ST* ps)
  3. {
  4. 	assert(ps);
  5. 	//空
  6. 	assert(ps->top > 0);
  7. 	ps->top--;
  8. }

3.2.5 计算大小函数

  1. //计算大小函数
  2. int STSize(ST* ps)
  3. {
  4. 	assert(ps);
  5.  
  6. 	return ps->top;
  7.  
  8. }

3.2.6 空栈函数

  1. //判空（栈）函数
  2. bool STEmpty(ST* ps)
  3. {
  4. 	assert(ps);
  5.  
  6. 	return ps->top==0;
  7. }

看top指向是否空，如果为空则会返回1，不为空则返回0.

3.2.7 获取栈顶函数

  1. //获取栈顶函数
  2. STDataType STTop(ST* ps)
  3. {
  4. 	assert(ps);
  5. 	//空
  6. 	assert(ps->top > 0);
  7. 	return ps->a[ps->top - 1];
  8. }

 3.2.8 小测试

最后我们来测试是否满足栈的特点：后进先出

  1. void TestStack1()
  2. {
  3. 	ST st;
  4. 	STInit(&st);
  5. 	STPush(&st, 1);
  6. 	STPush(&st, 2);
  7. 	STPush(&st, 3);
  8. 	STPush(&st, 4);
  9. 	STPush(&st, 5);
  10. 	while (!STEmpty(&st))
  11. 	{
  12. 		printf("%d ", STTop(&st));
  13. 		STPop(&st);//获取后一位的栈顶
  14. 	}
  15. 	printf("\n");
  16.  
  17. 	STDestroy(&st);
  18. }

3.3 全部代码

  1. //Stack.h
  2. pragma once
  3. #include <stdio.h>
  4. #include <assert.h>
  5. #include <stdlib.h>
  6. #include <stdbool.h>
  7.  
  8.  
  9. typedef int STDataType;
  10. typedef struct Stack
  11. {
  12. 	STDataType* a;
  13. 	int top;
  14. 	int capacity;
  15. }ST;
  16.  
  17. //初始化函数
  18. void STInit(ST* ps);
  19.  
  20. //销毁函数
  21. void STDestroy(ST* ps);
  22.  
  23. //入栈函数
  24. void STPush(ST* ps, STDataType x);
  25.  
  26. //出栈函数
  27. void STPop(ST* ps);
  28.  
  29. //计算大小函数
  30. int STSize(ST* ps);
  31.  
  32. //空（栈）函数
  33. bool STEmpty(ST* ps);
  34.  
  35. //获取栈顶函数
  36. STDataType STTop(ST* ps);

——————————————————————————————-——————————

  1. //Test,c
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include "Stack.h"
  4.  
  5.  
  6. void TestStack1()
  7. {
  8. 	ST st;
  9. 	STInit(&st);
  10. 	STPush(&st, 1);
  11. 	STPush(&st, 2);
  12. 	STPush(&st, 3);
  13. 	STPush(&st, 4);
  14. 	STPush(&st, 5);
  15. 	while (!STEmpty(&st))
  16. 	{
  17. 		printf("%d ", STTop(&st));
  18. 		STPop(&st);//获取后一位的栈顶
  19. 	}
  20. 	printf("\n");
  21.  
  22. 	STDestroy(&st);
  23. }
  24.  
  25.  
  26. int main()
  27. {
  28. 	TestStack1();
  29. 	return 0;
  30. }

—————————————————————————————————————————— 

  1.  
  2. //Stack,c
  3. #define _CRT_SECURE_NO_WARNINGS 1
  4. #include "Stack.h"
  5.  
  6.  
  7. //初始化函数
  8. void STInit(ST* ps)
  9. {
  10. 	assert(ps);
  11. 	ps->top = 0;
  12. 	ps->a = NULL;
  13. 	ps->capacity = 0;
  14. }
  15.  
  16.  
  17. //销毁函数
  18. void STDestroy(ST* ps)
  19. {
  20. 	assert(ps);
  21. 	free(ps->a);
  22. 	ps->a = NULL;
  23. 	ps->top = ps->capacity = 0;
  24. }
  25.  
  26.  
  27. //入栈函数
  28. void STPush(ST* ps, STDataType x)
  29. {
  30. 	assert(ps);
  31. 	//扩容准备
  32. 	if (ps->top == ps->capacity)
  33. 	{
  34. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  35. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
  36. 		if (tmp == NULL)
  37. 		{
  38. 			perror("relloc fail");
  39. 			exit(-1);
  40. 		}
  41. 		ps->a = tmp;
  42. 		ps->capacity = newCapacity;
  43. 	}
  44. 	//入栈准备
  45. 	ps->a[ps->top] = x;
  46. 	ps->top++;
  47.  
  48.  
  49.  
  50. }
  51.  
  52. //出栈函数
  53. void STPop(ST* ps)
  54. {
  55. 	assert(ps);
  56. 	//空
  57. 	assert(ps->top > 0);
  58. 	ps->top--;
  59. }
  60.  
  61. //计算大小函数
  62. int STSize(ST* ps)
  63. {
  64. 	assert(ps);
  65.  
  66. 	return ps->top;
  67.  
  68. }
  69.  
  70. //空（栈）函数
  71. bool STEmpty(ST* ps)
  72. {
  73. 	assert(ps);
  74.  
  75. 	return ps->top == 0;
  76. }
  77.  
  78. //获取栈顶函数
  79. STDataType STTop(ST* ps)
  80. {
  81. 	assert(ps);
  82. 	//空
  83. 	assert(ps->top > 0);
  84. 	return ps->a[ps->top - 1];
  85. }

其实写到最后我们可以发现，栈其实就是顺序表的简化版，相当于定义了部分适用于栈特征的接口罢了~ 

四.栈的练习

4.1 有效的括号

链接：力扣——有效的括号

基本思路：

  • 数量上最后再进行判断~
  • 类型上：遇到右括号就进行匹配，看有没有对应的左括号。
  • 顺序上：当遇到右括号时判断距离最进的括号是否为对应左括号。

那如何找到最近的括号呢？

  1. 左括号，入栈
  2. 右括号，出栈顶括号，进行匹配

  1. //前面需要用到Stack.h与Stack.c的代码	
  2. bool isValid(char* s)
  3. 	{
  4. 		ST st;
  5. 		STInit(&st);
  6. 		char topVal;
  7. 		while (*s)
  8. 		{
  9.             //左括号入栈
  10. 			if (*s == '(' || *s == '[' || *s == '{')
  11. 			{
  12. 				STPush(&st, *s);
  13. 			}
  14.             //右括号判定
  15. 			else
  16. 			{
  17. 				//数量不匹配——如果栈中没有左括号，
  18.                 //说明在s中右括号在左括号前面，那肯定是不行的
  19. 				if (STEmpty(&st))
  20. 				{
  21. 					STDestroy(&st);
  22. 					return false;
  23. 				}
  24.                 //在这一步说明栈中有左括号
  25. 				topVal = STTop(&st);//把栈顶的左括号存入topVal中
  26. 				STPop(&st);//压栈，使得下一次取排在栈顶前一位的左括号
  27. 				if ((*s == ']' && topVal != '[') || (*s == ')' && topVal != '(') || (*s                                     
  28.                      == '}' && topVal != '{'))
  29.              //这里我们不去判定括号与括号的对应，
  30.              //去判断不对应的情况，这样筛选到最后的就是对应的                    
  31. 				{
  32. 					STDestroy(&st);//如果在栈顶中取出的左括号与条件中目前
  33.                                    // 数组指向的右括号不对应，那就销毁栈并且返回错误
  34. 					return false;
  35. 				}
  36. 			}
  37.  
  38. 			++s;//对数组中的每一个元素进行遍历
  39. 		}
  40.         //到了最后如果栈里面还有左括号，那么就说明数量对不上，在STEmpty(&st)判断为0
  41.         //如果栈里面没有左括号，那么在STEmpty(&st)判断为1
  42. 		//栈不为空，flase,说明数量不匹配
  43. 		bool ret = STEmpty(&st);
  44. 		STDestroy(&st);
  45. 		return ret;
  46. 	}

备注：千万不要想着去用switch，千万不要，除非你想要头脑风暴。。。。

五.队列

5.1队列的概念及结构

  • 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。
  • 入队列：进行插入操作的一端称为队尾。
  • 出队列：进行删除操作的一端称为队头。

5.2 队列的实现

队列也可以用数组或链表的结构实现，使用链表的结构表现更优一些，因为数组在实现出队列（头删）效率比较低~

这里我们采用单链表结构进行实现队列，既然队列核心是一端出一端入，那我们就先预设头节点（head）与尾节点（tail）的指向。

因为是不带哨兵位，所以我们插入第一个节点时既要赋值给head,又要赋值给tail。并且还要用到二级，因为形参的改变影响不了实参。（这里也不能用return,我们这里要返回两个值。）如果有友友理解不了二级指针可以移步至这篇文章单链表，里面的尾插部分有详细讲解哦~

切回正题，在这里我们可以采用新的方法来实现二级指针的功能。

  1. typedef struct Queue
  2. {
  3. 	QNode* head;
  4. 	QNode* tail;
  5. 	int size;
  6. }Que;
  7. //入队列函数
  8. void QueuePush(Que* pq, QDataType x);

我们可以再建立一个结构体，里面放置头指针和尾指针，用结构体接收，这样就可以改变二者的指向了。

5.2.1 初始化函数

  1. //初始化函数
  2. void QueueInit(Que* pq)
  3. {
  4. 	assert(pq);
  5. 	pq->head = pq->tail = NULL;
  6. 	pq->size = 0;
  7. }

5.2.2 入队列函数

在我们处理好空间问题后，要进行入队列（尾插）就得先找到尾节点，不过这里还有一些小问题需要注意。

如果链表是空的呢？——赋值给它们2个

  1. //入队列函数
  2. void QueuePush(Que* pq, QDataType x)
  3. {
  4. 	assert(pq);
  5.     //创造新节点
  6. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  7. 	if (newnode == NULL)
  8. 	{
  9. 		perror("malloc fail");
  10. 		exit(-1);
  11. 	}
  12.     //给新节点插入数据
  13. 	newnode->data = x;
  14. 	newnode->next = NULL;
  15. 	if (pq->tail==NULL)//链表为空时
  16. 	{
  17. 		pq->head = pq->tail = newnode;
  18. 	}
  19. 	else//链表不为空时
  20. 	{
  21. 		pq->head->next = newnode;
  22. 		pq->tail = newnode;
  23. 	}
  24.     pq->size++;
  25. }

5.2.3 出队列函数

出队列其实就是头删，定义好下一位的指针next就可以实现了

不过这样写还有一个问题；在只剩下一个节点的时候，head可以顺利置空，但tail却没有置空变成了野指针。

  1. //出队列函数
  2. void QueuePop(Que* pq)
  3. {
  4. 	assert(pq);
  5. 	assert(!QueueEmpty(pq));//空链表时不给删除
  6. 	if (pq->head->next == NULL)//只剩下一个节点时
  7. 	{
  8. 		pq->head = pq->tail = NULL;
  9. 	}
  10. 	else
  11. 	{
  12. 		QNode* next = pq->head->next;
  13. 		free(pq->head);
  14. 		pq->head = next;
  15. 	}
  16. 	pq->size--;
  17. }

5.2.4 获取头队列函数

  1. //获取头队列函数
  2. QDataType QueueFront(Que* pq)
  3. {
  4. 	assert(pq);
  5. 	assert(!QueueEmpty(pq));
  6. 	return pq->head->data;
  7. }

5.2.5 获取尾队列函数

  1. //获取尾队列函数
  2. QDataType QueueBack(Que* pq)
  3. {
  4. 	assert(pq);
  5. 	assert(!QueueEmpty(pq));
  6. 	return pq->tail->data;
  7. }

5.2.6 判空（队列）函数

  1. //判空（队列）函数
  2. bool QueueEmpty(Que* pq)
  3. {
  4. 	assert(pq);
  5.  
  6. 	return pq->head == NULL;
  7. }

5.2.7 计算队列大小函数

  1. //计算大小函数
  2. int QueueSize(Que* pq)
  3. {
  4. 	assert(pq);
  5.  
  6. 	return pq->size;
  7. }

5.2.8 销毁函数

  1. //销毁函数
  2. void QueueDestroy(Que* pq)
  3. {
  4. 	assert(pq);
  5. 	QNode* cur = pq->head;//创造一个方便遍历的指针
  6. 	while (cur)
  7. 	{
  8. 		QNode* next = cur->next;//记录每一次销毁后一位的指针
  9. 		free(cur);
  10. 		cur = next;
  11. 	}
  12. 	pq->head = pq->tail = NULL;//置空，避免野指针
  13. 	pq->size = 0;
  14. }

 5.2.9 小测试

  1. void TestQueue()
  2. {
  3. 	Que q;
  4. 	QueueInit(&q);
  5. 	QueuePush(&q, 1);
  6. 	QueuePush(&q, 2);
  7. 	QueuePush(&q, 3);
  8. 	QueuePush(&q, 4);
  9. 	QueuePush(&q, 5);
  10.  
  11. 	while (!QueueEmpty(&q))//遍历，链表不为空就继续
  12. 	{
  13. 		printf("%d ", QueueFront(&q));//打印头队列
  14. 		QueuePop(&q);//打印完就让其出队列
  15. 	}
  16. 	printf("\n");
  17.  
  18.  
  19. 	QueueDestroy(&q);
  20.  
  21. }

成功实现先进先出。

5.3 全部代码 

  1. //Queue.h
  2. #pragma once
  3. #include <stdio.h>
  4. #include <assert.h>
  5. #include <stdlib.h>
  6. #include <stdbool.h>
  7.  
  8. typedef int QDataType;
  9. typedef struct QueueNode
  10. {
  11. 	struct QueueNode* next;
  12. 	QDataType data;
  13. }QNode;
  14.  
  15. typedef struct Queue
  16. {
  17. 	QNode* head;
  18. 	QNode* tail;
  19. 	int size;
  20. }Que;
  21.  
  22.  
  23.  
  24. //入队列函数
  25. void QueuePush(Que* pq, QDataType x);
  26.  
  27. //初始化函数
  28. void QueueInit(Que* pq);
  29.  
  30. //销毁函数
  31. void QueueDestroy(Que* pq);
  32.  
  33. //出队列函数
  34. void QueuePop(Que* pq);
  35.  
  36. //获取头队列函数
  37. QDataType QueueFront(Que* pq);
  38.  
  39. //获取尾队列函数
  40. QDataType QueueBack(Que* pq);
  41.  
  42. //判空（队列）函数
  43. bool QueueEmpty(Que* pq);
  44.  
  45. //计算大小函数
  46. int QueueSize(Que* pq);

————-——————————————————————————————————————

  1. //Queue.c
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include "Queue.h"
  4.  
  5.  
  6. //初始化函数
  7. void QueueInit(Que* pq)
  8. {
  9. 	assert(pq);
  10. 	pq->head = pq->tail = NULL;
  11. 	pq->size = 0;
  12. }
  13.  
  14. //入队列函数
  15. void QueuePush(Que* pq, QDataType x)
  16. {
  17. 	assert(pq);
  18. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  19. 	if (newnode == NULL)
  20. 	{
  21. 		perror("malloc fail");
  22. 		exit(-1);
  23. 	}
  24. 	newnode->data = x;
  25. 	newnode->next = NULL;
  26. 	if (pq->tail==NULL)
  27. 	{
  28. 		pq->head = pq->tail = newnode;
  29. 	}
  30. 	else
  31. 	{
  32. 		pq->tail->next = newnode;
  33. 		pq->tail = newnode;
  34. 	}
  35. 	pq->size++;
  36. }
  37.  
  38. //出队列函数
  39. void QueuePop(Que* pq)
  40. {
  41. 	assert(pq);
  42. 	assert(!QueueEmpty(pq));
  43. 	if (pq->head->next == NULL)
  44. 	{
  45. 		free(pq->head);
  46. 		pq->head = pq->tail = NULL;
  47. 	}
  48. 	else
  49. 	{
  50. 		QNode* next = pq->head->next;
  51. 		free(pq->head);
  52. 		pq->head = next;
  53. 	}
  54. 	pq->size--;
  55. }
  56.  
  57. //获取头队列函数
  58. QDataType QueueFront(Que* pq)
  59. {
  60. 	assert(pq);
  61. 	assert(!QueueEmpty(pq));
  62. 	return pq->head->data;
  63. }
  64.  
  65. //获取尾队列函数
  66. QDataType QueueBack(Que* pq)
  67. {
  68. 	assert(pq);
  69. 	assert(!QueueEmpty(pq));
  70. 	return pq->tail->data;
  71. }
  72.  
  73. //判空（队列）函数
  74. bool QueueEmpty(Que* pq)
  75. {
  76. 	assert(pq);
  77.  
  78. 	return pq->head == NULL;
  79. }
  80.  
  81. //计算大小函数
  82. int QueueSize(Que* pq)
  83. {
  84. 	assert(pq);
  85.  
  86. 	return pq->size;
  87. }
  88.  
  89. //销毁函数
  90. void QueueDestroy(Que* pq)
  91. {
  92. 	assert(pq);
  93. 	QNode* cur = pq->head;
  94. 	while (cur)
  95. 	{
  96. 		QNode* next = cur->next;
  97. 		free(cur);
  98. 		cur = next;
  99. 	}
  100. 	pq->head = pq->tail = NULL;
  101. 	pq->size = 0;
  102. }

———————————————————————————————————————————

  1. //Test.c
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include "Queue.h"
  4.  
  5.  
  6. void TestQueue()
  7. {
  8. 	Que q;
  9. 	QueueInit(&q);
  10. 	QueuePush(&q, 1);
  11. 	QueuePush(&q, 2);
  12. 	QueuePush(&q, 3);
  13. 	QueuePush(&q, 4);
  14. 	QueuePush(&q, 5);
  15.  
  16. 	while (!QueueEmpty(&q))//遍历，链表不为空就继续
  17. 	{
  18. 		printf("%d ", QueueFront(&q));//打印头队列
  19. 		QueuePop(&q);//打印完就让其出队列
  20. 	}
  21. 	printf("\n");
  22.  
  23.  
  24. 	QueueDestroy(&q);
  25.  
  26. }
  27.  
  28.  
  29. int main()
  30. {
  31. 	TestQueue();
  32. 	return 0;
  33. }

六.队列的练习

6.1选择题

学习完队列和栈我们可以知道，入队列是1 2 3 4 5那出队列就是1 2 3 4 5，那栈呢？也入栈1 2 3 4 5，出栈就一定是5 4 3 2 1吗？

第一问无疑是选B，那第二问又是怎么回事呢？我们看好这一句话“进栈过程可以出栈”，这意味着有多种可能性，其中最不可能的就是C选项了，3出栈前提是1 2 3入栈，那1出栈前提是1入栈，显然不符合事实。

6.2用队列实现栈

链接：力扣——用队列实现栈

  1.  
  2.  
  3.  
  4. typedef struct {
  5.  
  6. } MyStack;
  7.  
  8.  
  9. MyStack* myStackCreate() {
  10.  
  11. }
  12.  
  13. void myStackPush(MyStack* obj, int x) {
  14.  
  15. }
  16.  
  17. int myStackPop(MyStack* obj) {
  18.  
  19. }
  20.  
  21. int myStackTop(MyStack* obj) {
  22.  
  23. }
  24.  
  25. bool myStackEmpty(MyStack* obj) {
  26.  
  27. }
  28.  
  29. void myStackFree(MyStack* obj) {
  30.  
  31. }

6.2.1 整体思路：

我们先列出两个队列，然后往其中一个队列Push1 2 3 4,要想实现后入先出的栈，就得把4优先Pop出来 .

为了实现Pop4，我们可以依次出队列中队头数据把它插入到另一个队列里，当剩下最后一个数据4时再Pop掉（不继续插入到另一个队列）

当我们想让5，6入队列的时候又应该去哪里呢？——去不为空的队列，然后再重复上述的操作（把n个数据的前n-1个导走）最后Pop出6（后入先出） 。

所以大思路就是保持一个队列为空（导出数据），另一个不为空（存入数据）。

  • 入队列：不为空的队列
  • 出队列：不为空队列前N-1个出队列，插入空队列。删除剩余的数据。

 代码解析：

  1. MyStack* myStackCreate() {
  2.     MyStack st;
  3.  
  4.     //......
  5.     return &st
  6. }

这个接口的作用仅仅是返回&st吗？——这个局部作用域一出来那么里面的变量都会销毁，这时候传st的地址已经是没意思的了，它已经变成一个野指针了。为了保证MyStack的对象还在，我们可以改用malloc来创造节点，这样出作用域时，malloc出来的空间还是在的。

  1. MyStack* myStackCreate() {
  2. 	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
  3. 	QueueInit(&pst->q1);
  4. 	QueueInit(&pst->q2);
  5.  
  6. 	return pst;
  7. }

6.2.2 Push函数（入队列）：

由于我们不知道哪个为空，哪个不为空，那么我们直接用判空条件来判断再进行入队列

  1. void myStackPush(MyStack* obj, int x) {
  2. 	if (!QueueEmpty(&obj->q1))//如果q1为空
  3. 	{
  4. 		QueuePush(&obj->q1, x);
  5. 	}
  6. 	else
  7. 	{
  8. 		QueuePush(&obj->q2, x);
  9. 	}
  10.  
  11. }

6.2.3 Pop函数(出队列）：

还是一样的逻辑，不为空的队列往空队列导入。在这里我们假设q1为空，q2不为空。如果q1不为空（判空函数）那交换即可。

  1. int myStackPop(MyStack* obj) {
  2. 	QNode* empty = &obj->q1;//假设q1为空
  3. 	QNode* nonEmpty = &obj->q2;//假设q2不为空
  4. 	if (!QueueEmpty(&obj->q1))//如果qi不为空
  5. 	{
  6. 		empty = &obj->q2;//交换
  7. 		nonEmpty = &obj->q1;
  8.  
  9. 	}
  10. 	//前size-1个导入空队列
  11. 	while (QueueSize(nonEmpty) > 1)
  12. 	{
  13. 		QueuePush(empty, QueueFront(nonEmpty));
  14. 		//进行入队列，在空队列中存入在不为空队列中的首个数据
  15. 		QueuePop(nonEmpty);
  16. 		//再Pop掉该数据，使下一次循环是首数据后面的数据
  17.  
  18. 	}//入一次出一次，直达剩下一个
  19. 	//这时候只剩下一个数据，获取栈顶元素
  20. 	int top = QueueFront(nonEmpty);//存储不为空队列中的元素
  21. 	QueuePop(nonEmpty);//再Pop掉该元素
  22.  
  23. 	return top;//返回所谓的栈顶数据
  24. 	//至此，该函数完全实现在2个队列入好数据后，
  25. 	//结果返回的是后入队列的数据，实现了后进后出。
  26. }

到这里大家是不是有疑惑，为什么都是&obj，到了empty传输时反而不用取地址了呢？

我们需要把类型认识清楚，q1与q2是队列的结构体，该结构体包含了头指针（head)，尾指针（tail),和size。对于我们所要实现的接口（Pop,Push,Creat)而言，它们想要改变的都是结构体的指针（tail,head等）来实现自身功能。所以这里需要&obj,而empty与nonEmpty已经是结构体指针了，就相当于&obj，也就不需要&了。

6.2.4 Top函数（取栈顶）：

这个函数要实现的功能是取栈顶元素，也就是取最后入队列的数据。这里我们可以直接复用前面所写的获取队列尾部数据函数（ QueueBack）来轻松实现。

  1. int myStackTop(MyStack* obj) {
  2. 	//哪个队列不为空就去取该队列的尾部数据
  3. 	if (!QueueEmpty(&obj->q1))
  4. 	{
  5. 		return QueueBack(&obj->q1);
  6. 	}
  7. 	else
  8. 	{
  9. 		return QueueBack(&obj->q2);
  10. 	}
  11. }

6.2.5 Empty函数（判空）:

在这里的判空应该是两个队列都为空，那才是空。一个为空的不算空。

  1. bool myStackEmpty(MyStack* obj) {
  2. 	return  QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
  3. }

6.2.6 Free（释放空间）函数：

这里我们不能直接free掉obj，因为在obj里面有两个队列q1,q2而这两个队列的底层是链表，所以我们在free之前记得使用销毁函数（QueueDestroy）（销毁链表）

  1. void myStackFree(MyStack* obj) {
  2. 	QueueDestroy(&obj->q1);
  3. 	QueueDestroy(&obj->q2);
  4. 	free(obj);
  5. }

6.2.7 全部代码

注：想要写题解或者测试，请自行添加上文关于Queue.c与Queue.h的代码段（下面代码能够复用的前提）

  1.  
  2. typedef struct {
  3. 	Que q1;
  4. 	Que q2;
  5. } MyStack;
  6.  
  7.  
  8. MyStack* myStackCreate() {
  9. 	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
  10. 	QueueInit(&pst->q1);
  11. 	QueueInit(&pst->q2);
  12.  
  13. 	return pst;
  14. }
  15.  
  16. void myStackPush(MyStack* obj, int x) {
  17. 	if (!QueueEmpty(&obj->q1))//如果q1为空
  18. 	{
  19. 		QueuePush(&obj->q1, x);
  20. 	}
  21. 	else
  22. 	{
  23. 		QueuePush(&obj->q2, x);
  24. 	}
  25.  
  26. }
  27.  
  28. int myStackPop(MyStack* obj) 
  29. {
  30. 	QNode* empty = &obj->q1;//假设q1为空
  31. 	QNode* nonEmpty = &obj->q2;//假设q2不为空
  32. 	if (!QueueEmpty(&obj->q1))//如果qi不为空
  33. 	{
  34. 		empty = &obj->q2;//交换
  35. 		nonEmpty = &obj->q1;
  36.  
  37. 	}
  38. 	//前size-1个导入空队列
  39. 	while (QueueSize(nonEmpty) > 1)
  40. 	{
  41. 		QueuePush(empty, QueueFront(nonEmpty));
  42. 		//进行入队列，在空队列中存入在不为空队列中的首个数据
  43. 		QueuePop(nonEmpty);
  44. 		//再Pop掉该数据，使下一次循环是首数据后面的数据
  45.  
  46. 	}//入一次出一次，直达剩下一个
  47. 	//这时候只剩下一个数据，获取栈顶元素
  48. 	int top = QueueFront(nonEmpty);//存储不为空队列中的元素
  49. 	QueuePop(nonEmpty);//再Pop掉该元素
  50.  
  51. 	return top;//返回所谓的栈顶数据
  52. 	//至此，该函数完全实现在2个队列入好数据后，
  53. 	//结果返回的是后入队列的数据，实现了后进后出。
  54. }
  55.  
  56. int myStackTop(MyStack* obj) {
  57. 	//哪个队列不为空就去取该队列的尾部数据
  58. 	if (!QueueEmpty(&obj->q1))
  59. 	{
  60. 		return QueueBack(&obj->q1);
  61. 	}
  62. 	else
  63. 	{
  64. 		return QueueBack(&obj->q2);
  65. 	}
  66. }
  67.  
  68. bool myStackEmpty(MyStack* obj) {
  69. 	return  QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
  70. }
  71.  
  72. void myStackFree(MyStack* obj) {
  73. 	QueueDestroy(&obj->q1);
  74. 	QueueDestroy(&obj->q2);
  75. 	free(obj);
  76. }

最后附上结构图，帮助大家理解~

这也是我们为什么不能直接free掉obj的原因。

6.3用栈实现队列

链接：力扣——用栈实现队列

  1. typedef struct {
  2.  
  3. } MyQueue;
  4.  
  5.  
  6. MyQueue* myQueueCreate() {
  7.  
  8. }
  9.  
  10. void myQueuePush(MyQueue* obj, int x) {
  11.  
  12. }
  13.  
  14. int myQueuePop(MyQueue* obj) {
  15.  
  16. }
  17.  
  18. int myQueuePeek(MyQueue* obj) {
  19.  
  20. }
  21.  
  22. bool myQueueEmpty(MyQueue* obj) {
  23.  
  24. }
  25.  
  26. void myQueueFree(MyQueue* obj) {
  27.  
  28. }

6.3.1 整体思路：

老规矩我们先创造两个栈，其中一个依次输入1 2 3 4，要想实现队列的先进先出，那最终要Pop的数就是1.至此，我们可以沿用与上一题差不多的思路（先入栈，再出栈导到另一个栈，最后再处理1.）。

当我们把1Pop掉时再尝试Push5 6，把2 3 4导回去再入栈5 6继续重复上述操作是没问题的，那能不能不把2 3 4导回原来的栈呢？——这时候的情况就发生了变化：可以把2 3 4全部Pop掉，这样第二个栈就空了，再把5 6导入第二个栈最终可以Pop出5.

这时候我们就可以制定规则了

  • pushst栈: 这个栈只能用来入栈。
  • popst栈：这个栈只能用来出栈。

跟上题一样先搞出两个栈出来；

  1. MyQueue* myStackCreate() {
  2. 	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
  3. 	STInit(&obj->pushst);
  4. 	STInit(&obj->popst);
  5.  
  6. 	return obj;
  7. }

6.3.2 Push（入栈）函数

  1. void myQueuePush(MyQueue* obj, int x) {
  2. 	STPush(&obj->pushst, x);
  3. }

6.3.3 Peek(取头)函数

我们先来写Peek（获取头队列数据函数），要想获取首先得判断popst中是否为空，如果是空的我们需要从pushst中导出数据到popst里。这样才可以获取头队列数据。如果有友友对这里复用的函数命名不熟悉可以去目录对照查看。

  1. int myQueuePeek(MyQueue* obj) {
  2. 	//哪个队列不为空就去取该队列的尾部数据
  3. 	if (STEmpty(&obj->popst))
  4. 	{
  5. 		//判断popst为空，开始导入数据
  6. 		while (!STEmpty(&obj->pushst))
  7. 		{
  8. 			STPush(&obj->popst, STTop(&obj->pushst));//导入数据后再进行删除头队列数据
  9. 			STPop(&obj->pushst);//导进一个删除一个，清空pushst
  10. 		}
  11. 	}
  12. 	return STTop(&obj->popst);
  13. }

6.3.4 Pop（出栈）函数

到这一步我们就可以发现先写Peek的好处了，因为Peek已经先判断popst是否为空，为空就把pushst的数据搬过来，所以我们只需要处理好popst里面的数据就好了。

  1. int myQueuePop(MyQueue* obj)
  2. {
  3. 	int front = myQueuePeek(obj);//存储队列首个数据
  4. 	STPop(&obj->popst);//pop掉队列的头数据
  5. 	return front;//返回首个数据，达成用两个栈实现先进先出的队列
  6. }

6.3.5 Empty（判空）函数

  1. bool myQueueEmpty(MyQueue* obj) {
  2. 	return  QueueEmpty(&obj->pushst) && QueueEmpty(&obj->popst);
  3. }

6.3.6 Free（释放空间）函数

  1. void myQueueFree(MyQueue* obj) {
  2. 	STDestroy(&obj->pushst);
  3. 	STDestroy(&obj->popst);
  4. 	free(obj);
  5. }

6.3.7 全部代码

注：想要写题解或者测试，请自行添加上文关于Stack.h与Stack.c的代码段（下面代码能够复用的前提）

  1. typedef struct {
  2. 	ST pushst;
  3. 	ST popst;
  4. } MyQueue;
  5.  
  6.  
  7. MyQueue* myQueueCreate() {
  8. 	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
  9. 	STInit(&obj->pushst);
  10. 	STInit(&obj->popst);
  11.  
  12. 	return obj;
  13. }
  14.  
  15. void myQueuePush(MyQueue* obj, int x) {
  16. 	STPush(&obj->pushst, x);
  17. }
  18.  
  19.  
  20.  
  21. int myQueuePeek(MyQueue* obj) {
  22. 	//哪个队列不为空就去取该队列的尾部数据
  23. 	if (STEmpty(&obj->popst))
  24. 	{
  25. 		//判断popst为空，开始导入数据
  26. 		while (!STEmpty(&obj->pushst))
  27. 		{
  28. 			STPush(&obj->popst, STTop(&obj->pushst));//导入数据后再进行删除头队列数据
  29. 			STPop(&obj->pushst);//导进一个删除一个，清空pushst
  30. 		}
  31. 	}
  32. 	return STTop(&obj->popst);
  33. }
  34.  
  35. int myQueuePop(MyQueue* obj)
  36. {
  37. 	int front = myQueuePeek(obj);//存储队列首个数据
  38. 	STPop(&obj->popst);//pop掉队列的头数据
  39. 	return front;//返回首个数据，达成用两个栈实现先进先出的队列
  40. }
  41.  
  42.  
  43.  
  44.  
  45. bool myQueueEmpty(MyQueue* obj) {
  46. 	return  STEmpty(&obj->pushst) && STEmpty(&obj->popst);
  47. }
  48.  
  49. void myQueueFree(MyQueue* obj) {
  50. 	STDestroy(&obj->pushst);
  51. 	STDestroy(&obj->popst);
  52. 	free(obj);
  53. }

6.4 设计循环队列

链接：力扣——设计循环队列

  1. typedef struct {
  2.  
  3. } MyCircularQueue;
  4.  
  5.  
  6. MyCircularQueue* myCircularQueueCreate(int k) {
  7.  
  8. }
  9.  
  10. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  11.  
  12. }
  13.  
  14. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  15.  
  16. }
  17.  
  18. int myCircularQueueFront(MyCircularQueue* obj) {
  19.  
  20. }
  21.  
  22. int myCircularQueueRear(MyCircularQueue* obj) {
  23.  
  24. }
  25.  
  26. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  27.  
  28. }
  29.  
  30. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  31.  
  32. }
  33.  
  34. void myCircularQueueFree(MyCircularQueue* obj) {
  35.  
  36. }

图像示例：

循环原则：删除完数据front++,增加完数据rear++.

循环关键就是front到rear,虽然经过增删会改变它们的位置，但在定长数组中起点就是front，终点就是rear。但需要注意[front,rear)这是左闭右开的关系。因为rear插入数据后会指向下一位。

这里用数组实现比较轻松，用链表反而会很复杂。

  • 第一缺陷：用rear取队尾数据不好取，因为rear是每次插入数据后才往后移，如果想取队尾部那就得用到rear->pre了，这就变成了双向链表了。又或者再多给一个指针，变成3个指针。
  • 第二缺陷：不好判满，链表为空rear与front指向同一处，而只有一个数据时，还是指向同一处。
  • 第三缺陷：当链表满时rear又指向了与front一致的地方，与链表为空的情况一致，空与满判断不了。

所以为了解决这个问题，很多人选择多开一处空间，该空间不存储数据就为了让rear指到最后。

所以用链表始终存在一些问题，故而我们选择比链表适合一些的数组来实现。

6.4.1 整体思路：

这里判定满的条件就是rear+1，当rear的下标是4时可以想象+1就回到front的指向位置。所以最终的规律就是(rear+1)%(k+1)==front.

我们先来模拟一下增删：

当准备插入7时，只要我们的判满条件达成理论上是不会继续插入滴~我们继续删除数据~

当我们把6给删除后数组为空数组了，不能再继续删除了，而这时候我们发现front与rear相等，也满足了判空条件。

总结：实现循环链表的两个关键点

  • 判空：front==rear
  • 判满：（rear+1)%(k+1)==front

6.4.2 创造函数（Creat)

  1. typedef struct {
  2. 	int* a;//定义数组
  3. 	int front;//起点
  4. 	int rear;//终点
  5. 	int k;//有效数字
  6. } MyCircularQueue;
  7.  
  8.  
  9. MyCircularQueue* myCircularQueueCreate(int k) {
  10. 	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  11. 	//多开一个空间方便区分空和满
  12. 	obj->a = (int*)malloc(sizeof(int) * (k + 1));
  13. 	obj->front = obj->rear = 0;
  14. 	obj->k = k;
  15.     return obj;
  16. }

6.4.2 判空与判满函数（Is(Empty)/(Full))

  1. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  2. 	return obj->front == obj->rear;
  3. }
  4.  
  5. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  6. 	return (obj->rear + 1)%(obj->k+1) == obj->front;
  7. }

6.4.3 EnQueue(插入)函数

在三种插入情况中我们需要注意第三种：rear循环绕到开头。

  1. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  2. 	if (myCircularQueueIsFull(obj))//如果已经满了
  3. 	{
  4. 		return false;
  5. 	}
  6. 	//没满情况下
  7. 	obj->a[obj->rear] = value;
  8. 	obj->rear++;
  9.  
  10. 	obj->rear %= (obj->k + 1);
  11. 	//针对第三种情况当rear在下标4插入7时rear++变成5需要循环到头部
  12.  
  13. 	return true;
  14.  
  15. }

6.4.4 DeQueue（删除）函数

删除完数据front++，那front也会遇到跟上面rear一样的问题，当指向尾时再++需要循环绕到头部。

  1. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  2. 	if (myCircularQueueIsEmpty(obj))//如果已经是空的
  3. 	{
  4. 		return false;
  5. 	}
  6.  
  7. 	obj->front++;
  8. 	obj->front %= (obj->k + 1);
  9. 	return true;
  10. }

6.4.5 Front（取头）函数

  1. int myCircularQueueFront(MyCircularQueue* obj) {
  2. 	if (myCircularQueueIsEmpty(obj))//如果已经是空的
  3. 	{
  4. 		return -1;
  5. 	}
  6. 	else
  7. 	{
  8. 		return obj->a[obj->front];
  9. 	}
  10. }

6.4.6 rear（取尾）函数

取队尾函数就不像上面取队头那么好取了。正常的队尾取到rear-1就行，但如果是这种情况呢？取到-1该怎么办。

虽然可以通过if条件来判断并修改，但这里我们来引用一种巧妙的方法；

  1. int myCircularQueueRear(MyCircularQueue* obj) {
  2. 	if (myCircularQueueIsEmpty(obj))//如果已经是空的
  3. 	{
  4. 		return -1;
  5. 	}
  6. 	else
  7. 	{
  8. 		return obj->a[(obj->rear+obj->k)%(obj->k+1)];
  9. 	}
  10. }

6.4.7 Free（释放空间）函数

  1. void myCircularQueueFree(MyCircularQueue* obj) {
  2. 	free(obj->a);
  3. 	free(obj);
  4. }

6.4.8 全部代码

  1.  
  2.  
  3.  
  4. typedef struct {
  5. 	int* a;//定义数组
  6. 	int front;//起点
  7. 	int rear;//终点
  8. 	int k;//有效数字
  9. } MyCircularQueue;
  10.  
  11.  
  12. MyCircularQueue* myCircularQueueCreate(int k) {
  13. 	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  14. 	//多开一个空间方便区分空和满
  15. 	obj->a = (int*)malloc(sizeof(int) * (k + 1));
  16. 	obj->front = obj->rear = 0;
  17. 	obj->k = k;
  18. 	return obj;
  19. }
  20.  
  21. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  22. 	return obj->front == obj->rear;
  23. }
  24.  
  25. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  26. 	return (obj->rear + 1)%(obj->k+1) == obj->front;
  27. }
  28.  
  29.  
  30. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  31. 	if (myCircularQueueIsFull(obj))//如果已经满了
  32. 	{
  33. 		return false;
  34. 	}
  35. 	//没满情况下
  36. 	obj->a[obj->rear] = value;
  37. 	obj->rear++;
  38.  
  39. 	obj->rear %= (obj->k + 1);
  40. 	//针对第三种情况当rear在下标4插入7时rear++变成5需要循环到头部
  41.  
  42. 	return true;
  43.  
  44. }
  45.  
  46. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  47. 	if (myCircularQueueIsEmpty(obj))//如果已经是空的
  48. 	{
  49. 		return false;
  50. 	}
  51.  
  52. 	obj->front++;
  53. 	obj->front %= (obj->k + 1);
  54. 	return true;
  55. }
  56.  
  57. int myCircularQueueFront(MyCircularQueue* obj) {
  58. 	if (myCircularQueueIsEmpty(obj))//如果已经是空的
  59. 	{
  60. 		return -1;
  61. 	}
  62. 	else
  63. 	{
  64. 		return obj->a[obj->front];
  65. 	}
  66. }
  67.  
  68. int myCircularQueueRear(MyCircularQueue* obj) {
  69. 	if (myCircularQueueIsEmpty(obj))//如果已经是空的
  70. 	{
  71. 		return -1;
  72. 	}
  73. 	else
  74. 	{
  75. 		return obj->a[(obj->rear+ obj->k)%(obj->k+1)];
  76. 	}
  77. }
  78.  
  79.  
  80.  
  81. void myCircularQueueFree(MyCircularQueue* obj) {
  82. 	free(obj->a);
  83. 	free(obj);
  84. }

4b12323f94834afd9ec146a3c10df229.jpeg七.结语

其实队列和栈的实现我们看作单链表的部分实现，因为我们只需要完成二者特定的结构性质就行了。所以只要单链表学扎实，想实现还是很轻松滴~另外提一嘴，4道oj题非常重要！里面可以帮助我们更加深入理解栈和队列。最后感谢大家的观看，友友们能够学习到新的知识是额滴荣幸，期待我们下次相见~

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

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

  

闽ICP备14008679号