史上最强数据结构----栈和队列相关笔试面试题

转x33g5p2x  于2022-04-12 转载在 其他  
字(9.7k)|赞(0)|评价(0)|浏览(450)

1. 栈和队列面试题

1.1 括号匹配问题

题目：

思路：

首先将所给的字符串进行遍历，如果是左括号就将它压入栈中，根据栈后进先出的特性，然后逐个取出栈中的左括号与后面剩下的右括号进行逐对进行匹配，如果不匹配就返回false，如果都匹配了就返回true。

例如：

代码：

  1. typedef char STDataType;
  2. typedef struct Stack
  3. {
  4. 	STDataType* a;
  5. 	int top;//栈顶的位置
  6. 	int capacity;//容量
  7. }ST;
  8. void StackInit(ST* ps)
  9. {
  10. 	assert(ps);
  11. 	ps->a = NULL;
  12. 	ps->capacity = 0;
  13. 	ps->top = 0;
  14. }
  15. void StackDestory(ST*ps)
  16. {
  17. 	assert(ps);
  18. 	free(ps->a);
  19. 	ps->a = NULL;
  20. 	ps->capacity =ps->top =  0;
  21. }
  22. void StackPush(ST* ps, STDataType x)
  23. {
  24. 	assert(ps);
  25. 	if (ps->top == ps->capacity)//满了进行扩容
  26. 	{
  27. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  28. 		ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
  29. 		if (ps->a == NULL)
  30. 		{
  31. 			printf("fail malloc\n");
  32. 			exit(-1);
  33. 		}
  34. 		ps->capacity = newCapacity;
  35. 	}
  36. 	ps->a[ps->top++] = x;
  37. }
  38. void StackPop(ST* ps)
  39. {
  40. 	assert(ps);
  41. 	assert(ps->top > 0);
  42. 	--ps->top;
  43. }
  44. bool StackEmpty(ST* ps)
  45. {
  46. 	assert(ps);
  47. 	return ps->top == 0;
  48. }
  49. STDataType StackTop(ST* ps)
  50. {
  51. 	assert(ps);
  52. 	assert(ps->top > 0);
  54. 	return ps->a[ps->top - 1];
  55. }
  56. int SizeStack(ST* ps)
  57. {
  58. 	assert(ps);
  59. 	return ps->top;
  60. }
  61. //前面的所有代码就是定义一个栈以及栈的相关函数
  62. bool isValid(char * s){
  63.     ST st;
  64.     StackInit(&st);
  65.     while(*s)
  66.     {
  67.         if(*s=='['||*s=='('||*s=='{')
  68.         {
  69.             StackPush(&st,*s);
  70.             ++s;
  71.         }
  72.         else
  73.         {
  74.             if(StackEmpty(&st))//当所给的字符串中只有右括号时直接返回false
  75.             {
  76.                 StackDestory(&st);
  77.                 return false;
  78.             }
  79.             char top = StackTop(&st);//从栈中取一个左括号
  80.             StackPop(&st);//进行出栈操作，让刚才取的字符出栈
  81.             if((*s==']'&&top!='[')
  82.             ||(*s=='}'&&top!='{')
  83.             ||(*s==')'&&top!='('))//两个字符不相匹配的情况下直接返回false
  84.             {
  85.                 StackDestory(&st);
  86.                 return false;
  87.             }
  88.             else
  89.             {
  90.                 ++s;
  91.             }
  92.         }
  93.     }
  94.     //栈为空，说明所有左括号都匹配了
  95.     bool ret =  StackEmpty(&st);//判断是否只有左括号，如果只有左括号此时ret就为false，如果前面都已经匹配完了ret就等于true
  96.     StackDestory(&st);
  97.     return ret;
  98. }

1.2 用队列实现栈

解析上面的实例：

输入的第一行是执行的操作。第二行是执行操作的数据。

输出是对应的返回值。

思路：用两个队列实现栈。

栈的基本结构：

1、入栈，push数据到不为空的队列。

2、出栈，把不为空的队列的数据前N-1导入到另一个空队列，最后剩下的一个删掉。

代码：

  1. typedef int QDataType;
  2. typedef struct QueueNode
  3. {
  4. 	QDataType data;
  5. 	struct QueueNode* next;
  6. }QNode;
  7. typedef struct Queue
  8. {
  9. 	QNode* head;
  10. 	QNode* tail;
  11. }Queue;
  12. void QueueInit(Queue* pq);
  13. void QueueDestory(Queue* pq);
  14. void QueuePush(Queue*pq,QDataType x);
  15. void QueuePop(Queue*pq);
  16. size_t QueueSize(Queue* pq);
  17. QDataType QueueFront(Queue* pq);
  18. QDataType QueueBack(Queue* pq);
  19. bool QueueEmpty(Queue* pq);
  20. void QueueInit(Queue* pq)
  21. {
  22. 	assert(pq);
  23. 	pq->head =pq->tail = NULL;
  24. }
  25. QNode* BuyQNode(QDataType x)
  26. {
  27. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  28. 	if (newnode == NULL)
  29. 	{
  30. 		printf("fail malloc\n");
  31. 		exit(-1);
  32. 	}
  33. 	newnode->data = x;
  34. 	newnode->next = NULL;
  35. 	return newnode;
  36. }
  37. void QueuePush(Queue* pq, QDataType x)
  38. {
  39. 	assert(pq);
  40. 	QNode* newnode = BuyQNode(x);
  41. 	if (pq->tail == NULL)
  42. 	{
  43. 		assert(pq->head == NULL);
  44. 		pq->head= pq->tail = newnode;
  45. 	}
  46. 	else
  47. 	{
  48. 		pq->tail->next = newnode;
  49. 		pq->tail = newnode;
  50. 	}
  51. 	
  52. }
  53. void QueuePop(Queue* pq)
  54. {
  55. 	assert(pq);
  56. 	assert(pq->tail&&pq->head);
  57. 	if (pq->head->next==NULL)//处理只有一个节点的时候
  58. 	{
  59. 		free(pq->tail);
  60. 		pq->tail = pq->head = NULL;
  61. 	}
  62. 	else//有多个节点
  63. 	{
  64. 		QNode* next = pq->head->next;
  65. 		free(pq->head);
  66. 		pq->head = next;
  67. 	}
  68. }
  69. size_t QueueSize(Queue* pq)
  70. {
  71. 	assert(pq);
  72. 	size_t size = 0;
  73. 	QNode* cur = pq->head;
  74. 	while (cur!= pq->tail->next)
  75. 	{
  76. 		size++;
  77. 		cur = cur->next;
  78. 	}
  79. 	return size;
  80. }
  81. QDataType QueueFront(Queue* pq)
  82. {
  83. 	assert(pq);
  84. 	assert(pq->head);
  85. 	return pq->head->data;
  86. }
  87. QDataType QueueBack(Queue* pq)
  88. {
  89. 	assert(pq);
  90. 	assert(pq->tail);
  91. 	return pq->tail->data;
  92. }
  93. void QueueDestory(Queue* pq)
  94. {
  95. 	assert(pq);
  96. 	QNode* cur = pq->head;
  97. 	while (cur)
  98. 	{
  99. 		QNode* next = cur->next;
  100. 		free(cur);
  101. 		cur = next;
  102. 	}
  103. 	pq->head = pq->tail = NULL;
  104. }
  105. bool QueueEmpty(Queue* pq)
  106. {
  107. 	assert(pq);
  108. 	return pq->head==NULL&&pq->tail==NULL;
  109. }
  110. typedef struct {
  111.     Queue q1;
  112.     Queue q2;
  113. } MyStack;
  115. MyStack* myStackCreate() {
  116.     MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
  117.     assert(pst);
  118.     QueueInit(&pst->q1);//这一行代码和后面这一行代码等价:QueueInit(&(pst->q1));
  119.     QueueInit(&pst->q2);//这一行代码和后面这一行代码等价:QueueInit(&(pst->q2));
  120.     return pst;
  121. }
  123. void myStackPush(MyStack* obj, int x) {
  124.     assert(obj);
  125.     if(!QueueEmpty(&obj->q1))
  126.     {
  127.         QueuePush(&obj->q1,x);
  128.     }
  129.     else
  130.     {
  131.         QueuePush(&obj->q2,x);
  132.     }
  133. }
  135. int myStackPop(MyStack* obj) {
  136.     assert(obj);
  137.     Queue *emptyQ = &obj->q1;
  138.     Queue*nonEmptyQ = &obj->q2;
  139.     if(!QueueEmpty(&obj->q1))
  140.     {
  141.         emptyQ = &obj->q2;
  142.         nonEmptyQ = &obj->q1;
  143.     }
  144.     //把非空队列的前N个数据，导入空队列，剩下一个删掉
  145.     //就实现了后进先出
  146.     while(QueueSize(nonEmptyQ)>1)
  147.     {
  148.         QueuePush(emptyQ,QueueFront(nonEmptyQ));//将非空队列的队头数据push到非空队列中
  149.         QueuePop(nonEmptyQ);//将非空队列的队头数据出队
  150.     }
  151.     QDataType top = QueueFront(nonEmptyQ);
  152.     QueuePop(nonEmptyQ);
  153.     return top;
  154. }
  156. int myStackTop(MyStack* obj) {
  157.     assert(obj);
  158.     
  159.     if(!QueueEmpty(&obj->q1))
  160.     {
  161.         return QueueBack(&obj->q1);
  162.     }
  163.     else
  164.     {
  165.         return QueueBack(&obj->q2);
  166.     }
  167.    
  168. }
  169. bool myStackEmpty(MyStack* obj) {
  170.     assert(obj);
  171.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
  172. }
  174. void myStackFree(MyStack* obj) {
  175.     assert(obj);
  176.     QueueDestory(&obj->q1);
  177.     QueueDestory(&obj->q2);
  178.     free(obj);
  179. }

1.3 用栈实现队列

思路：

注意：在上面的代码中，在进行出队操作时，只要popST这个栈中有数据，那么我们就不进行倒数据的操作（即将push中的数据倒到popST这个栈中），只有当pop中的数据为空且我们要进行出队时才进行倒数据。

队列结构：

代码：

  1. typedef int STDataType;
  2. //数组栈的实现
  3. typedef struct Stack
  4. {
  5. 	STDataType* a;
  6. 	int top;//栈顶的位置
  7. 	int capacity;//容量
  8. }ST;
  9. void StackInit(ST* ps)
  10. {
  11. 	assert(ps);
  12. 	ps->a = NULL;
  13. 	ps->capacity = 0;
  14. 	ps->top = 0;
  15. }
  16. void StackDestory(ST*ps)
  17. {
  18. 	assert(ps);
  19. 	free(ps->a);
  20. 	ps->a = NULL;
  21. 	ps->capacity =ps->top =  0;
  22. }
  23. void StackPush(ST* ps, STDataType x)
  24. {
  25. 	assert(ps);
  26. 	if (ps->top == ps->capacity)//满了进行扩容
  27. 	{
  28. 		int newCapacity = ps->capacity == 0 ? 2 : 2 * ps->capacity;
  29. 		STDataType*new = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
  30. 		if (new == NULL)
  31. 		{
  32. 			printf("fail malloc\n");
  33. 			exit(-1);
  34. 		}
  35. 		ps->a = new;
  36. 		ps->capacity = newCapacity;
  37. 	}
  38. 	ps->a[ps->top++] = x;
  39. }
  40. void StackPop(ST* ps)
  41. {
  42. 	assert(ps);
  43. 	assert(ps->top > 0);
  44. 	--ps->top;
  45. }
  46. bool StackEmpty(ST* ps)
  47. {
  48. 	assert(ps);
  49. 	return ps->top == 0;
  50. }
  51. STDataType StackTop(ST* ps)
  52. {
  53. 	assert(ps);
  54. 	assert(ps->top > 0);
  56. 	return ps->a[ps->top - 1];
  57. }
  58. int SizeStack(ST* ps)
  59. {
  60. 	assert(ps);
  61. 	return ps->top;
  62. }
  63. void StackInit(ST*ps);
  64. void StackDestory(ST* ps);
  65. void StackPush(ST* ps,STDataType x);
  66. void StackPop(ST* ps);
  67. bool StackEmpty(ST* ps);
  68. int SizeStack(ST* ps);
  69. STDataType StackTop(ST* ps);
  70. typedef struct {
  71.     ST pushST;
  72.     ST popST;
  73. } MyQueue;
  75. MyQueue* myQueueCreate() {
  76.     MyQueue * myQueue = (MyQueue*)malloc(sizeof(MyQueue));
  77.     assert(myQueue);
  78.     StackInit(&myQueue->pushST);
  79.     StackInit(&myQueue->popST);
  80.     return myQueue;
  81. }
  83. void myQueuePush(MyQueue* obj, int x) {
  84.     assert(obj);
  85.     StackPush(&obj->pushST,x);//入队直接向pushST插入即可
  86. }
  88. int myQueuePop(MyQueue* obj){
  89.     assert(obj);
  90.     if(StackEmpty(&obj->popST))//push为空，就进行倒数据，就符合先进先出的顺序了
  91.     {
  92.         while(!StackEmpty(&obj->pushST))
  93.         {
  94.             StackPush(&obj->popST,StackTop(&obj->pushST));
  95.             StackPop(&obj->pushST);
  96.         }
  97.     }
  98.     STDataType ret = StackTop(&obj->popST);//临时保存返回的数据
  99.     StackPop(&obj->popST);
  100.     return ret;
  101. }
  103. int myQueuePeek(MyQueue* obj) {
  104.     assert(obj);
  105.     if(StackEmpty(&obj->popST))
  106.     {
  107.         while(!StackEmpty(&obj->pushST))
  108.         {
  109.             StackPush(&obj->popST,StackTop(&obj->pushST));
  110.             StackPop(&obj->pushST);
  111.         }
  112.     }
  113.     return StackTop(&obj->popST);
  114. }
  116. bool myQueueEmpty(MyQueue* obj) {
  117.     assert(obj);
  118.     return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
  119. }
  121. void myQueueFree(MyQueue* obj) {
  122.     assert(obj);
  123.     StackDestory(&obj->pushST);
  124.     StackDestory(&obj->popST);
  125.     free(obj);
  126. }

1.4 设计循环队列

为了避免空和满混淆，无法区分，多开一个空间。

1. front = tail时是空

2. tail下一个位置是front时是满

满的两种情况：

1、obj->tail = k && obj->head = 0

2、obj->tail+1 = obj->head

代码：

  1. typedef struct {
  2.     int *a;
  3.     int head;//循环队列的头
  4.     int tail;//循环队列的尾
  5.     int capacity;//循环队列元素的最大数目
  6. } MyCircularQueue;
  8. bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空的声明
  9. bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满的声明
  10. MyCircularQueue* myCircularQueueCreate(int k) //循环队列的初始化
  11. {
  12.     MyCircularQueue*myCircularQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  13.     assert(myCircularQ);
  14.     int *tmp = (int*)malloc(sizeof(int)*(k+1));
  15.     assert(tmp);
  16.     myCircularQ->a = tmp;
  17.     myCircularQ->head = 0;
  18.     myCircularQ->tail = 0;
  19.     myCircularQ->capacity = k;
  20.     return myCircularQ;
  21. }
  23. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //向循环队列插入一个元素，如果成功插入则返回真。
  24. {
  25.     assert(obj);
  26.     if(myCircularQueueIsFull(obj))//满了的情况
  27.     {
  28.         return false;
  29.     }
  30.     obj->a[obj->tail] = value;
  31.     if(obj->tail==obj->capacity)//此时已经到达了开辟数组的最后一个位置，tail再进行++操作后会跳跃到第一个位置
  32.     {
  33.         obj->tail = 0;
  34.     }
  35.     else
  36.     {
  37.         ++obj->tail;
  38.     }
  39.     return true;
  40. }
  42. bool myCircularQueueDeQueue(MyCircularQueue* obj) //从循环队列中删除一个元素，如果成功删除则返回真。
  43. {
  44.     assert(obj);
  45.     if(myCircularQueueIsEmpty(obj))//循环队列中为空的情况
  46.     {
  47.         return false;
  48.     }
  49.     if(obj->head==obj->capacity)//循环队列中的head在开辟的最后的一个空间位置的情况，head要发生跳跃
  50.     {
  51.         obj->head = 0;
  52.     }
  53.     else
  54.     {
  55.         ++obj->head;
  56.     }
  57.     return true;
  58. }
  60. int myCircularQueueFront(MyCircularQueue* obj) //从队首获取元素，如果队列为空，返回 -1 。
  61. {
  62.     assert(obj);
  63.     if(myCircularQueueIsEmpty(obj))//队列元素为空的情况
  64.         return -1;
  65.     return obj->a[obj->head];
  66. }
  68. int myCircularQueueRear(MyCircularQueue* obj)//获取队尾元素，如果队列为空，返回 -1 。
  69. {
  70.     assert(obj);
  71.     if(myCircularQueueIsEmpty(obj))//循环队列元素为空的情况
  72.         return -1;
  73.     if(obj->tail==0)//尾在头的时候，就要返回最后一个空间的位置
  74.     {
  75.         return obj->a[obj->capacity];
  76.     }
  77.     else
  78.     {
  79.         return obj->a[obj->tail-1];//正常情况返回tail的前一个位置
  80.     }
  81. }
  83. bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断循环队列是否满
  84. {
  85.     assert(obj);
  86.     return obj->tail==obj->head;//尾下标等于头下标的时候就是空
  87. }
  89. bool myCircularQueueIsFull(MyCircularQueue* obj) //判断循环队列是否满
  90. {
  91.     assert(obj);
  92.     if(obj->tail==obj->capacity && obj->head==0)//判断的是尾下标指向最后一块空间，头下标在最靠前的空间
  93.     {
  94.         return true;
  95.     }
  96.     else
  97.     {
  98.         return obj->tail+1 ==obj->head;
  99.     }
  100. }  
  102. void myCircularQueueFree(MyCircularQueue* obj) //循环队列的销毁
  103. {
  104.     assert(obj);
  105.     free(obj->a);
  106.     free(obj);
  107. }

2. 概念选择题

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

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

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

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

解析：C选项中，3出来之后要想出1的话，就必须先出2。

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

A 1

B 2

C 99

D 0

解析：由前面循环队列的实现，很容易就得知此时元素的个数为0。

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

A 从队尾插入一个新元素

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

C 判断一个队列是否为空

D 读取队头元素的值

5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N，实际最多存储N - 1个数据。其队内有效长度为（B）(假设队头不存放数据)

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

B (rear - front + N) % N

C ear - front) % (N + 1)

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

解析：此题要考虑两种情况：

第一种情况：front在rear的前面

第二种情况：front在rear的后面

注意：从最后绕到了最前面其实就相当于在最后面越界继续相加！如下图所示：

综合上面两种情况：最终公式为：

count = (rear - front + N ) % N （为什么第一种也加了N？因为对于front在rear前面的情况来说，是否加N对结果没有任何的影响，因为还要对N进行取模操作）

3. 栈和队列的用途

栈：用来解决括号匹配，逆波兰表达式的求解，递归改非递归等等。

队列：公平排队，广度优先遍历等等。

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/m0_57304511/article/details/124094135

内容来源于网络，如有侵权，请联系作者删除！

数据结构c语言算法链表后端

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com