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

【LeetCode】栈和队列oj专题

作者：不正经 | 2024-05-21 20:50:59

赞

踩

【LeetCode】栈和队列oj专题

有不懂的地方一定要看看我往期文章哦！

个人主页：小八哥向前冲~_博客

所属专栏：数据结构【c语言】

注意：这些题目实现全部由c语言实现，解决这些问题需要用到栈和队列，如果对c语言实现栈和队列有问题的同学，可以看：队列的实现 和 栈的实现 俩篇文章哦！

目录

配括号问题

循环队列问题

用栈实现队列

用队列实现栈

配括号问题

题目：

详情：【LeetCode】配括号问题

思路：

我们将 '('     '['   '{'统称为左括号，将  ']'   ')'   '}'统称为右括号。

经过观察，这个配括号问题就是一个简单的配对问题。

我们遍历数组，将左括号全部入栈，然后一一出栈和数组中右括号进行配对。

实现代码的时候需要注意几点：

  • 如果数组里面没有左括号，只有右括号，则永远配不成功。
  • 如果出栈配对时，栈里最终还有左括号，也就是说右括号比左括号多，也配不成功。

代码：

  1. typedef char STDateType;
  2. //栈
  3. typedef struct stack
  4. {
  5. 	STDateType* a;
  6. 	int top;
  7. 	int capacity;
  8. }ST;
  9.  
  10. //栈的初始化和销毁
  11. void STInit(ST* p);
  12. void STDestroy(ST* p);
  13. //入栈，出栈
  14. void STpush(ST* p,STDateType x);
  15. void STpop(ST* p);
  16. //栈顶的数据
  17. STDateType STtop(ST* p);
  18. //栈的数据个数
  19. int STsize(ST* p);
  20. //判空
  21. bool STEmpty(ST* p);
  22. //栈的初始化和销毁
  23. void STInit(ST* p)
  24. {
  25. 	assert(p);
  26. 	p->a = NULL;
  27. 	p->capacity = 0;
  28. 	p->top = 0;
  29. }
  30. void STDestroy(ST* p)
  31. {
  32. 	assert(p);
  33. 	free(p->a);
  34. 	p->capacity = p->top = 0;
  35. }
  36. //入栈，出栈
  37. void STpush(ST* p, STDateType x)
  38. {
  39. 	assert(p);
  40. 	if (p->top == p->capacity)
  41. 	{
  42. 		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
  43. 		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
  44. 		if (tmp == NULL)
  45. 		{
  46. 			perror("realloc failed!");
  47. 			return;
  48. 		}
  49. 		p->a = tmp;
  50. 		p->capacity = newcapacity;
  51. 	}
  52. 	p->a[p->top++] = x;
  53. }
  54. void STpop(ST* p)
  55. {
  56. 	assert(p);
  57. 	//出栈的话要判断一下空的情况
  58. 	assert(!STEmpty(p));
  59. 	p->top--;
  60. }
  61. //栈顶的数据
  62. STDateType STtop(ST* p)
  63. {
  64. 	assert(p);
  65. 	//出栈的话要判断一下空的情况
  66. 	assert(!STEmpty(p));
  67. 	return p->a[p->top-1];
  68. }
  69. //栈的数据个数
  70. int STsize(ST* p)
  71. {
  72. 	assert(p);
  73. 	return p->top;
  74. }
  75. //判空
  76. bool STEmpty(ST* p)
  77. {
  78. 	assert(p);
  79. 	return p->top == 0;
  80. }
  81. bool isValid(char* s) {
  82.     ST st;
  83.     STInit(&st);
  84.     while(*s)
  85.     {
  86.         //左括号入栈
  87.         if(*s=='('||*s=='['||*s=='{')
  88.         {
  89.             STpush(&st,*s);
  90.         }
  91.         else
  92.         {
  93.             //如果一个左括号也没有，栈里面就没有数据，那么永远配不成功
  94.             if(STEmpty(&st))
  95.             {
  96.                 STDestroy(&st);
  97.                 return false;
  98.             }
  99.             char top=STtop(&st);
  100.             STpop(&st);
  101.             if(top=='('&&*s!=')'
  102.             ||top=='['&&*s!=']'
  103.             ||top=='{'&&*s!='}')
  104.             {
  105.                STDestroy(&st);
  106.                return false;
  107.             }
  108.         }
  109.         s++;
  110.     }
  111.     //如果出栈配对后，栈里还有左括号，那么也永远配不成功
  112.     bool ret=STEmpty(&st);
  113.     STDestroy(&st);
  114.     return ret;
  115. }

循环队列问题

题目：

详情：【LeetCode】循环队列的实现

思路：两种方法

方法一：

将这个循环队列看成循环数组。

由于队列的先进先出原则，我们可以定义三个变量：头变量，尾变量，数据个数变量。

我们简单推理知道：我们动态开辟k个数据，进队列，从尾插入数据，入队列，从头删除数据，出队列。

可是又有一个新的问题：如何判断这个循环数组里面是空还是满呢？

上图：

由此可知，我们判断不了满的情况和空的情况。

我们可以这样来解决：

  1. 定义一个size变量，记录数组数据个数。
  2. 多开辟一个数据空间。

我们主要介绍第二种解决方案。

那么如何判断空和满呢？

另外需要注意的是：

在入队列（tail++）时，tail可能会越界，也要取模运算，出队列（head++）时，head也可能越界，也要取模运算。

思路到了这里，还要最后一个问题：怎么访问尾队列数据和头队列数据呢?

我们访问头队列数据很容易，直接访问头变量就行，可是尾呢？

上图：

代码：

  1.  
  2.  
  3.  
  4. typedef struct {
  5.     int*a;
  6.     int head;
  7.     int tail;
  8.     int k;
  9. } MyCircularQueue;
  10.  
  11.  
  12. MyCircularQueue* myCircularQueueCreate(int k) {
  13.     MyCircularQueue*p=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  14.     //多开一个空间，解决判满判空冲突问题
  15.     p->a=(int*)malloc(sizeof(int)*(k+1));
  16.     p->head=p->tail=0;
  17.     p->k=k;
  18.     return p;
  19. }
  20. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  21.     return obj->head==obj->tail;
  22. }
  23.  
  24. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  25.     return (obj->tail+1)%(obj->k+1)==obj->head;
  26. }
  27. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  28.     if(myCircularQueueIsFull(obj))
  29.     {
  30.         return false;
  31.     }
  32.     obj->a[obj->tail]=value;
  33.     obj->tail++;
  34.     (obj->tail)%=(obj->k+1);
  35.     return true;
  36. }
  37.  
  38. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  39.     if(myCircularQueueIsEmpty(obj))
  40.     {
  41.         return false;
  42.     }
  43.     obj->head++;
  44.     (obj->head)%=(obj->k+1);
  45.     return true;
  46. }
  47.  
  48. int myCircularQueueFront(MyCircularQueue* obj) {
  49.     if(myCircularQueueIsEmpty(obj))
  50.     {
  51.         return -1;
  52.     }
  53.     else
  54.         return obj->a[obj->head];
  55. }
  56.  
  57. int myCircularQueueRear(MyCircularQueue* obj) {
  58.     if(myCircularQueueIsEmpty(obj))
  59.     {
  60.         return -1;
  61.     }
  62.     else
  63.         return obj->a[(obj->tail+obj->k)%(obj->k+1)];
  64.         //return obj->a[obj->tail==0?k:obj->tail-1];
  65. }
  66.  
  67. void myCircularQueueFree(MyCircularQueue* obj) {
  68.     free(obj->a);
  69.     free(obj);
  70. }
  71.

方法二

思路：

我们可以将这个循环队列看成循环链表。

定义三个指针变量：尾指针，头指针，尾指针的前一个指针。

进队列，从尾进，尾指针指向下一个，出队列，从头出，头指针指向下一个。

有了上一部分基础，我们判空判满依旧可以多开辟一个空间。

为什么要定义尾指针的前一个指针，只定义头指针和尾指针不行吗？

当我们访问尾队列数据时，可以直接用尾指针的前一个指针直接访问就行，省了一个循环找尾队列数据的遍历！

代码：

  1. typedef struct Node
  2. {
  3.     struct Node*next;
  4.     int val;
  5. }Node;
  6.  
  7. typedef struct {
  8.     Node*phead;
  9.     Node*ptail;
  10.     Node*preptail;
  11. } MyCircularQueue;
  12.  
  13.  
  14. MyCircularQueue* myCircularQueueCreate(int k) {
  15.     MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  16.     obj->phead=obj->ptail=NULL;
  17.     for(int i=0;i<k+1;i++)
  18.     {
  19.         Node*cur=(Node*)malloc(sizeof(Node));
  20.         cur->next=NULL;
  21.         if(obj->phead==NULL)
  22.         {
  23.             obj->phead=obj->ptail=cur;
  24.         }
  25.         else
  26.         {
  27.             obj->ptail->next=cur;
  28.             obj->ptail=cur;
  29.         }
  30.     }
  31.     obj->ptail->next=obj->phead;
  32.     obj->preptail=obj->ptail;
  33.     obj->ptail=obj->phead;
  34.     return obj;
  35. }
  36. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  37.     return obj->phead==obj->ptail;
  38. }
  39.  
  40. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  41.     return obj->ptail->next==obj->phead;
  42. }
  43.  
  44. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  45.     if(myCircularQueueIsFull(obj))
  46.     {
  47.         return false;
  48.     }
  49.     obj->ptail->val=value;
  50.     obj->ptail=obj->ptail->next;
  51.     obj->preptail=obj->preptail->next;
  52.     return true;
  53. }
  54.  
  55. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  56.     if(myCircularQueueIsEmpty(obj))
  57.     {
  58.         return false;
  59.     }
  60.     obj->phead=obj->phead->next;
  61.     return true;
  62. }
  63.  
  64. int myCircularQueueFront(MyCircularQueue* obj) {
  65.     if(myCircularQueueIsEmpty(obj))
  66.     {
  67.         return -1;
  68.     }
  69.     return obj->phead->val;
  70. }
  71.  
  72. int myCircularQueueRear(MyCircularQueue* obj) {
  73.     if(myCircularQueueIsEmpty(obj))
  74.     {
  75.         return -1;
  76.     }
  77.     return obj->preptail->val;
  78. }
  79.  
  80. void myCircularQueueFree(MyCircularQueue* obj) {
  81.     while(obj->phead!=obj->ptail)
  82.     {
  83.         Node*next=obj->phead->next;
  84.         free(obj->phead);
  85.         obj->phead=next;
  86.     }
  87.     free(obj);
  88. }

用栈实现队列

题目：

详情：【LeetCode】栈实现队列

思路：

我们可以将一个栈专门用来入数据的，另一个专门用来出数据的。

当出数据的栈为空时，还想出数据，将入数据的栈的数据全部导入出数据的栈，再继续出数据即可！

代码：

  1. typedef int STDateType;
  2. //栈
  3. typedef struct stack
  4. {
  5. 	STDateType* a;
  6. 	int top;
  7. 	int capacity;
  8. }ST;
  9.  
  10. //栈的初始化和销毁
  11. void STInit(ST* p);
  12. void STDestroy(ST* p);
  13. //入栈，出栈
  14. void STpush(ST* p,STDateType x);
  15. void STpop(ST* p);
  16. //栈顶的数据
  17. STDateType STtop(ST* p);
  18. //栈的数据个数
  19. int STsize(ST* p);
  20. //判空
  21. bool STEmpty(ST* p);
  22.  
  23.  
  24. //栈的初始化和销毁
  25. void STInit(ST* p)
  26. {
  27. 	assert(p);
  28. 	p->a = NULL;
  29. 	p->capacity = 0;
  30. 	p->top = 0;
  31. }
  32. void STDestroy(ST* p)
  33. {
  34. 	assert(p);
  35. 	free(p->a);
  36. 	p->capacity = p->top = 0;
  37. }
  38. //入栈，出栈
  39. void STpush(ST* p, STDateType x)
  40. {
  41. 	assert(p);
  42. 	if (p->top == p->capacity)
  43. 	{
  44. 		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
  45. 		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
  46. 		if (tmp == NULL)
  47. 		{
  48. 			perror("realloc failed!");
  49. 			return;
  50. 		}
  51. 		p->a = tmp;
  52. 		p->capacity = newcapacity;
  53. 	}
  54. 	p->a[p->top++] = x;
  55. }
  56. void STpop(ST* p)
  57. {
  58. 	assert(p);
  59. 	//出栈的话要判断一下空的情况
  60. 	assert(!STEmpty(p));
  61. 	p->top--;
  62. }
  63. //栈顶的数据
  64. STDateType STtop(ST* p)
  65. {
  66. 	assert(p);
  67. 	//出栈的话要判断一下空的情况
  68. 	assert(!STEmpty(p));
  69. 	return p->a[p->top-1];
  70. }
  71. //栈的数据个数
  72. int STsize(ST* p)
  73. {
  74. 	assert(p);
  75. 	return p->top;
  76. }
  77. //判空
  78. bool STEmpty(ST* p)
  79. {
  80. 	assert(p);
  81. 	return p->top == 0;
  82. }
  83.  
  84.  
  85. typedef struct {
  86.     ST pushst;
  87.     ST popst;
  88. } MyQueue;
  89.  
  90.  
  91. MyQueue* myQueueCreate() {
  92.     MyQueue*p=(MyQueue*)malloc(sizeof(MyQueue));
  93.     STInit(&(p->pushst));
  94.     STInit(&(p->popst));
  95.     return p;
  96. }
  97.  
  98. void myQueuePush(MyQueue* obj, int x) {
  99.     STpush(&(obj->pushst),x);
  100. }
  101.  
  102. int myQueuePop(MyQueue* obj) {
  103.     int top=myQueuePeek(obj);
  104.     STpop(&(obj->popst));
  105.     return top;
  106. }
  107.  
  108. int myQueuePeek(MyQueue* obj) {
  109.     if(STEmpty(&(obj->popst)))
  110.     {
  111.         while(!STEmpty(&(obj->pushst)))
  112.         {
  113.            STpush(&(obj->popst),STtop(&(obj->pushst)));
  114.            STpop(&(obj->pushst));
  115.         }
  116.     }
  117.     return STtop(&(obj->popst));
  118. }
  119.  
  120. bool myQueueEmpty(MyQueue* obj) {
  121.     return STEmpty(&(obj->pushst))&&STEmpty(&(obj->popst));
  122. }
  123.  
  124. void myQueueFree(MyQueue* obj) {
  125.     STDestroy(&(obj->pushst));
  126.     STDestroy(&(obj->popst));
  127.     free(obj);
  128. }

用队列实现栈

题目：

详情：【LeetCode】队列实现栈

思路：

我们可以将判断俩队列哪个为空队列，哪个不为空队列。

进栈时，入数据在不为空的队列里，出栈时，出数据时，需要将不为空队列的数据导入为空队列中去，然后再去出栈！

而判断哪个为空队列，我们可以用假设法！

代码：

  1. typedef int QDataType;
  2. //原则：先进先出
  3.  
  4. //队列
  5. typedef struct QueueNode
  6. {
  7. 	struct QueueNode* next;
  8. 	QDataType val;
  9. }QNode;
  10.  
  11. //管理队列的一些参数
  12. typedef struct Queue
  13. {
  14. 	QNode* phead;
  15. 	QNode* ptail;
  16. 	int size;//队列中数据的个数
  17. }Queue;
  18.  
  19. //参数初始化
  20. void QueueInit(Queue* pq);
  21. //入队   队尾入队
  22. void Queuepush(Queue* pq, QDataType x);
  23. //出队   队头出队
  24. void Queuepop(Queue* pq);
  25. //数据个数
  26. int Queuesize(Queue* pq);
  27. //队列判空
  28. bool QueueEmpty(Queue* pq);
  29. //队尾数据
  30. QDataType QueueBack(Queue* pq);
  31. //队头数据
  32. QDataType QueueFront(Queue* pq);
  33. //队列的销毁
  34. void QueueDestroy(Queue* pq);
  35.  
  36. //参数初始化
  37. void QueueInit(Queue* pq)
  38. {
  39. 	assert(pq);
  40. 	pq->phead = pq->ptail = NULL;
  41. 	pq->size = 0;
  42. }
  43. //入队   队尾入队
  44. void Queuepush(Queue* pq, QDataType x)
  45. {
  46. 	QNode* node = (QNode*)malloc(sizeof(QNode));
  47. 	if (node == NULL)
  48. 	{
  49. 		perror("malloc failed!");
  50. 		return;
  51. 	}
  52. 	node->next = NULL;
  53. 	node->val = x;
  54. 	//入队
  55. 	if (pq->ptail == NULL)
  56. 	{
  57. 		pq->phead = pq->ptail = node;
  58. 	}
  59. 	else
  60. 	{
  61. 		pq->ptail->next = node;
  62. 		pq->ptail = node;
  63. 	}
  64. 	//插入数据，数据个数增加
  65. 	pq->size++;
  66. }
  67.  
  68. //出队   队头出队
  69. void Queuepop(Queue* pq)
  70. {
  71. 	assert(pq);
  72. 	//队列不能为空
  73. 	assert(pq->size > 0);
  74. 	//当只有一个节点时，出队后，尾指针变成野指针！
  75. 	if (pq->phead->next == NULL)//一个节点
  76. 	{
  77. 		free(pq->phead);
  78. 		pq->phead = pq->ptail = NULL;
  79. 	}
  80. 	else//多个节点
  81. 	{
  82. 		QNode* next = pq->phead->next;
  83. 		free(pq->phead);
  84. 		pq->phead = next;
  85. 	}
  86. 	pq->size--;
  87. }
  88. //队尾数据
  89. QDataType QueueBack(Queue* pq)
  90. {
  91. 	assert(pq->size > 0);
  92. 	return pq->ptail->val;
  93. }
  94. //队头数据
  95. QDataType QueueFront(Queue* pq)
  96. {
  97. 	assert(pq->size != 0);
  98. 	return pq->phead->val;
  99. }
  100.  
  101. //数据个数
  102. int Queuesize(Queue* pq)
  103. {
  104. 	assert(pq);
  105. 	return pq->size;
  106. }
  107. //队列判空
  108. bool QueueEmpty(Queue* pq)
  109. {
  110. 	assert(pq);
  111. 	return pq->size == 0;
  112. }
  113. //队列的销毁
  114. void QueueDestroy(Queue* pq)
  115. {
  116. 	assert(pq);
  117. 	QNode* cur = pq->phead;
  118. 	while (cur)
  119. 	{
  120. 		QNode* next = cur->next;
  121. 		free(cur);
  122. 		cur = next;
  123. 	}
  124. 	pq->phead = pq->ptail = NULL;
  125. 	pq->size = 0;
  126. 	cur = NULL;
  127. }
  128.  
  129. typedef struct {
  130.     Queue q1;
  131.     Queue q2;
  132. } MyStack;
  133.  
  134.  
  135. MyStack* myStackCreate() {
  136.     MyStack*p=(MyStack*)malloc(sizeof(MyStack));
  137.     QueueInit(&(p->q1));
  138.     QueueInit(&(p->q2));
  139.     return p;
  140. }
  141.  
  142. void myStackPush(MyStack* obj, int x) {
  143.     if(!QueueEmpty(&(obj->q1)))
  144.     {
  145.         Queuepush(&(obj->q1),x);
  146.     }
  147.     else
  148.     {
  149.         Queuepush(&(obj->q2),x);
  150.     }
  151. }
  152.  
  153. int myStackPop(MyStack* obj) {
  154.     Queue*empty=&(obj->q1);
  155.     Queue*noempty=&(obj->q2);
  156.     if(!QueueEmpty(&(obj->q1)))
  157.     {
  158.         noempty=&(obj->q1);
  159.         empty=&(obj->q2);
  160.     }
  161.     while(Queuesize(noempty)>1)
  162.     {
  163.         Queuepush(empty,QueueFront(noempty));
  164.         Queuepop(noempty);
  165.     }
  166.     int front=QueueFront(noempty);
  167.     Queuepop(noempty);
  168.     return front;
  169. }
  170.  
  171. int myStackTop(MyStack* obj) {
  172.     if(!QueueEmpty(&(obj->q1)))
  173.     {
  174.         return QueueBack(&(obj->q1));
  175.     }
  176.     else
  177.     {
  178.         return QueueBack(&(obj->q2));
  179.     }
  180. }
  181.  
  182. bool myStackEmpty(MyStack* obj) {
  183.     return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2));
  184. }
  185.  
  186. void myStackFree(MyStack* obj) {
  187.     QueueDestroy(&(obj->q1));
  188.     QueueDestroy(&(obj->q2));
  189.     free(obj);
  190. }

这些题目你都掌握了吗？只要对链表和顺序表很熟悉，解决这种题目还是很轻松的！

我们下期见！

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

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

  

闽ICP备14008679号