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

【万字详解栈和队列及其OJ题】_oj手动扩栈

作者：Gausst松鼠会 | 2024-05-25 06:32:38

赞

踩

oj手动扩栈

各位大佬们，今天分享的是栈和队列的实现以及相关OJ题，如果觉得不错的话能支持一下菜鸟吗？

目录

一 栈

1.1 栈的概念及结构

1.2 栈的实现

 二 队列

2.1队列的概念及结构

 2.2队列的实现

三 栈与队列的OJ练习

3.1 括号匹配问题

3.2 用队列实现栈

3.3 用栈实现队列

 3.4 设置循环队列

一 栈

1.1 栈的概念及结构


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

 

 

1.2 栈的实现

实现栈的方式一般有两种：顺序表和链表。

但用顺序表实现栈较为优，原因有如下：

1 栈都是从栈顶插入数据以及删除数据，用链表实现不好尾删（如果尾删时间复杂度为O(N)）

2 链表每次开辟空间时都会有消耗，而动态顺序表一次可以malloc几倍的空间大小
 

1cc9388784c74b2c84f827eea14b3a29.png

 接下来就用动态顺序表来实现栈：

1 结构体类型的声明：

  1. typedef int STDataType;
  2. typedef struct Stack
  3. {
  4. 	STDataType* a;
  5. 	int top;
  6. 	int capacity;
  7. }ST;

这里用了一个STDataType*的指针指向了一个动态开辟的空间，top记录栈顶的位置，以及空间容量的大小。

2 各接口函数的声明：

  1. void StackInit(ST* ps);
  2. void StackDestroy(ST* ps);
  3. bool StackEmpty(ST* ps);
  4. void StackPush(ST* ps, STDataType x);
  5. void StackPop(ST* ps);
  6. STDataType StackTop(ST* ps);

3 判断栈是否为空：

  1. bool StackEmpty(ST* ps)
  2. {
  3. 	return ps->top == 0;
  4. }

用其他方法也行，这种方法比较简单。

4 初始化栈：

  1. void StackInit(ST* ps)
  2. {
  3. 	assert(ps);
  4. 	ps->a = NULL;
  5. 	ps->capacity = ps->top = 0;
  6. }

5 销毁栈：

  1. void StackDestroy(ST* ps)
  2. {
  3. 	free(ps->a);
  4. 	ps->a = NULL;
  5. 	ps->capacity = ps->top = 0;
  6. }

6 入栈：

  1. void StackPush(ST* ps, STDataType x)
  2. {
  3. 	assert(ps);
  4. 	if (ps->capacity == ps->top)
  5. 	{
  6. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  7. 		STDataType* tmp =(STDataType*) realloc(ps->a, sizeof(STDataType)* newCapacity);
  8. 		if (tmp == NULL)
  9. 		{
  10. 			printf("realloc fail\n");
  11. 		}
  12. 		ps->a = tmp;
  13. 		ps->capacity = newCapacity;
  14. 	}
  15. 	ps->a[ps->top] = x;
  16. 	ps->top++;
  17. }

7 出栈：

  1. void StackPop(ST* ps)
  2. {
  3. 	assert(ps);
  4. 	assert(!StackEmpty(ps));
  5. 	ps->top--;
  6. }

删除时要注意当栈为空时就不要删除了。

8 得到栈顶的元素：

  1. STDataType stackTop(ST* ps)
  2. {
  3. 	return ps->a[ps->top-1];
  4. }

由于初始化时top置为0，而每次push完后top++,所以要得到栈顶的元素就必须让top-1，当然如果初始化时top置为-1，就不需要-1了，但是push数据的代码也得做出相应的调整。

我们可以用个测试函数来测试一下上面接口是否有误：

bf7955e25d75483b8232614573b11339.png

 经过分析可知应该是没多大问题的。写这种多种接口的最好的方法是写完一个就测试一个，这样出了问题也能更快的调试分析出来问题所在。

是不是感觉栈其实也没有那么难，这些玩法都是我们之前顺序表和链表玩过的，下面我们来做两个栈的概念题来巩固一下：

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的
顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
 

这个题选B，没啥好说的

4.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
 

 这种题就一个一个带入，首先看A ：1进栈然后出栈，然后2 3 4，进栈，以4 3 2出栈，符合题意。B ： 1 2进栈，2出栈，3 4进栈，以3 4 1出栈，符合题意。 C： 1 2 3进栈，3出栈，4进栈，但是出栈必须是4先出，所以不符合。 D： 1 2 3进栈，3出栈，4进栈，4出栈，最后2 1出栈，符合题意。所以本题选C

 二 队列

2.1队列的概念及结构

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

fd251b0ddfdd4192b47c4c2d9e36b15c.png

 2.2队列的实现


与栈类似，队列也可以数组和链表的结构实现，但是队列使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

 

 接下来就用顺序表实现队列：

1 结构体类型的声明：

  1. typedef int QDataType;
  2. typedef struct QueueNode
  3. {
  4. 	QDataType val;
  5. 	struct QueueNode* next;
  6. }QueueNode;
  7.  
  8. typedef struct Queue
  9. {
  10. 	QueueNode* head;
  11. 	QueueNode* tail;
  12.     int sz;
  13. }Queue;

这里定义了一个tail的目的是为了更方便在队尾删除数据，而通常定义两个不同的量我们又喜欢放在一个结构体上。

2 各接口函数的声明：

  1. bool QueueEmpty(Queue* pq);
  2. void QueueInit(Queue* pq);
  3. void QueueDestroy(Queue* pq);
  4. void QueuePush(Queue* pq, QDataType x);
  5. void QueuePop(Queue* pq);
  6. QDataType QueueFront(Queue* pq);
  7. QDataType QueueBack(Queue* pq);
  8. int QueueSize(Queue* pq);

3 判断队列是否为空：

  1. bool QueueEmpty(Queue* pq)
  2. {
  3. 	return pq->head == NULL && pq->tail == NULL;
  4. }

 只要有一个不为空那么队列就不为空，所以用&&。

4 初始化队列：

  1. void QueueInit(Queue* pq)
  2. {
  3. 	assert(pq);
  4. 	pq->head = NULL;
  5. 	pq->tail = NULL;
  6. }

5 销毁队列：

  1. void QueueDestroy(Queue* pq)
  2. {
  3. 	assert(pq);
  4. 	QueueNode* cur = pq->head;
  5. 	while (cur)
  6. 	{
  7. 		QueueNode* next = cur->next;
  8. 		free(cur);
  9. 		cur = next;
  10. 	}
  11. 	pq->head = pq->tail = NULL;
  12. }

销毁栈最后别忘了将head和tail置为空，否则就留下了隐患。

6 队尾入数据：

  1. void QueuePush(Queue* pq, QDataType x)
  2. {
  3. 	assert(pq);
  4. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  5. 	newnode->val = x;
  6. 	newnode->next = NULL;
  7. 	if (pq->head == NULL)
  8. 	{
  9. 		pq->head = pq->tail = newnode;
  10. 	}
  11. 	else
  12. 	{
  13. 		pq->tail->next = newnode;
  14. 		pq->tail = newnode;
  15. 	}
  16.     pq->sz++;
  17. }

这里要讨论head和tail都为空的情况，否则就会出错。

7 队头删数据：

  1. void QueuePop(Queue* pq)
  2. {
  3. 	assert(pq);
  4. 	assert(!QueueEmpty(pq));
  5. 	QueueNode* next = pq->head->next;
  6. 	free(pq->head);
  7. 	pq->head = next;
  8. 	if (pq->head == NULL)
  9. 	{
  10. 		pq->tail = NULL;
  11. 	}
  12.     pq->sz--;
  13. }

同理删除数据时队列不能为空，但是要注意当head为空时也要把tail置为空，这样才能避免对野指针的访问。

8 得到队头元素：

  1. QDataType QueueFront(Queue* pq)
  2. {
  3. 	assert(pq);
  4. 	assert(!QueueEmpty(pq));
  5. 	return pq->head->val;
  6. }

同理，队头不能为空。

9 得到队尾元素：

  1. QDataType QueueBack(Queue* pq)
  2. {
  3. 	assert(pq);
  4. 	assert(!QueueEmpty(pq));
  5. 	return pq->tail->val;
  6. }

10 队列长度：

  1. int QueueSize(Queue* pq)
  2. {
  3. 	assert(pq);
  4. 	return pq->sz;
  5. }

我们可以测试一下接口是否有误：

350ac0f177524aa4864fa86a3e5f6625.png

三 栈与队列的OJ练习

3.1 括号匹配问题

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
 

示例 1：

输入：s = "()"
输出：true


示例 2：

输入：s = "()[]{}"
输出：true


示例 3：

输入：s = "(]"
输出：false


示例 4：

输入：s = "([)]"
输出：false


示例 5：

输入：s = "{[]}"
输出：true
 

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

解题思路：

这是一个经典用栈解决问题的题目，先让左括号入栈，当取到右括号时就出栈，拿这个左括号与右括号匹配，若能够成功匹配就接着迭代，否则就返回false,当全部元素都取完了的时候都没有返回false时就返回true.但是还要考虑栈不为空的情况。

具体代码：

  1. typedef char STDataType;
  2. typedef struct Stack
  3. {
  4. 	STDataType* a;
  5. 	int top;
  6. 	int capacity;
  7. }ST;
  8.  
  9. void StackInit(ST* ps);
  10. void StackDestroy(ST* ps);
  11. void StackPush(ST* ps, STDataType x);
  12. void StackPop(ST* ps);
  13. STDataType StackTop(ST* ps);
  14. bool StackEmpty(ST* ps);
  15.  
  16. void StackInit(ST* ps)
  17. {
  18. 	assert(ps);
  19. 	ps->a = NULL;
  20. 	ps->capacity = ps->top = 0;
  21. }
  22.  
  23. void StackDestroy(ST* ps)
  24. {
  25. 	free(ps->a);
  26. }
  27.  
  28. void StackPush(ST* ps, STDataType x)
  29. {
  30. 	assert(ps);
  31. 	if (ps->capacity == ps->top)
  32. 	{
  33. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  34. 		STDataType* tmp =(STDataType*) realloc(ps->a, sizeof(STDataType)* newCapacity);
  35. 		if (tmp == NULL)
  36. 		{
  37. 			printf("realloc fail\n");
  38. 		}
  39. 		ps->a = tmp;
  40. 		ps->capacity = newCapacity;
  41. 	}
  42. 	ps->a[ps->top] = x;
  43. 	ps->top++;
  44. }
  45.  
  46. void StackPop(ST* ps)
  47. {
  48. 	assert(ps);
  49. 	ps->top--;
  50. }
  51.  
  52. STDataType StackTop(ST* ps)
  53. {
  54. 	return ps->a[ps->top-1];
  55. }
  56.  
  57.  
  58. bool StackEmpty(ST* ps)
  59. {
  60. 	return ps->top == 0;
  61. }
  62.  
  63. bool isValid(char * s)
  64. {
  65.     ST ps;
  66. 	StackInit(&ps);
  67.     //遍历
  68.     while(*s)
  69.       {
  70.         if(*s=='(' || *s=='[' || *s=='{')
  71.          {
  72.             StackPush(&ps,*s);
  73.             s++;
  74.          }
  75.         else
  76.           {//遇到了右括号，但是栈里面没有数据，说明前面没有左括号，不匹配返回false
  77.               if(StackEmpty(&ps))
  78.               {
  79.                     StackDestroy(&ps);//返回前记得销毁，否则造成内存泄漏
  80.                     return false; 
  81.               }
  82.              STDataType top=StackTop(&ps);
  83.              StackPop(&ps);
  84.              //这里用不匹配来判断更为方便
  85.              if((*s==')' && top!='(')
  86.              || (*s==']' && top!='[')
  87.              || (*s=='}' && top!='{'))
  88.                  {
  89.                     StackDestroy(&ps);//返回前记得销毁，否则造成内存泄漏
  90.                     return false; 
  91.                  }
  92.                  s++;
  93.           }
  94.        }
  95.        //如果栈不是为空就返回false
  96.       bool ret=StackEmpty(&ps);
  97.        StackDestroy(&ps);//返回前记得销毁，否则造成内存泄漏
  98.        return ret;
  99. }

题中值得注意的地方我都用了注释进行了说明，一定要注意否则代码可能就会编不过。

73847f9797144517870509b790fc4c63.png

3.2 用队列实现栈

题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]


输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
 

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
 

解题思路：

让其中一个空队列保存数据，然后再让该队列一个一个从队头出数据保存到另外一个队列中，直至最后一个数据，再pop掉，然后迭代下去。

具体代码实现：

  1. typedef int QDataType;
  2. typedef struct QueueNode
  3. {
  4. 	QDataType val;
  5. 	struct QueueNode* next;
  6. }QueueNode;
  7.  
  8. typedef struct Queue
  9. {
  10. 	QueueNode* head;
  11. 	QueueNode* tail;
  12. }Queue;
  13.  
  14. void QueueInit(Queue* pq);
  15. void QueuePush(Queue* pq, QDataType x);
  16. void QueueDestroy(Queue* pq);
  17. void QueuePop(Queue* pq);
  18. QDataType QueueFront(Queue* pq);
  19. QDataType QueueBack(Queue* pq);
  20. int QueueSize(Queue* pq);
  21. bool QueueEmpty(Queue* pq);
  22.  
  23. void QueueInit(Queue* pq)
  24. {
  25. 	assert(pq);
  26. 	pq->head = NULL;
  27. 	pq->tail = NULL;
  28. }
  29.  
  30. void QueuePush(Queue* pq, QDataType x)
  31. {
  32. 	assert(pq);
  33. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  34. 	newnode->val = x;
  35. 	newnode->next = NULL;
  36. 	if (pq->head == NULL)
  37. 	{
  38. 		pq->head = pq->tail = newnode;
  39. 	}
  40. 	else
  41. 	{
  42. 		pq->tail->next = newnode;
  43. 		pq->tail = newnode;
  44. 	}
  45.  
  46. }
  47.  
  48. void QueueDestroy(Queue* pq)
  49. {
  50. 	assert(pq);
  51. 	QueueNode* cur = pq->head;
  52. 	while (cur)
  53. 	{
  54. 		QueueNode* next = cur->next;
  55. 		free(cur);
  56. 		cur = next;
  57. 	}
  58. 	pq->head = pq->tail = NULL;
  59. }
  60.  
  61. bool QueueEmpty(Queue* pq)
  62. {
  63. 	return pq->head == NULL && pq->tail == NULL;
  64. }
  65.  
  66. void QueuePop(Queue* pq)
  67. {
  68. 	assert(pq);
  69. 	assert(!QueueEmpty(pq));
  70. 	QueueNode* next = pq->head->next;
  71. 	free(pq->head);
  72. 	pq->head = next;
  73. 	if (pq->head == NULL)
  74. 	{
  75. 		pq->tail = NULL;
  76. 	}
  77. }
  78.  
  79.  
  80. QDataType QueueFront(Queue* pq)
  81. {
  82. 	assert(pq);
  83. 	assert(!QueueEmpty(pq));
  84.     return pq->head->val;
  85. }
  86.  
  87. QDataType QueueBack(Queue* pq)
  88. {
  89. 	assert(pq);
  90. 	assert(!QueueEmpty(pq));
  91. 	return pq->tail->val;
  92. }
  93.  
  94. int QueueSize(Queue* pq)
  95. {
  96. 	assert(pq);
  97. 	if (QueueEmpty(pq))
  98. 		return 0;
  99. 	QueueNode* cur = pq->head;
  100. 	int count = 0;
  101. 	while (cur)
  102. 	{
  103. 		count++;
  104. 		cur = cur->next;
  105. 	}
  106. 	return count;
  107. }
  108.  
  109. typedef struct {
  110. Queue q1;
  111. Queue q2;
  112. } MyStack;
  113.  
  114. MyStack* myStackCreate() {
  115. MyStack* tmp=(MyStack*)malloc(sizeof(MyStack));
  116.  
  117.  
  118.     QueueInit(&tmp->q1);
  119.     QueueInit(&tmp->q2);
  120.     return tmp;
  121.  
  122. }
  123.  
  124. void myStackPush(MyStack* obj, int x) {
  125. if(QueueEmpty(&obj->q1))
  126. {
  127.      QueuePush(&obj->q2,x);
  128. }
  129. else
  130. {
  131.      QueuePush(&obj->q1,x);    
  132. }
  133. }
  134.  
  135. int myStackPop(MyStack* obj) {
  136. Queue* emptyQ=&obj->q1;
  137. Queue* unemptyQ=&obj->q2;
  138. if(QueueEmpty(&obj->q2))
  139. {
  140.      emptyQ=&obj->q2;
  141.      unemptyQ=&obj->q1;
  142. }
  143. while(QueueSize(unemptyQ)>1)
  144. {
  145.     QueuePush(emptyQ,QueueFront(unemptyQ));
  146.     QueuePop(unemptyQ);
  147. }
  148. int top=QueueFront(unemptyQ);
  149. QueuePop(unemptyQ);
  150. return top;
  151. }
  152.  
  153. int myStackTop(MyStack* obj) {
  154. if(!QueueEmpty(&obj->q1))
  155. return QueueBack(&obj->q1);
  156. else
  157. return QueueBack(&obj->q2);
  158. }
  159.  
  160. bool myStackEmpty(MyStack* obj) {
  161. return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
  162. }
  163.  
  164. void myStackFree(MyStack* obj) {
  165. QueueDestroy(&obj->q1);
  166. QueueDestroy(&obj->q2);
  167. free(obj);
  168. obj=NULL;
  169. }
  170.  
  171. /**
  172.  * Your MyStack struct will be instantiated and called as such:
  173.  * MyStack* obj = myStackCreate();
  174.  * myStackPush(obj, x);
  175.  
  176.  * int param_2 = myStackPop(obj);
  177.  
  178.  * int param_3 = myStackTop(obj);
  179.  
  180.  * bool param_4 = myStackEmpty(obj);
  181.  
  182.  * myStackFree(obj);
  183. */

这里面分装了两个队列q1和q2,具体如何初始化 push pop可以参照上面我写的接口，free时记得把q1和q2都destroy掉，不然会造成内存泄漏。

b32aab0efdb441bbb8aa95a00fb11ffa.png

3.3 用栈实现队列

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false


说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]


输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
 

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
 

解题思路;

与用队列实现栈相同，我们仍然要分装两个栈pushSt和popSt,往pushSt中push数据，当pop时就把pushSt中的数据一个一个导过去，此时popST中数据就符合先进后出。

具体代码实现：

  1. typedef int STDataType;
  2. typedef struct Stack
  3. {
  4. 	STDataType* a;
  5. 	int top;
  6. 	int capacity;
  7. }ST;
  8.  
  9. void StackInit(ST* ps);
  10. void StackDestroy(ST* ps);
  11. void StackPush(ST* ps, STDataType x);
  12. void StackPop(ST* ps);
  13. STDataType StackTop(ST* ps);
  14. bool StackEmpty(ST* ps);
  15.  
  16. void StackInit(ST* ps)
  17. {
  18. 	assert(ps);
  19. 	ps->a = NULL;
  20. 	ps->capacity = ps->top = 0;
  21. }
  22.  
  23. void StackDestroy(ST* ps)
  24. {
  25. 	free(ps->a);
  26. 	ps->a = NULL;
  27. 	ps->capacity = ps->top = 0;
  28. }
  29.  
  30. bool StackEmpty(ST* ps)
  31. {
  32. 	return ps->top == 0;
  33. }
  34.  
  35. void StackPush(ST* ps, STDataType x)
  36. {
  37. 	assert(ps);
  38. 	if (ps->capacity == ps->top)
  39. 	{
  40. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  41. 		STDataType* tmp =(STDataType*) realloc(ps->a, sizeof(STDataType)* newCapacity);
  42. 		if (tmp == NULL)
  43. 		{
  44. 			printf("realloc fail\n");
  45. 		}
  46. 		ps->a = tmp;
  47. 		ps->capacity = newCapacity;
  48. 	}
  49. 	ps->a[ps->top] = x;
  50. 	ps->top++;
  51. }
  52.  
  53. void StackPop(ST* ps)
  54. {
  55. 	assert(ps);
  56. 	assert(!StackEmpty(ps));
  57. 	ps->top--;
  58. }
  59.  
  60. STDataType StackTop(ST* ps)
  61. {
  62. 	return ps->a[ps->top-1];
  63. }
  64. typedef struct {
  65. ST pushSt;
  66. ST popSt;
  67. } MyQueue;
  68.  
  69.  
  70. MyQueue* myQueueCreate() {
  71.  
  72. MyQueue *ps=(MyQueue*)malloc(sizeof(MyQueue));
  73. StackInit(&ps->pushSt);
  74. StackInit(&ps->popSt);
  75. return ps;
  76. }
  77.  
  78. void myQueuePush(MyQueue* obj, int x) {
  79. StackPush(&obj->pushSt,x);
  80. }
  81.  
  82. int myQueuePop(MyQueue* obj) 
  83. {
  84.     //如果popST为空就将pushST中的数据导入进去，
  85.     //此时popST中数据就符合先进后出
  86. if(StackEmpty(&obj->popSt))
  87. {
  88.     while(!StackEmpty(&obj->pushSt))
  89.     {
  90.          StackPush(&obj->popSt,StackTop(&obj->pushSt));
  91.          StackPop(&obj->pushSt);
  92.     }
  93. }
  94.     int front=StackTop(&obj->popSt);
  95.     StackPop(&obj->popSt);
  96.     return front;
  97.  
  98. }
  99.  
  100. int myQueuePeek(MyQueue* obj) {
  101. if(StackEmpty(&obj->popSt))
  102. {
  103.     while(!StackEmpty(&obj->pushSt))
  104.     {
  105.          StackPush(&obj->popSt,StackTop(&obj->pushSt));
  106.          StackPop(&obj->pushSt);
  107.     }  
  108. }
  109. return StackTop(&obj->popSt);
  110. }
  111. bool myQueueEmpty(MyQueue* obj) {
  112. return StackEmpty(&obj->pushSt) && StackEmpty(&obj->popSt);
  113. }
  114.  
  115. void myQueueFree(MyQueue* obj) {
  116. StackDestroy(&obj->pushSt);
  117. StackDestroy(&obj->popSt);
  118. free(obj);
  119. }
  120.  
  121. /**
  122.  * Your MyQueue struct will be instantiated and called as such:
  123.  * MyQueue* obj = myQueueCreate();
  124.  * myQueuePush(obj, x);
  125.  
  126.  * int param_2 = myQueuePop(obj);
  127.  
  128.  * int param_3 = myQueuePeek(obj);
  129.  
  130.  * bool param_4 = myQueueEmpty(obj);
  131.  
  132.  * myQueueFree(obj);
  133. */

结果展示：

b85ec3f71be54562975c22433a51d538.png

 3.4 设置循环队列

再介绍该题之前我们得了解一下什么是循环队列？

 

 

循环队列无论使用数组实现还是链表实现，较优的方法是多开辟一个空间，否则就无法实现判空和判满。（当然你用一个整形变量记录当前有效数据长度也是可行的，只不过用多开一个单位这种方法比较优）

题目描述：

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
 

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4
 

提示：

所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。

解题思路：

这个题用链表和数组都可以，这儿用的是数组解题（这个题用数组比链表简单不少），让front和tail分别指向相对数据的头和尾，但是要注意当front和tail超过了k+1时的处理方法，可以用判断，也可以用%来处理。如果是在搞不懂%,用判断也是一种比较好的方法。

具体代码：

  1. typedef struct {
  2. 	int* a;
  3. 	int front;
  4. 	int tail;
  5. 	int k;
  6. } MyCircularQueue;
  7.  
  8. bool myCircularQueueIsEmpty(MyCircularQueue* obj);
  9. bool myCircularQueueIsFull(MyCircularQueue* obj);
  10.  
  11. MyCircularQueue* myCircularQueueCreate(int k) {
  12. 	MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  13. 	cq->a = (int*)malloc(sizeof(int) * (k + 1));
  14. 	cq->front = cq->tail = 0;
  15. 	cq->k = k;
  16. 	return cq;
  17. }
  18.  
  19. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  20. 	if (myCircularQueueIsFull(obj))
  21. 		return false;
  22. 	obj->a[obj->tail] = value;
  23. 	obj->tail++;
  24. 	obj->tail %= (obj->k + 1);
  25. 	return true;
  26. }
  27.  
  28. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  29. 	if (myCircularQueueIsEmpty(obj))
  30. 		return false;
  31. 	obj->front++;
  32. 	obj->front %= (obj->k + 1);
  33. 	return true;
  34. }
  35.  
  36. int myCircularQueueFront(MyCircularQueue* obj) {
  37. 	if (myCircularQueueIsEmpty(obj))
  38. 		return -1;
  39. 	return obj->a[obj->front];
  40. }
  41.  
  42. int myCircularQueueRear(MyCircularQueue* obj) {
  43. 	if (myCircularQueueIsEmpty(obj))
  44. 		return -1;
  45. 	if (obj->tail == 0)
  46. 		return obj->a[obj->k];
  47. 	else
  48. 		return obj->a[obj->tail - 1];
  49. }
  50.  
  51. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  52. 	return obj->front == obj->tail;
  53. }
  54.  
  55. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  56. 	return (obj->tail + 1) % (obj->k + 1) == obj->front;
  57. }
  58.  
  59. void myCircularQueueFree(MyCircularQueue* obj) {
  60. 	free(obj->a);
  61. 	obj->a = NULL;
  62. 	free(obj);
  63. }
  64.  
  65. /**
  66.  * Your MyCircularQueue struct will be instantiated and called as such:
  67.  * MyCircularQueue* obj = myCircularQueueCreate(k);
  68.  * bool param_1 = myCircularQueueEnQueue(obj, value);
  70.  * bool param_2 = myCircularQueueDeQueue(obj);
  72.  * int param_3 = myCircularQueueFront(obj);
  74.  * int param_4 = myCircularQueueRear(obj);
  76.  * bool param_5 = myCircularQueueIsEmpty(obj);
  78.  * bool param_6 = myCircularQueueIsFull(obj);
  80.  * myCircularQueueFree(obj);
  81. */

结果展示：

8fb5b5560a12487ebfb7e6e0fe92082b.png

好了，今天的分享就到这里了，如果觉得该文对你有帮助的话能不能支持一下博主呢？

16cc7067dd7943aa87ed59fe672e571f.png

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

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

  

闽ICP备14008679号