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

【初阶数据结构】栈和队列（附题目）

作者：凡人多烦事01 | 2024-05-31 20:04:34

赞

踩

【初阶数据结构】栈和队列（附题目）

目录

1.栈

1.1栈的概念及结构

1.2栈的实现

1.2.2实现结构的选择

a.数组

b.链表

c.更优的选择

1.2.3实现结构

a.栈的结构体

b.栈的初始化

c.栈的销毁

d.入栈

e.出栈 

f.获取栈顶元素

g.获取栈中有效元素个数 

h.检测队列是否为空，如果为空返回非零结果，如果非空返回0 

2.队列

2.1队列的概念及结构

2.2队列的实现

2.2.1.实现结构的选择

2.2.2.实现结构的选择

a.单个队列节点的结构体

b.维护队列的结构体

c.队列的初始化

d.销毁队列 

e.队尾入队列 

f.队头出队列 

g.获取队列头部元素 

h.获取队列队尾元素

i.获取队列中有效元素个数

j.检测队列是否为空，如果为空返回非零结果，如果非空返回0 

3.栈和队列面试题

1. 括号匹配问题。OJ链接

2. 用队列实现栈。OJ链接

3. 用栈实现队列。OJ链接

4. 设计循环队列。OJ链接

4.概念选择题

4.1题目

4.2答案

5.附录源码：

5.1栈：

Stack.h

Stack.c

5.2队列

Queue.h

Queue.c

1.栈

1.1栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈在逻辑上仍然是线性的，但是与顺序表、链表不同，栈只能在栈顶入数据，在栈底出数据，不能在任意位置进行操作，栈顶与栈底是根据功能命名的，没有严格规定首部是栈顶，尾部是栈底。

1.2栈的实现

1.2.2实现结构的选择

在数据结构之前的学习中，我们已经学习了链式与数组这两种存储的结构，栈的实现一般都可以使用数组或者链表实现。相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。

a.数组

对于数组而言，如果我们将头部作为栈底，那么压栈出栈就需要挪动许多数据，算法复杂度为较大，因此我们一般将数组头部作为栈顶，尾部作为栈底.

b.链表

与数组不同，对于单链表而言，如果我们将链表的尾部作为栈底，我们是无法直接访问链表尾部的，同时进行压栈、出栈时，我们还需要找到尾节点的前一个节点，这样使用链表构建栈就会相当麻烦，读者读到这里，可能会认为找前一个节点麻烦，这是由于单链表结构的固有缺陷导致的，那我们直接使用双向链表，不就好了吗？确实，找前一个节点不麻烦了，但是为了解决这个问题，使用了双向链表，那么我们每个节点就多出一个需要维护的节点，空间损耗就大了，而且找尾节点还是需要遍历的，总得来说，我们花费的代价就太大了。因此将链表的尾部作为栈底并不是一个明智的选择。因此我们还是使用单链表（不带头），只不过将单链表第一个有效节点处，作为栈顶。这样我们进行压栈、出栈就方便了。

c.更优的选择

数组与链表两种结构看上去各有千秋，不过，实际上有数组去实现栈会更优一些。有的读者可能会认为如果是动态开辟数组的话，不是会有扩容上的消耗吗？同时不是还有将数据迁移到新的空间上的消耗吗？确实，如果仅看这些，按需申请的链表似乎更优一些，但是扩容调用的是系统上的资源，运行很快，并且一次扩容都是按倍扩，扩容的次数并不会很多，更重要的是数组的CPU的高速缓存更好（涉及知识点较多，这里便不展开了），因此，这里笔者主要使用数组来实现栈。

1.2.3实现结构

a.栈的结构体

静态的结构在实践用到的地方并不多，因此我们实现动态增长的栈。栈的结构体中,_a指向动态开辟的数组空间，_top用来指向栈顶元素或者栈顶元素的下一个位置，_capacity用来表示栈的容量

  1. // 支持动态增长的栈
  2. typedef int STDataType;
  3.  
  4. typedef struct Stack
  5. {
  6. 	STDataType* _a;
  7. 	int _top;		// 栈顶
  8. 	int _capacity;  // 容量 
  9. }Stack;
b.栈的初始化

栈的初始化中，需要注意的是_top的初始值初始化为-1与初始化为0是截然不同的。我们的惯性思考会认为没有数据就是0,但是_top此处并不是单纯的表示数据个数的，我们知道数组能访问到最小下表是0，如果_top是表示指向栈顶数据的，那么当_top初始化为0，表示没有数据，当数组内有一个数据时，为了表示有一个数据，我们就将_top+1吗？这样似乎浪费空间了，因此如果_top是表示指向栈顶数据，我们就将_top初始化为-1，如果_top指向栈顶数据的下一个位置，我们就将_top始化为 0，这时的_top就还可以表示表示数组元素的个数了。笔者接下来实现栈的结构，_top指向栈顶元素的下一个位置。

  1. // 初始化栈 
  2. void StackInit(Stack* ps)
  3. {
  4. 	assert(ps);
  5.  
  6. 	ps->_a = NULL;
  7.  
  8. 	// top指向栈顶数据的下一个位置
  9. 	ps->_top = 0;
  10.  
  11. 	// top指向栈顶数据
  12. 	//ps->_top = -1;
  13.  
  14. 	ps->_capacity = 0;
  15. }
c.栈的销毁
  1. // 销毁栈 
  2. void StackDestroy(Stack* ps)
  3. {
  4. 	assert(ps);
  5.  
  6. 	free(ps->_a);
  7. 	ps->_a = NULL;
  8. 	ps->_capacity = ps->_top = 0;
  9. }
d.入栈

入栈之前，我们需要先判断数组的空间是否足够，如果不足，我们再扩容，因为_top指向的是栈顶元素的下一个数据，一次插入时的_top当前指向的位置就是要插入数据的位置。之后_top再加一。

  1. // 入栈 
  2. void StackPush(Stack* ps, STDataType data)
  3. {
  4. 	assert(ps);
  5.  
  6. 	//扩容
  7. 	if(ps->_capacity == ps->_top)
  8. 	{
  9.         //对于第一次开辟空间，先初始化4个字节空间，之后每次扩容，扩大两倍
  10. 		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
  11. 		STDataType* newnode = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
  12.  
  13. 		if (NULL == newnode)
  14. 		{
  15. 			perror("StackInit:realloc");
  16. 			exit(1);
  17. 		}
  18.  
  19. 		ps->_a = newnode;
  20.         //更新容量的记录值
  21. 		ps->_capacity = newcapacity;
  22. 	}
  23.  
  24. 	ps->_a[ps->_top] = data;
  25. 	ps->_top++;
  26. }
e.出栈 
  1. // 出栈 
  2. void StackPop(Stack* ps)
  3. {
  4.  
  5. 	assert(ps);
  6. 	assert(ps->_top > 0);
  7.  
  8. 	ps->_top--;
  9.  
  10. }
f.获取栈顶元素
  1. // 获取栈顶元素 
  2. STDataType StackTop(Stack* ps)
  3. {
  4.  
  5. 	assert(ps);
  6. 	assert(ps->_top > 0);
  7.  
  8. 	return ps->_a[ps->_top - 1];
  9. }
g.获取栈中有效元素个数 
  1. // 获取栈中有效元素个数 
  2. int StackSize(Stack* ps)
  3. {
  4. 	assert(ps);
  5.  
  6. 	return ps->_top;
  7. }
h.检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  1. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  2. bool StackEmpty(Stack* ps)
  3. {
  4. 	assert(ps);
  5.  
  6. 	return ps->_top == 0;
  7. }

2.队列

2.1队列的概念及结构

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

2.2队列的实现

2.2.1.实现结构的选择

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据时，就需要挪动数据，效率会比较低。

2.2.2.实现结构的选择

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型 时可以就会使用循环队列（涉及到许多其他知识，这里便不过多介绍）。环形队列可以使用数组实现，也可以使用循环链表实现。

a.单个队列节点的结构体
  1. typedef int QDataType;
  2.  
  3. // 链式结构：表示队列 
  4. typedef struct QListNode
  5. {
  6. 	struct QListNode* _next;
  7. 	QDataType _data;
  8. }QNode;
b.维护队列的结构体

与栈不同，在实现队列时，以入队列为例，我们需要传尾指针，如果要改变尾节点还要传对应的二级指针，同时如果队列现在一个节点都没有，我们还需要传对应头指针的二级指针。总得来说，各种接口的使用似乎非常不便，针对这种问题，我们专门创建一个结构体去维护头指针与尾指针。调用接口时，我们只需要传入这个结构体的指针就可以了。这样我们就可以通过访问结构体来改变对应的头尾指针。此外加上_size记录数据个数

  1. // 队列的结构 
  2. typedef struct Queue
  3. {
  4. 	QNode* _front;
  5. 	QNode* _rear;
  6. 	int _size;
  7. }Queue;
c.队列的初始化

传入专门维护的结构体初始化。

  1. // 初始化队列 
  2. void QueueInit(Queue* q)
  3. {
  4. 	q->_front = NULL;
  5.  
  6. 	q->_rear = NULL;
  7.  
  8. 	q->_size = 0;
  9. }
d.销毁队列 

循环遍历节点，挨个释放

  1. // 销毁队列 
  2. void QueueDestroy(Queue* q)
  3. {
  4. 	assert(q);
  5.  
  6. 	QNode* cur = q->_front;
  7. 	while(cur)
  8. 	{
  9. 		QNode* next = cur->_next;
  10. 		free(cur);
  11.  
  12. 		cur = next;
  13. 	}
  14.  
  15. 	q->_front = q->_rear = NULL;
  16. 	q->_size = 0;
  17. }
e.队尾入队列 

如果队列内没有节点时，在入队列时，还需要该表头结点。

  1. // 队尾入队列 
  2. void QueuePush(Queue* q, QDataType data)
  3. {
  4. 	assert(q);
  5.  
  6. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  7.  
  8. 	if (NULL == newnode)
  9. 	{
  10. 		perror("QueuePush:malloc failed");
  11. 		exit(1);
  12. 	}
  13.  
  14. 	newnode->_data = data;
  15. 	newnode->_next = NULL;
  16.  
  17. 	if (NULL == q->_rear)
  18. 	{
  19. 		q->_front = q->_rear = newnode;
  20. 	}
  21.  
  22. 	else
  23. 	{
  24. 		q->_rear->_next = newnode;
  25. 		q->_rear = newnode;
  26. 	}
  27.  
  28. 	q->_size++;
  29. }
f.队头出队列 

出队列之前需要判断是否队列中是否存在数据，没有数据，无法出数据。如果队列队列中只有一个数据，出完数据，还需要改变头结点。

  1. // 队头出队列 
  2. void QueuePop(Queue* q)
  3. {
  4. 	assert(q);
  5. 	assert(q->_size);
  6.  
  7. 	QNode* next = q->_front->_next;
  8. 	free(q->_front);
  9. 	q->_front = next;
  10.  
  11. 	if (q->_size == 1)
  12. 	{
  13. 		q->_rear = NULL;
  14. 	}
  15.  
  16. 	q->_size--;
  17.  
  18. }
g.获取队列头部元素 

首先判断头指针是否为空，不为空才可以获取头部元素。

  1. // 获取队列头部元素 
  2. QDataType QueueFront(Queue* q)
  3. {
  4. 	assert(q);
  5. 	assert(q->_front);
  6.  
  7. 	return q->_front->_data;
  8. }
h.获取队列队尾元素

首先判断尾指针是否为空，不为空才可以获取尾部元素。

  1. // 获取队列队尾元素 
  2. QDataType QueueBack(Queue* q)
  3. {
  4. 	assert(q);
  5. 	assert(q->_rear);
  6.  
  7. 	return q->_rear->_data;
  8.  
  9. }
i.获取队列中有效元素个数
  1. // 获取队列中有效元素个数 
  2. int QueueSize(Queue* q)
  3. {
  4. 	assert(q);
  5.  
  6. 	return q->_size;
  7. }
j.检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  1. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  2. bool QueueEmpty(Queue* q)
  3. {
  4. 	assert(q);
  5.  
  6. 	return q->_size == 0;
  7. }

3.栈和队列面试题

1. 括号匹配问题。OJ链接

这一道题，要求左括号与对应的右括号匹配，当取出字符串中的右括号时，需要与当前右括号的前面第一个左括号括号比对，如果是对应的左括号，则匹配成功，取下一个右括号，并且取前面第一个左括号匹配（已经匹配的左括号不再参与匹配）。我们发现我们总是需要取离右括号最近的左括号（相对其他左括号顺序靠后的元素）。匹配后，已匹配的括号不参加，下次匹配据需向“左找”。

因此根据题意，我们这里可以创建栈，循环遍历字符数组，如果当前是左括号，则入栈，如果是右括号，那么这时，我们就取栈顶的元素（由于栈是后入先出栈，因此栈顶的元素就是左边离右括号最近的左括号），与右括号匹配，如果匹配则，将匹配的左括号出栈，继续循环，如果不匹配，则结束遍历。

  1. #include<stdlib.h>
  2. #include<stdbool.h>
  3. #include<assert.h>
  4. #include<stdio.h>
  5.  
  6.  
  7. // 支持动态增长的栈
  8. typedef int STDataType;
  9.  
  10. typedef struct Stack
  11. {
  12. 	STDataType* _a;
  13. 	int _top;		// 栈顶
  14. 	int _capacity;  // 容量 
  15. }Stack;
  16.  
  17. // 初始化栈 
  18. void StackInit(Stack* ps)
  19. {
  20. 	ps->_a = NULL;
  21. 	ps->_capacity = ps->_top = 0;
  22. }
  23.  
  24. // 入栈 
  25. void StackPush(Stack* ps, STDataType data)
  26. {
  27. 	assert(ps);
  28. 	if(ps->_capacity == ps->_top)
  29. 	{
  30. 		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
  31. 		STDataType* newnode = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
  32.  
  33. 		if (NULL == newnode)
  34. 		{
  35. 			perror("StackInit:realloc");
  36. 			exit(1);
  37. 		}
  38. 		ps->_a = newnode;
  39. 		ps->_capacity = newcapacity;
  40. 	}
  41.  
  42. 	ps->_a[ps->_top] = data;
  43. 	ps->_top++;
  44. }
  45.  
  46. // 出栈 
  47. void StackPop(Stack* ps)
  48. {
  49.  
  50. 	assert(ps);
  51. 	assert(ps->_top > 0);
  52.  
  53. 	ps->_top--;
  54.  
  55. }
  56.  
  57. // 获取栈顶元素 
  58. STDataType StackTop(Stack* ps)
  59. {
  60.  
  61. 	assert(ps);
  62. 	assert(ps->_top > 0);
  63.  
  64. 	return ps->_a[ps->_top - 1];
  65. }
  66.  
  67. // 获取栈中有效元素个数 
  68. int StackSize(Stack* ps)
  69. {
  70. 	assert(ps);
  71.  
  72. 	return ps->_top;
  73. }
  74.  
  75. // 检测栈是否为空，如果为空返回0，如果不为空返回非零结果
  76. bool StackEmpty(Stack* ps)
  77. {
  78. 	assert(ps);
  79. 	return ps->_top;
  80. }
  81.  
  82. // 销毁栈 
  83. void StackDestroy(Stack* ps)
  84. {
  85. 	assert(ps);
  86. 	free(ps->_a);
  87. 	ps->_a = NULL;
  88. 	ps->_capacity = ps->_top = 0;
  89. }
  90.  
  91.  
  92. bool isValid(char* s)
  93. {
  94.     Stack p;
  95.     StackInit(&p);
  96.     while(*s)
  97.     {
  98.         if(*s == '(' || *s == '{' || *s == '[')//左括号入栈
  99.         {
  100.             StackPush(&p,*s);
  101.         }
  102.         else
  103.         {
  104.             if(!StackEmpty(&p))//右括号入栈前不能没有左括号，否则一定会出现不匹配的情况
  105.             {
  106.                 StackDestroy(&p);
  107.                 return false;
  108.             }
  109.  
  110.             char top = 0;
  111.             top = StackTop(&p);
  112.  
  113.             if(top == '(' && *s != ')'||top == '{' && *s != '}'||top == '[' && *s != ']')//括号不匹配返回false
  114.             {
  115.                 StackDestroy(&p);
  116.                 return false;
  117.             }
  118.  
  119.             StackPop(&p);//匹配成功，将匹配的左括号出栈
  120.         }
  121.  
  122.         s++;//移动到下一个括号
  123.     }
  124.  
  125.     int ret = !StackEmpty(&p);//判断栈内是否为空，为空说明存在未匹配的左括号
  126.     StackDestroy(&p);
  127.     
  128.     return ret;
  129. }

2. 用队列实现栈。OJ链接

这一题，我们需要根据队列先进先出的性质实现栈后进先出的性质，题目给了我们两个队列，因此这题就是通过将数据在两个列类之间转移来完成的，问题的关键就在于如何转移数据。

如果说队列中已经有数据，为了出4，这是我们就可以将1、2、3入队列入到q2中，这时我们就可以出q1中的4，达到后进先出的效果，之后加入我们入栈5,6呢？我们又将5,6入到哪个队列中呢？

假如们入到 q1,中，这时如果我们将5入到q2,再出6,似乎没什么问题，那么这是如果我们不出6，我们还需要继续导入数据呢？

这是我们发现，面对两个都不为空的队列，我们再想入数据，我们必须先遍历已经存储的数据进行，判断当数据较多时，我们就会发现复杂度以及程序的逻辑性都不会太好。因此，为了避免这一混乱的情况发生，我们必须保证将数据入到不为空的队列，这样出数据将数据导到空队列中，出完数量后，就又保持两队列一空一不为空了。

  1. #include<stdio.h>
  2. #include<assert.h>
  3. #include<stdlib.h>
  4. #include"stdbool.h"
  5.  
  6. typedef int QDataType;
  7.  
  8. // 链式结构：表示队列 
  9. typedef struct QListNode
  10. {
  11. 	struct QListNode* _next;
  12. 	QDataType _data;
  13. }QNode;
  14.  
  15. // 队列的结构 
  16. typedef struct Queue
  17. {
  18. 	QNode* _front;
  19. 	QNode* _rear;
  20. 	int _size;
  21. }Queue;
  22. void QueueInit(Queue* q)
  23. {
  24. 	q->_front = NULL;
  25.  
  26. 	q->_rear = NULL;
  27.  
  28. 	q->_size = 0;
  29. }
  30.  
  31. // 队尾入队列 
  32. void QueuePush(Queue* q, QDataType data)
  33. {
  34. 	assert(q);
  35. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  36.  
  37. 	if (NULL == newnode)
  38. 	{
  39. 		perror("QueuePush:malloc failed");
  40. 		exit(1);
  41. 	}
  42.  
  43. 	newnode->_data = data;
  44. 	newnode->_next = NULL;
  45.  
  46. 	if (0 == q->_size)
  47. 	{
  48. 		q->_front = q->_rear = newnode;
  49. 	}
  50. 	else
  51. 	{
  52. 		q->_rear->_next = newnode;
  53. 		q->_rear = q->_rear->_next;
  54. 	}
  55. 	q->_size++;
  56. }
  57.  
  58. // 队头出队列 
  59. void QueuePop(Queue* q)
  60. {
  61. 	assert(q);
  62. 	assert(q->_size);
  63.  
  64. 	QNode* next = q->_front->_next;
  65. 	free(q->_front);
  66. 	q->_front = next;
  67.  
  68. 	if (q->_size == 1)
  69. 	{
  70. 		q->_rear = NULL;
  71. 	}
  72.  
  73. 	q->_size--;
  74.  
  75. }
  76.  
  77. // 获取队列头部元素 
  78. QDataType QueueFront(Queue* q)
  79. {
  80. 	assert(q);
  81. 	assert(q->_size);
  82.  
  83. 	return q->_front->_data;
  84. }
  85.  
  86. // 获取队列队尾元素 
  87. QDataType QueueBack(Queue* q)
  88. {
  89. 	assert(q);
  90. 	assert(q->_size);
  91.  
  92. 	return q->_rear->_data;
  93.  
  94. }
  95.  
  96. // 获取队列中有效元素个数 
  97. int QueueSize(Queue* q)
  98. {
  99. 	assert(q);
  100.  
  101. 	return q->_size;
  102. }
  103.  
  104. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  105. bool QueueEmpty(Queue* q)
  106. {
  107. 	assert(q);
  108.  
  109. 	return q->_size == 0;
  110. }
  111.  
  112. // 销毁队列 
  113. void QueueDestroy(Queue* q)
  114. {
  115. 	assert(q);
  116.     
  117. 	QNode* cur = q->_front;
  118. 	while(cur)
  119. 	{
  120. 		QNode* next = cur->_next;
  121. 		free(cur);
  122.  
  123. 		cur = next;
  124. 	}
  125.  
  126. 	q->_front = q->_rear = NULL;
  127. 	q->_size = 0;
  128. }
  129. typedef struct {
  130.     Queue q1;
  131.     Queue q2;
  132. } MyStack;
  133.  
  134.  
  135. MyStack* myStackCreate() {
  136.     MyStack*pst = (MyStack*)malloc(sizeof(MyStack));
  137. //创建模拟的栈时，只能malloc动态创建，不能静态开辟，否则出了函数，开辟空间会被收回
  138. //也不能使用static, 否则多次调用函数，值会一直保存，会出问题。
  139.     if(NULL == pst)
  140.     {
  141.         perror("malloc");
  142.         exit(1);
  143.     }
  144.  
  145.     QueueInit(&pst->q1);
  146.     QueueInit(&pst->q2);
  147.  
  148.     return pst;
  149. }
  150.  
  151. void myStackPush(MyStack* obj, int x) {
  152.     if(!QueueEmpty(&obj->q1))
  153.     {
  154.         QueuePush(&obj->q1,x);
  155.     }
  156.  
  157.     else
  158.     {
  159.          QueuePush(&obj->q2,x);
  160.     }
  161. }
  162.  
  163. int myStackPop(MyStack* obj) {
  164.     //假设法
  165.     Queue* empty = &(obj->q1);
  166.     Queue* nonempty = &(obj->q2);
  167.     if(!QueueEmpty(&(obj->q1)))
  168.     {
  169.         nonempty = &(obj->q1);
  170.         empty = &(obj->q2);
  171.     }
  172.  
  173.     //不为空的队列前size-1导走，删除最后一个就是栈顶数据
  174.     while(QueueSize(nonempty) > 1)
  175.     {
  176.         QueuePush(empty,QueueFront(nonempty));
  177.         QueuePop(nonempty);
  178.     }
  179.  
  180.     int top = QueueFront(nonempty);
  181.     QueuePop(nonempty);
  182.  
  183.     return  top;
  184. }
  185.  
  186. int myStackTop(MyStack* obj) {
  187.     if(!QueueEmpty(&(obj->q1)))
  188.     {
  189.        return QueueBack(&(obj->q1));
  190.     }
  191.     else
  192.     {
  193.        return QueueBack(&(obj->q2));
  194.     }
  195. }
  196.  
  197. bool myStackEmpty(MyStack* obj) {
  198.     //两个队列都为空才是空
  199.     return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2));
  200. }
  201.  
  202. void myStackFree(MyStack* obj) {
  203.  
  204.     QueueDestroy(&(obj->q1));
  205.     QueueDestroy(&(obj->q2));
  206.  
  207.     free(obj);
  208. }
  209.  
  210. /**
  211.  * Your MyStack struct will be instantiated and called as such:
  212.  * MyStack* obj = myStackCreate();
  213.  * myStackPush(obj, x);
  214.  
  215.  * int param_2 = myStackPop(obj);
  216.  
  217.  * int param_3 = myStackTop(obj);
  218.  
  219.  * bool param_4 = myStackEmpty(obj);
  220.  
  221.  * myStackFree(obj);
  222. */

需要注意的是最后销毁时，要先销毁队列对应的空间，在销毁存储两个队列指针的空间。

3. 用栈实现队列。OJ链接

对于这一题，如果我们沿用用队列实现栈的思路，似乎也可以，我们将先将其他数据入到另一个栈中，再留下要出栈的数据出栈。但是我们要入栈时，我们不能在入到非空的栈中，因为这样，出数据的时候，顺序就完全乱了，对此，我们可以将原数据再倒回原数据中，再向非空栈中入数据。这样就没问题了，但是这样就比较麻烦了。

根据观察，我们发现其实在将数据到到空栈是，原数据顺序会倒过来，这是我们再出栈，就直接实现了先进先出的效果。

因此我们将两个栈分成一个专门出数据，一个专门入数据，当出数据栈popst为空，我们就将入数据栈pushst数据全部导到popst中（必须一次性将所有数据全部导入，否则顺序就乱了。）入数据时，直接往对应栈入就行了。

  1. #include<stdlib.h>
  2. #include<stdbool.h>
  3. #include<assert.h>
  4. #include<stdio.h>
  5.  
  6.  
  7. // 支持动态增长的栈
  8. typedef int STDataType;
  9.  
  10. typedef struct Stack
  11. {
  12. 	STDataType* _a;
  13. 	int _top;		// 栈顶
  14. 	int _capacity;  // 容量 
  15. }Stack;
  16. // 初始化栈 
  17. void StackInit(Stack* ps)
  18. {
  19. 	ps->_a = NULL;
  20. 	ps->_capacity = ps->_top = 0;
  21. }
  22.  
  23. // 入栈 
  24. void StackPush(Stack* ps, STDataType data)
  25. {
  26. 	assert(ps);
  27. 	if(ps->_capacity == ps->_top)
  28. 	{
  29. 		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
  30. 		STDataType* newnode = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
  31.  
  32. 		if (NULL == newnode)
  33. 		{
  34. 			perror("StackInit:realloc");
  35. 			exit(1);
  36. 		}
  37. 		ps->_a = newnode;
  38. 		ps->_capacity = newcapacity;
  39. 	}
  40.  
  41. 	ps->_a[ps->_top] = data;
  42. 	ps->_top++;
  43. }
  44.  
  45. // 出栈 
  46. void StackPop(Stack* ps)
  47. {
  48.  
  49. 	assert(ps);
  50. 	assert(ps->_top > 0);
  51.  
  52. 	ps->_top--;
  53.  
  54. }
  55.  
  56. // 获取栈顶元素 
  57. STDataType StackTop(Stack* ps)
  58. {
  59.  
  60. 	assert(ps);
  61. 	assert(ps->_top > 0);
  62.  
  63. 	return ps->_a[ps->_top - 1];
  64. }
  65.  
  66. // 获取栈中有效元素个数 
  67. int StackSize(Stack* ps)
  68. {
  69. 	assert(ps);
  70.  
  71. 	return ps->_top;
  72. }
  73.  
  74. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  75. bool StackEmpty(Stack* ps)
  76. {
  77. 	assert(ps);
  78. 	return ps->_top == 0;
  79. }
  80.  
  81. // 销毁栈 
  82. void StackDestroy(Stack* ps)
  83. {
  84. 	assert(ps);
  85. 	free(ps->_a);
  86. 	ps->_a = NULL;
  87. 	ps->_capacity = ps->_top = 0;
  88. }
  89.  
  90. typedef struct {
  91.     Stack pushst;
  92.     Stack popst;
  93. } MyQueue;
  94.  
  95.  
  96. MyQueue* myQueueCreate() {
  97.     MyQueue* q1 = (MyQueue*)malloc(sizeof(MyQueue));
  98.     StackInit(&q1->pushst);
  99.     StackInit(&q1->popst);
  100.     return q1;
  101. }
  102.  
  103. void myQueuePush(MyQueue* obj, int x) {
  104. //实现入队列数据
  105.     StackPush(&obj->pushst,x);
  106. }
  107.  
  108.  
  109. int myQueuePeek(MyQueue* obj) {
  110.     if(StackEmpty(&obj->popst))
  111.     {
  112.         //倒数据
  113. //实现出队列数据
  114.         while(!StackEmpty(&obj->pushst))//专门出数据的栈为空，就先导入一下数据
  115.         {
  116.             StackPush(&obj->popst,StackTop(&obj->pushst));
  117.             StackPop(&obj->pushst);
  118.         }
  119.  
  120.     }
  121.  
  122.     return StackTop(&obj->popst);
  123. }
  124.  
  125. int myQueuePop(MyQueue* obj) {
  126. //出队列队头数据
  127.     int front = myQueuePeek(obj);
  128.     StackPop(&obj->popst);
  129.  
  130.     return front;
  131.  
  132. }
  133.  
  134. bool myQueueEmpty(MyQueue* obj) {
  135. //两个栈都为空，队列才为空
  136.     return StackEmpty(&obj->pushst)&&StackEmpty(&obj->popst);
  137. }
  138.  
  139. void myQueueFree(MyQueue* obj) {
  140. //先释放对应栈空间，再释放队列对应空间
  141.     StackDestroy(&obj->pushst);
  142.     StackDestroy(&obj->popst);
  143.     free(obj);
  144. }
  145.  
  146. /**
  147.  * Your MyQueue struct will be instantiated and called as such:
  148.  * MyQueue* obj = myQueueCreate();
  149.  * myQueuePush(obj, x);
  150.  
  151.  * int param_2 = myQueuePop(obj);
  152.  
  153.  * int param_3 = myQueuePeek(obj);
  154.  
  155.  * bool param_4 = myQueueEmpty(obj);
  156.  
  157.  * myQueueFree(obj);
  158. */

4. 设计循环队列。OJ链接

这道题目的意思就是队列的的空间大小是固定的，这些空间可以重复使用，看到这一题的循环结构，也许有的读者会想到链表，认为链表的结构完成这一题会比数组简单，但是实际上并不是这样的，笔者这里先以数组完成这题，链表的不便后文讲解。

首先假设要插入的空间K是4，这是如果我们开辟4个空间，head、tail都初始化为0，push一个数据，tail++,pop一个数据，head++，当tail、head值大于K,通过%K,实现回环，这样head == tail时，就代表数组为空的情况了，但是，我们发现如果数组满时也会出现head == tail，这就是我们说的假溢出的情况了。

为了解决这个问题，笔者有两种方法，一种是创建size专门记录数组元素个数；还有一种是多开一个空间。笔者接下来重点介绍第二种（对于这类问题一些官方解答更喜欢用第二种方法）。

如上图，其他不变，只是我们判断数组满到条件变成了（tail+1）%(k+1) == head;这是为什么呢？我们知道，head是指向队列的头，tail指向尾的下一位，因为我们多开了一个空间，并且是按序的空出空间，因此，当数组满时，尾的空间后面就是空空间，tail指向它，这时如果tail再向前走一步，就与head相等，不过这时，为了避免出现越界的情况，tail+1需要%（K+1），这就相当于tail+1>5时，tail+1-5，tail回到数组开头，同时数组越界的情况是相对与数组总长的，因此这里是%（k+1）不是%k.

  1.  
  2.  
  3. typedef struct {//创建结构体存储需要用到的值方便维护
  4.     int k;
  5.     int head;
  6.     int tail;
  7.     int* a;
  8. } MyCircularQueue;
  9.  
  10.  
  11. MyCircularQueue* myCircularQueueCreate(int k) {//初始化结构体
  12.  
  13.    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  14.    obj->a = (int*)malloc((k + 1) * sizeof(int));
  15.    obj->head = 0;
  16.    obj->tail = 0;
  17.    obj->k = k;
  18.  
  19.    return obj;
  20. }
  21.  
  22. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  23.  
  24.     return obj->head == obj->tail;//head == tail为空
  25.  
  26. }
  27.  
  28. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  29.  
  30.    return (obj->tail + 1)%(obj->k + 1) == obj->head;//(tail + 1)%(k + 1) == head 为满
  31.  
  32. }
  33.  
  34. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  35.  
  36.     if(myCircularQueueIsFull(obj))
  37.     {
  38.         return false;
  39.     }
  40.  
  41.     else
  42.     {
  43.         obj->a[obj->tail] = value;
  44.         obj->tail = (obj->tail + 1) % (obj->k + 1);//防止越界
  45.         return true;
  46.     }
  47. }
  48.  
  49. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  50.  
  51.     if(myCircularQueueIsEmpty(obj))
  52.     {
  53.         return false;
  54.     }
  55.  
  56.         obj->head = (obj->head + 1) % (obj->k + 1);//防止head越界
  57.         return true;
  58.  
  59. }
  60.  
  61. int myCircularQueueFront(MyCircularQueue* obj) {
  62.  
  63.     if(myCircularQueueIsEmpty(obj))//为空取不到队头的数据
  64.     {
  65.         return -1;
  66.     }
  67.     else
  68.     {
  69.         return obj->a[obj->head];
  70.     }
  71. }
  72.  
  73. int myCircularQueueRear(MyCircularQueue* obj) {
  74.  
  75.     if(myCircularQueueIsEmpty(obj))//为空取不到队尾的数据
  76.     {
  77.         return -1;
  78.     }
  79.     else
  80.     {
  81.         return obj->a[(obj->tail-1 + obj->k + 1) % (obj->k + 1)];
  82.     }
  83. }
  84.  
  85.  
  86.  
  87. void myCircularQueueFree(MyCircularQueue* obj) {
  88.  
  89.     free(obj->a);
  90.     free(obj);
  91.  
  92. }
  93.  
  94. /**
  95.  * Your MyCircularQueue struct will be instantiated and called as such:
  96.  * MyCircularQueue* obj = myCircularQueueCreate(k);
  97.  * bool param_1 = myCircularQueueEnQueue(obj, value);
  98.  
  99.  * bool param_2 = myCircularQueueDeQueue(obj);
  100.  
  101.  * int param_3 = myCircularQueueFront(obj);
  102.  
  103.  * int param_4 = myCircularQueueRear(obj);
  104.  
  105.  * bool param_5 = myCircularQueueIsEmpty(obj);
  106.  
  107.  * bool param_6 = myCircularQueueIsFull(obj);
  108.  
  109.  * myCircularQueueFree(obj);
  110. */

这里需要特别注意的是，当我们取队尾的数据时，由于tail是指向队尾数据的下一位，因此如果tail在数组头，tail-1取队尾就会出现负数的情况，因此与（tail+1）%(k+1)类似，我们要将（tail+1 +k+1）%(k+1)，这样就可以避免出现，负数的情况，如果tail不在队头这样处理也不会有问题。

那么回到一开始的问题，为什么笔者说，使用链表不像看上去那样简单呢？首先，用链表形成循环队列，不像数组那样直接申请一块空间方便，其次由于tail是指向尾的下一个位置，因此我们如果想要找尾会很麻烦，对此可以使用双向链表、遍历寻找尾、专门创建变量记录tail前一个节点，总的来说，使用链表不光没有什么实质的好处，反而还会有不少麻烦。当然，如果读者想要用链表完成，也不无不可。

4.概念选择题

4.1题目

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

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

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

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

3.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作 后， front=rear=99 ，则循环队列中的元素个数为（ ）

A 1

B 2

C 99

D 0或者100

4.以下( )不是队列的基本运算？

A 从队尾插入一个新元素

B 从队列中删除第i个元素

C 判断一个队列是否为空

D 读取队头元素的值

5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设 队头不存放数据)

A (rear - front + N) % N + 1

B (rear - front + N) % N

C ear - front) % (N + 1)

D (rear - front + N) % (N - 1)

4.2答案

1.B  //依次入栈，入完再出栈，后入先出

2.C  //不可能出现2不出，就出到1

3.D  //属于没有多开一个空间的方法，相等时可能为空，可能满。

4.B

5.B

5.附录源码：

5.1栈：

Stack.h

  1. #pragma once
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include<stdlib.h>
  4. #include<stdbool.h>
  5. #include<assert.h>
  6. #include<stdio.h>
  7.  
  8.  
  9. // 支持动态增长的栈
  10. typedef int STDataType;
  11.  
  12. typedef struct Stack
  13. {
  14. 	STDataType* _a;
  15. 	int _top;		// 栈顶
  16. 	int _capacity;  // 容量 
  17. }Stack;
  18.  
  19. // 初始化栈 
  20. void StackInit(Stack* ps);
  21.  
  22. // 入栈 
  23. void StackPush(Stack* ps, STDataType data);
  24.  
  25. // 出栈 
  26. void StackPop(Stack* ps);
  27.  
  28. // 获取栈顶元素 
  29. STDataType StackTop(Stack* ps);
  30.  
  31. // 获取栈中有效元素个数 
  32. int StackSize(Stack* ps);
  33.  
  34. // 检测栈是否为空，如果为空返回0 ，如果不为空返回非零结果
  35. bool StackEmpty(Stack* ps);
  36.  
  37. // 销毁栈 
  38. void StackDestroy(Stack* ps);

Stack.c

  1. #include"Stack.h"
  2.  
  3. // 初始化栈 
  4. void StackInit(Stack* ps)
  5. {
  6. 	assert(ps);
  7.  
  8. 	ps->_a = NULL;
  9.  
  10. 	// top指向栈顶数据的下一个位置
  11. 	ps->_top = 0;
  12.  
  13. 	// top指向栈顶数据
  14. 	//ps->_top = -1;
  15.  
  16. 	ps->_capacity = 0;
  17. }
  18.  
  19. // 入栈 
  20. void StackPush(Stack* ps, STDataType data)
  21. {
  22. 	assert(ps);
  23.  
  24. 	//扩容
  25. 	if(ps->_capacity == ps->_top)
  26. 	{
  27. 		int newcapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
  28. 		STDataType* newnode = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
  29.  
  30. 		if (NULL == newnode)
  31. 		{
  32. 			perror("StackInit:realloc");
  33. 			exit(1);
  34. 		}
  35.  
  36. 		ps->_a = newnode;
  37. 		ps->_capacity = newcapacity;
  38. 	}
  39.  
  40. 	ps->_a[ps->_top] = data;
  41. 	ps->_top++;
  42. }
  43.  
  44. // 出栈 
  45. void StackPop(Stack* ps)
  46. {
  47.  
  48. 	assert(ps);
  49. 	assert(ps->_top > 0);
  50.  
  51. 	ps->_top--;
  52.  
  53. }
  54.  
  55. // 获取栈顶元素 
  56. STDataType StackTop(Stack* ps)
  57. {
  58.  
  59. 	assert(ps);
  60. 	assert(ps->_top > 0);
  61.  
  62. 	return ps->_a[ps->_top - 1];
  63. }
  64.  
  65. // 获取栈中有效元素个数 
  66. int StackSize(Stack* ps)
  67. {
  68. 	assert(ps);
  69.  
  70. 	return ps->_top;
  71. }
  72.  
  73. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  74. bool StackEmpty(Stack* ps)
  75. {
  76. 	assert(ps);
  77.  
  78. 	return ps->_top == 0;
  79. }
  80.  
  81. // 销毁栈 
  82. void StackDestroy(Stack* ps)
  83. {
  84. 	assert(ps);
  85.  
  86. 	free(ps->_a);
  87. 	ps->_a = NULL;
  88. 	ps->_capacity = ps->_top = 0;
  89. }

5.2队列

Queue.h

  1. #pragma once
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include<stdio.h>
  4. #include<assert.h>
  5. #include<stdlib.h>
  6. #include"stdbool.h"
  7.  
  8. typedef int QDataType;
  9.  
  10. // 链式结构：表示队列 
  11. typedef struct QListNode
  12. {
  13. 	struct QListNode* _next;
  14. 	QDataType _data;
  15. }QNode;
  16.  
  17. // 队列的结构 
  18. typedef struct Queue
  19. {
  20. 	QNode* _front;
  21. 	QNode* _rear;
  22. 	int _size;
  23. }Queue;
  24.  
  25. // 初始化队列 
  26. void QueueInit(Queue* q);
  27.  
  28. // 队尾入队列 
  29. void QueuePush(Queue* q, QDataType data);
  30.  
  31. // 队头出队列 
  32. void QueuePop(Queue* q);
  33.  
  34. // 获取队列头部元素 
  35. QDataType QueueFront(Queue* q);
  36.  
  37. // 获取队列队尾元素 
  38. QDataType QueueBack(Queue* q);
  39.  
  40. // 获取队列中有效元素个数 
  41. int QueueSize(Queue* q);
  42.  
  43. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  44. bool QueueEmpty(Queue* q);
  45.  
  46. // 销毁队列 
  47. void QueueDestroy(Queue* q);

Queue.c

  1. #include"queue.h"
  2.  
  3.  
  4. // 初始化队列 
  5. void QueueInit(Queue* q)
  6. {
  7. 	q->_front = NULL;
  8.  
  9. 	q->_rear = NULL;
  10.  
  11. 	q->_size = 0;
  12. }
  13.  
  14. // 队尾入队列 
  15. void QueuePush(Queue* q, QDataType data)
  16. {
  17. 	assert(q);
  18.  
  19. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  20.  
  21. 	if (NULL == newnode)
  22. 	{
  23. 		perror("QueuePush:malloc failed");
  24. 		exit(1);
  25. 	}
  26.  
  27. 	newnode->_data = data;
  28. 	newnode->_next = NULL;
  29.  
  30. 	if (NULL == q->_rear)
  31. 	{
  32. 		q->_front = q->_rear = newnode;
  33. 	}
  34.  
  35. 	else
  36. 	{
  37. 		q->_rear->_next = newnode;
  38. 		q->_rear = newnode;
  39. 	}
  40.  
  41. 	q->_size++;
  42. }
  43.  
  44. // 队头出队列 
  45. void QueuePop(Queue* q)
  46. {
  47. 	assert(q);
  48. 	assert(q->_size);
  49.  
  50. 	QNode* next = q->_front->_next;
  51. 	free(q->_front);
  52. 	q->_front = next;
  53.  
  54. 	if (q->_size == 1)
  55. 	{
  56. 		q->_rear = NULL;
  57. 	}
  58.  
  59. 	q->_size--;
  60.  
  61. }
  62.  
  63. // 获取队列头部元素 
  64. QDataType QueueFront(Queue* q)
  65. {
  66. 	assert(q);
  67. 	assert(q->_front);
  68.  
  69. 	return q->_front->_data;
  70. }
  71.  
  72. // 获取队列队尾元素 
  73. QDataType QueueBack(Queue* q)
  74. {
  75. 	assert(q);
  76. 	assert(q->_rear);
  77.  
  78. 	return q->_rear->_data;
  79.  
  80. }
  81.  
  82. // 获取队列中有效元素个数 
  83. int QueueSize(Queue* q)
  84. {
  85. 	assert(q);
  86.  
  87. 	return q->_size;
  88. }
  89.  
  90. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  91. bool QueueEmpty(Queue* q)
  92. {
  93. 	assert(q);
  94.  
  95. 	return q->_size == 0;
  96. }
  97.  
  98. // 销毁队列 
  99. void QueueDestroy(Queue* q)
  100. {
  101. 	assert(q);
  102.  
  103. 	QNode* cur = q->_front;
  104. 	while(cur)
  105. 	{
  106. 		QNode* next = cur->_next;
  107. 		free(cur);
  108.  
  109. 		cur = next;
  110. 	}
  111.  
  112. 	q->_front = q->_rear = NULL;
  113. 	q->_size = 0;
  114. }

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

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

  

闽ICP备14008679号