• 【数据结构与算法】＜==＞栈和队列的OJ题

    作者：旧梦拾遗186

    专栏：数据结构成长日记

     

    目录

    用队列实现栈

    用栈实现队列

    循环队列设计

    循环队列的概念选择题

    用队列实现栈

     

    用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/

    请你仅使用两个队列实现一个后入先出（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 都保证栈不为空
     

    进阶：你能否仅用一个队列来实现栈。

    解答

    题目的意思其实很简单：就是让你用两个队列去模拟实现一个栈

    思路：思路其实很简单，我们知道队列是先进先出，而栈是后进先出，两个最大的不同在于顺序：

    我们假设在队列入了1，2，3，4那么现在要在队列中出一个元素，那就是1
    如果在栈中入了1，2，3，4那么现在要在栈中出一个元素，那就是4

    我们该怎么改变这种顺序呢？很简单，让有元素队列把前n-1个导入到空的队列，此时取出剩下的元素就是符合栈顺序的元素，我们不妨来画个图：

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

     

    用栈实现队列

    用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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 操作）
     

    进阶：

    你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

    题解

    这道题和上面的那道题是相反的，这里要让你用两个栈去实现队列，思路也是差不多的，但是对于两个栈来说，就存在一些差别了：我们还是以入栈1、2、3、4来举例子：

    只要导一次就可以了，这跟上边的题不一样，倒过去后顺序的相反的。 

     所以两个栈我们可以一个为PopST进行出数据的操作，出空了，再去另一个栈PushST将数据倒过来，仔细琢磨琢磨

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. //手撸一个栈
    7. typedef int STDataType;
    8. typedef struct Stack
    9. {
    10. 	STDataType*a;
    11. 	int top;
    12. 	int capacity;
    13. }ST;
    14.  
    15. void StackInit(ST* ps);
    16.  
    17. void StackDestory(ST* ps);
    18.  
    19. void StackPush(ST* ps,STDataType x);
    20.  
    21. void StackPop(ST* ps);
    22.  
    23. STDataType StackTop(ST* ps);
    24.  
    25. bool StackEmpty(ST*ps);
    26.  
    27. int StackSize(ST* ps);
    28.  
    29. void StackInit(ST* ps)
    30. {
    31. 	assert(ps);
    32. 	ps->a = NULL;
    33. 	ps->capacity = ps->top = 0;
    34. }
    35.  
    36. void StackDestory(ST* ps)
    37. {
    38. 	assert(ps);
    39. 	free(ps->a);
    40. 	ps->a = NULL;
    41. 	ps->capacity = ps->top = 0;
    42. }
    43.  
    44. void StackPush(ST* ps, STDataType x)
    45. {
    46. 	assert(ps);
    47. 	if (ps->top == ps->capacity)
    48. 	{
    49. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    50. 		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    51. 		if (NULL == tmp)
    52. 		{
    53. 			perror("malloc fail");
    54. 			exit(-1);
    55. 		}
    56. 		ps->a = tmp;
    57. 		ps->capacity = newCapacity;
    58. 	}
    59. 	ps->a[ps->top] = x;
    60. 	ps->top++;
    61. 	
    62. }
    63.  
    64. void StackPop(ST* ps)
    65. {
    66. 	assert(ps);
    67. 	assert(!StackEmpty(ps));
    68. 	ps->top--;
    69. }
    70.  
    71. STDataType StackTop(ST* ps)
    72. {
    73. 	assert(ps);
    74. 	assert(!StackEmpty(ps));
    75. 	return ps->a[ps->top - 1];
    76. }
    77.  
    78. bool StackEmpty(ST* ps)
    79. {
    80. 	assert(ps);
    81. 	return ps->top == 0;
    82. }
    83.  
    84. int StackSize(ST* ps)
    85. {
    86. 	assert(ps);
    87. 	return ps->top;
    88. }
    89.  
    90.  
    91.  
    92. typedef struct {
    93.     ST pushST;
    94.     ST popST;
    95.  
    96.  
    97. } MyQueue;
    98.  
    99.  
    100. MyQueue* myQueueCreate() {
    101.     MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    102.  
    103.     StackInit(&obj->pushST);
    104.     StackInit(&obj->popST);
    105.     return obj;
    106.  
    107. }
    108. //入队
    109. void myQueuePush(MyQueue* obj, int x) {
    110. //有数据就直接进入pushST栈
    111.      StackPush(&obj->pushST,x);
    112.  
    113. }
    114. void pushSTtopopST(MyQueue* obj)
    115. {
    116.     //先把popST栈的数据出栈，如果没有数据就让pushST栈的数据进入
    117.     if(StackEmpty(&obj->popST))
    118.     {
    119.         while(!StackEmpty(&obj->pushST))
    120.  
    121.         {
    122.             StackPush(&obj->popST,StackTop(&obj->pushST));
    123.             StackPop(&obj->pushST);
    124.         }
    125.  
    126.     }
    127. }
    128. //出队
    129. int myQueuePop(MyQueue* obj) {
    130.     pushSTtopopST(obj);
    131.     int front=StackTop(&obj->popST);
    132.     StackPop(&obj->popST);
    133.     return front;
    134.  
    135. }
    136. //取队头元素
    137. int myQueuePeek(MyQueue* obj) {
    138.     pushSTtopopST(obj);
    139.     return StackTop(&obj->popST);
    140.  
    141. }
    142.  
    143. bool myQueueEmpty(MyQueue* obj) {
    144.     return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
    145.  
    146. }
    147.  
    148. void myQueueFree(MyQueue* obj) {
    149.     StackDestory(&obj->popST);
    150.     StackDestory(&obj->pushST);
    151.  
    152. }
    153.  
    154. /**
    155.  * Your MyQueue struct will be instantiated and called as such:
    156.  * MyQueue* obj = myQueueCreate();
    157.  * myQueuePush(obj, x);
    158.  
    159.  * int param_2 = myQueuePop(obj);
    160.  
    161.  * int param_3 = myQueuePeek(obj);
    162.  
    163.  * bool param_4 = myQueueEmpty(obj);
    164.  
    165.  * myQueueFree(obj);
    166. */

     

    循环队列设计

    另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型
    时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

     

    设计循环队列icon-default.png?t=M666https://leetcode.cn/problems/design-circular-queue/

     

    设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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 的范围内；
    请不要使用内置的队列库。

    题解

     

    下面我们来看一看上面的题目：

    对于结构体的定义：我们需要一个数组存放数据，同时还有队头和队尾，以及空间的大小。

    我们来区分一下如何判断是否为空和是否为满的情况：

    空的时候，队头==队尾

    满的时候，(队尾+1)%空间的大小==队头。

    当判断对满是要考虑到如图的特殊情况此时，back在front前，此时还需要（back+1）%N的操作。

     

    后面一些细节的东西，我们直接来看代码：

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

     

     

    循环队列的概念选择题

    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)
    1.B
    2.C
    3.D
    4.B
    5.B

     

  • 相关阅读:
    Process.Start() 报错:系统找不到指定文件
    小度打头阵，百度大模型能否“赋能万物”？
    C++ map容器用法
    数据链路与MAC帧
    dsu on tree模板
    如何使用ChatGPT辅助写论文、数据分析、AI绘图？【附学习资料】
    注意论文投稿风险，现投期刊会不会成为预警期刊呢？
    MYSQL：Select语句顺序
    开源B2B网站电子商务平台源码下载搭建 实现高效交易的桥梁
    应用案例 | 使用dataFEED OPC Suite将汽车零部件工厂数据集成到SAP Business Suite
  • 原文地址：https://blog.csdn.net/weixin_67900732/article/details/126299269