• 猿创征文｜栈和队列OJ刷题

    前言

    作者：小蜗牛向前冲

    名言：我可以接收失败，但我不能接收放弃

     如果觉的博主的文章还不错的话，还请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

    为了提高自己编写代码的能力，特意开设刷题专题，记录自己刷题的思路和理解。欢迎❀大家的指正。

    在下面的解题中我们都用C语言实现。 

     1用队列实现栈

     在这里我们就是要将队列模拟实现成栈，我们知道队列是先进先出，栈是先进后出；那我们又如何实现呢?其实我们可以借助二个队列实现。下面我们借助图像来理解一下：

     

     首先我们建立二个队列p1,p2，我们可能理解为入栈我们就将入数据到p1处。

    其次，我们可以认为p2队列是用来中间存放数据的。

    这样我们就成功将5出栈了，如果要将4出栈，那么我们又得需要将p2中的数据倒入到p1中：

     这样我们就完成了4出栈。

    下面我们简单总结一下思路：

    1我们要建立二个队列经行模拟。

    2始终保持一个队列为空，在出栈时，将将n-1个数据都倒入到空队列中，那么留在另个队列的数据就可以直接出栈了。

    下面是完成的解题代码：

    1. typedef  int QDataType;
    2. //定义队列
    3. typedef struct QueueNode
    4. {
    5. 	QDataType data;//数据类型
    6. 	struct QueueNode* next;
    7. }QNode;
    8.  
    9. //定义指向头和尾的二个指针
    10. typedef struct Queue
    11. {
    12. 	QNode* head;
    13. 	QNode* tail;
    14. 	int size;
    15. }Queue;
    16.  
    17. //初始化
    18. void QueueInit(Queue* pq);
    19. //销毁
    20. void QueueDestroy(Queue* pq);
    21. //入队
    22. void QueuePush(Queue* pq, QDataType x);
    23. //出队
    24. void QueuePop(Queue* pq);
    25. //返回指向队头的数据的指针
    26. QDataType QueueFront(Queue* pq);
    27. //返回指向队尾的数据的指针
    28. QDataType QueueBack(Queue* pq);
    29. //判断队列是否为空
    30. bool QueueEmpty(Queue* pq);
    31. //返回队列的大小
    32. int QueueSize(Queue* pq);
    33.  
    34. //初始化
    35. void QueueInit(Queue* pq)
    36. {
    37. 	assert(pq);
    38. 	pq->head = pq->tail = NULL;
    39. 	pq->size = 0;
    40. }
    41.  
    42. //销毁
    43. void QueueDestroy(Queue* pq)
    44. {
    45. 	assert(pq);
    46. 	QNode* cur = pq->head;
    47. 	while (cur)
    48. 	{
    49. 		QNode* del = cur;
    50. 		cur = cur->next;//指向下个节点
    51. 		free(del);
    52. 	}
    53. 	pq->head = pq->tail = NULL;//防止出现野指针
    54. 	pq->size = 0;
    55. }
    56.  
    57. //入队
    58. void QueuePush(Queue* pq, QDataType x)
    59. {
    60. 	assert(pq);
    61. 	//申请节点
    62. 	QNode* newNode = (QNode*)malloc(sizeof(QNode));
    63. 	if (newNode==NULL)
    64. 	{
    65. 		perror("malloc fail");
    66. 		exit(-1);
    67. 	}
    68. 	else
    69. 	{
    70. 		newNode->data = x;
    71. 		newNode->next = NULL;
    72. 	}
    73. 	//队列为空
    74. 	if (pq->tail == NULL)
    75. 	{
    76. 		pq->head = pq->tail = newNode;
    77. 	}
    78. 	//不为空
    79. 	else
    80. 	{
    81. 		pq->tail->next = newNode;
    82. 		pq->tail = newNode;//tail指针指向newNode
    83. 	}
    84. 	pq->size++;
    85. }
    86.  
    87. //出队
    88. void QueuePop(Queue* pq)
    89. {
    90. 	assert(pq);
    91. 	//断言队列是否为空
    92. 	assert(!QueueEmpty(pq));
    93. 	//当队列中就一个数据时
    94. 	if (pq->head->next == NULL)
    95. 	{
    96. 		free(pq->head);
    97. 		pq->head = pq->tail = NULL;
    98. 	}
    99. 	else
    100. 	{
    101. 		QNode* del = pq->head;
    102. 		pq->head = pq->head->next;//头变为下个节点
    103. 		free(del);
    104. 		del = NULL;
    105. 	}
    106. 	pq->size--;
    107. }
    108.  
    109. //判断队列是否为空
    110. bool QueueEmpty(Queue* pq)
    111. {
    112. 	assert(pq);
    113. 	return pq->tail == NULL;
    114. }
    115.  
    116. //返回指向队头的数据的指针
    117. QDataType QueueFront(Queue* pq)
    118. {
    119. 	assert(pq);
    120. 	//断言队列是否为空
    121. 	assert(!QueueEmpty(pq));
    122. 	return pq->head->data;
    123. }
    124.  
    125. //返回指向队尾的数据的指针
    126. QDataType QueueBack(Queue* pq)
    127. {
    128. 	assert(pq);
    129. 	//断言队列是否为空
    130. 	assert(!QueueEmpty(pq));
    131. 	return pq->tail->data;
    132. }
    133.  
    134. //返回队列的大小
    135. int QueueSize(Queue* pq)
    136. {
    137. 	return pq->size;
    138. }
    139.  
    140. typedef struct {
    141.     Queue p1;//入栈
    142.     Queue p2;//出栈
    143.  
    144. } MyStack;
    145.  
    146.  
    147. MyStack* myStackCreate() {
    148.     	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    149.         //对栈初始化
    150.         QueueInit(&obj->p1);
    151.         QueueInit(&obj->p2);
    152.         return obj;
    153. }
    154.  
    155. void myStackPush(MyStack* obj, int x) {
    156.     //当p1为空时就将数据倒入
    157.     if(!QueueEmpty(&obj->p1))
    158.     {
    159.         QueuePush(&obj->p1,x);
    160.     }
    161.     else
    162.     {
    163.         QueuePush(&obj->p2,x);
    164.     }
    165.  
    166. }
    167.  
    168. int myStackPop(MyStack* obj) {
    169.     Queue* empty = &obj->p1;//假设p1为空
    170.     Queue* noEmpty = &obj->p2;
    171.     //如果p1队列为非空
    172.     if(!QueueEmpty(&obj->p1))
    173.     {
    174.         empty = &obj->p2;
    175.         noEmpty = &obj->p1;
    176.     }
    177.     //将非空队列中的N-1的数据都倒入到空队列中，那么原队列还剩的1个数据就是要返回的栈顶数据
    178.     while(QueueSize(noEmpty)>1)
    179.     {
    180.         QueuePush(empty,QueueFront(noEmpty));//入栈
    181.         QueuePop(noEmpty);//出栈
    182.     }
    183.     int top =  QueueFront(noEmpty);
    184.      QueuePop(noEmpty);//出栈
    185.     return top;
    186. }
    187.  
    188. int myStackTop(MyStack* obj) {
    189.     if(!QueueEmpty(&obj->p1))
    190.     {
    191.         return QueueBack(&obj->p1);
    192.     }
    193.     else
    194.     {
    195.         return QueueBack(&obj->p2);
    196.     }
    197. }
    198.  
    199. bool myStackEmpty(MyStack* obj) {
    200.     return QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2);
    201. }
    202.  
    203. void myStackFree(MyStack* obj) {
    204.      QueueDestroy(&obj->p1);
    205.      QueueDestroy(&obj->p2);
    206.      free(obj);
    207. }

     2 栈实现队列

    要用二个栈实现队列，这是很好实现的。

    为什么这么说呢？我们可以用栈PushST来模拟入队列，栈PopST模拟出队列。

    下面我们顺着这个思路来，来图解一下 1，2，3，4的入队列和出队列的过程。

    1数据入队列

     2 要出队列时，当PopST为空的时候，就将PushST的数据倒入到PopST中，然后直接出就行。

    完整代码：

    1. typedef  int STDataType;
    2. //定义栈
    3. typedef struct Stack
    4. {
    5. 	STDataType* arr;//数据类型
    6. 	int pos;//数组下标
    7. 	int capacity;//栈的容量
    8. }ST;
    9.  
    10. //初始化
    11. void StackInit(ST* ps);
    12. //销毁
    13. void StackDestroy(ST* ps);
    14. //入栈
    15. void StackPush(ST* ps, STDataType x);
    16. //出栈
    17. void StackPop(ST* ps);
    18. 显示返回栈顶数据
    19. STDataType StackTop(ST* ps);
    20. //判断栈是否为空
    21. bool StackEmpty(ST* ps);
    22. //返回栈的长度//初始化
    23. void StackInit(ST* ps)
    24. {
    25. 	assert(ps);
    26. 	ps->arr = NULL;//初始数组为空
    27. 	ps->pos = ps->capacity = 0;//初始为0
    28. }
    29.  
    30. //销毁
    31. void StackDestroy(ST* ps)
    32. {
    33. 	assert(ps);
    34. 	free(ps->arr);//arr是整个栈的地址
    35. 	ps->arr = NULL;
    36. 	ps->capacity = ps->pos = 0;
    37. }
    38.  
    39. //入栈
    40. void StackPush(ST* ps, STDataType x)
    41. {
    42. 	assert(ps);
    43. 	//判断栈的空间是否满
    44. 	if (ps->pos == ps->capacity)
    45. 	{
    46. 		//扩容
    47. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//扩2倍
    48. 		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
    49. 		if (tmp == NULL)
    50. 		{
    51. 			perror("reamlloc fail");
    52. 			exit(-1);
    53. 		}
    54. 		//跟新容量
    55. 		ps->arr = tmp;
    56. 		ps->capacity = newCapacity;
    57. 	}
    58. 	//入栈
    59. 	ps->arr[ps->pos] = x;
    60. 	ps->pos++;//下标++
    61. }
    62.  
    63. //出栈
    64. void StackPop(ST* ps)
    65. {
    66. 	assert(ps);
    67. 	//断言栈是否为空
    68. 	assert(!StackEmpty(ps));
    69. 	--ps->pos;
    70. }
    71.  
    72. //判断栈是否为空
    73. bool StackEmpty(ST* ps)
    74. {
    75. 	assert(ps);
    76. 	return ps->pos == 0;
    77. }
    78.  
    79. //显示返回栈顶数据
    80. STDataType StackTop(ST* ps)
    81. {
    82. 	assert(ps);
    83. 	//断言栈是否为空
    84. 	assert(!StackEmpty(ps));
    85. 	return  ps->arr[ps->pos - 1];//下标已经前移
    86. }
    87.  
    88. //返回栈的长度
    89. int StackSize(ST* ps)
    90. {
    91. 	assert(ps);
    92. 	return ps->pos;
    93. }
    94. int StackSize(ST* ps);
    95.  
    96. typedef struct {
    97. 	ST PushST;//入队列
    98. 	ST PopST;//出队列
    99. } MyQueue;
    100.  
    101.  
    102. MyQueue* myQueueCreate() {
    103. 	//为模拟的队列开辟空间
    104. 	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    105. 	//初始化
    106. 	StackInit(&obj->PushST);
    107. 	StackInit(&obj->PopST);
    108. 	return obj;
    109. }
    110.  
    111. void myQueuePush(MyQueue* obj, int x) {
    112. 	StackPush(&obj->PushST, x);
    113. }
    114. void PushSTTOPopST(MyQueue* obj)
    115. {
    116. 	//判断PopST是否为空
    117. 	if (StackEmpty(&obj->PopST))
    118. 	{
    119. 		while (!(StackEmpty(&obj->PushST)))
    120. 		{
    121. 			StackPush(&obj->PopST, StackTop(&obj->PushST));
    122. 			StackPop(&obj->PushST);
    123. 		}
    124. 	}
    125. }
    126.  
    127. int myQueuePop(MyQueue* obj) {
    128. 	//将PuahST中的元素都倒入PopST中
    129. 	PushSTTOPopST(obj);
    130. 	int fornt = StackTop(&obj->PopST);
    131. 	StackPop(&obj->PopST);
    132. 	return fornt;
    133. }
    134.  
    135. int myQueuePeek(MyQueue* obj) {
    136. 	//将PuahST中的元素都倒入PopST中
    137. 	PushSTTOPopST(obj);
    138. 	return StackTop(&obj->PopST);
    139.  
    140. }
    141.  
    142. bool myQueueEmpty(MyQueue* obj) {
    143. 	return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
    144. }
    145.  
    146. void myQueueFree(MyQueue* obj) {
    147. 	//销毁空间
    148. 	StackDestroy(&obj->PushST);
    149. 	StackDestroy(&obj->PushST);
    150. 	free(obj);
    151. }

     3 设计循环队列

     对于设计循环队列来说有二种思路：

    1 用数组实现

    2 用链表实现

     

     

    对于这二种思路，我会首选思路1，为什么会这么说呢？

    因为用链表实现循环队列，首先你要malloc多份空间，而且这样你还不好判断循环队列是否已满！

    所以：我会选择用思路1来为大家解题。

    此题有个重点：那就是如何判断队列是否以满。

    因为在对于空和满来说，队列中指针fornt和back都是指向同一个位置。

    那么我们这么去解决呢？

    我们有二个思路：

    1多开辟一块空间

    2用size标记队列的长度，当size==k时就满

    下面我们用思路1来解决：

     代码转换：

    1. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    2.     return (obj->back + 1) % obj->n == obj->fornt;
    3.  
    4. }

    完整代码：

    1. typedef struct {
    2.     int* arr;
    3.     int fornt;
    4.     int back;
    5.     int n;
    6.  
    7. } MyCircularQueue;
    8.  
    9.  
    10. MyCircularQueue* myCircularQueueCreate(int k) {
    11.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    12.     obj->arr = (int*)malloc(sizeof(int) * (k + 1));
    13.     obj->fornt = obj->back=0;
    14.     obj->n = k + 1;
    15.     return obj;
    16. }
    17.  
    18. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    19.     return obj->fornt == obj->back;
    20. }
    21.  
    22. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    23.     return (obj->back + 1) % obj->n == obj->fornt;
    24.  
    25. }
    26.  
    27. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    28.     if (myCircularQueueIsFull(obj))
    29.     {
    30.         return false;
    31.     }
    32.     obj->arr[obj->back] = value;
    33.     obj->back++;
    34.     //如果back指针已经指向尾，需要重新指向头
    35.     obj->back %= obj->n;
    36.     return true;
    37.  
    38. }
    39.  
    40. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    41.     if (myCircularQueueIsEmpty(obj))
    42.     {
    43.         return false;
    44.     }
    45.     obj->fornt++;
    46.     //如果fornt指针已经指向尾，需要重新指向头
    47.     obj->fornt %= obj->n;
    48.     return true;
    49. }
    50.  
    51. int myCircularQueueFront(MyCircularQueue* obj) {
    52.     if (myCircularQueueIsEmpty(obj))
    53.     {
    54.         return -1;
    55.     }
    56.     return obj->arr[obj->fornt];
    57. }
    58.  
    59. int myCircularQueueRear(MyCircularQueue* obj) {
    60.     if (myCircularQueueIsEmpty(obj))
    61.     {
    62.         return -1;
    63.     }
    64.     else if(obj->back==0)
    65.     return obj->arr[obj->n-1];
    66.     else
    67.     return obj->arr[obj->back-1];
    68.     // return obj->arr[(obj->back -1 + obj->n) % obj->n];
    69. }
    70.  
    71.  
    72.  
    73. void myCircularQueueFree(MyCircularQueue* obj) {
    74.     free(obj->arr);
    75.     free(obj);
    76.  
    77. }

  • 相关阅读:
    4.20.1 深度神经网络提高放射科医生在乳腺癌筛查中的表现
    【Python】Python 发布订阅模式实现松耦合
    Bootstrap前端开发框架（简介、版本、优点、使用、布局容器、栅格系统（栅格选项参数，列嵌套，列偏移，列排序，响应式工具））
    图像识别-YOLO V8安装部署-window-CPU-Pycharm
    【无标题】QCC 308x 518x 517x增加usb voice 32k采样率
    【flask】服务端获取客户端请求的文件
    【HTML5入门指北】第二篇 网页相关的标签
    如何将pdf转word？这几个软件可以做到文档格式转换
    八、JavaScript：事件监听器
    μC/OS-II---计时器管理1（os_tmr.c）
  • 原文地址：https://blog.csdn.net/qq_61552595/article/details/126796410