• 栈和队列oj题

    目录

    225. 用队列实现栈

    描述

    代码

     232. 用栈实现队列

    描述

    代码

    622. 设计循环队列

    描述

    代码

    补录一些概念题目

    结束语

    225. 用队列实现栈

     请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
     

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/implement-stack-using-queues

    描述

    代码

    1.  
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. //能用单链表解决问题就可以用单链表 -- 没必要使用双向循环链表，这属于有点小题大做了
    8.  
    9. typedef int QDataType;
    10. typedef struct QueueNode
    11. {
    12. 	struct QueueNode* next;
    13. 	QDataType data;
    14. }QNode;
    15.  
    16. //再定义一个节点来存放两个指针，方便后面操作
    17. typedef struct Queue
    18. {
    19. 	//尾指针
    20. 	QNode* tail;
    21. 	//头指针
    22. 	QNode* head;
    23. 	int size;
    24. }Queue;
    25.  
    26. //初始化  -- 到现在有三种不用二级指针来初始化结构体了 返回值、哨兵位的头节点和这里的创立一个新的结构体放俩这种
    27. void QueueInit(Queue* pq);
    28.  
    29. //销毁
    30. void QueueDestroy(Queue* pq);
    31.  
    32. //入队列 -- 根据队列的性质 只尾插
    33. void QueuePush(Queue* pq,QDataType x);
    34.  
    35. //出队列 -- 根据队列的性质 只头删
    36. void QueuePop(Queue* pq);
    37.  
    38. //查看头
    39. QDataType QueueFront(Queue* pq);
    40.  
    41. //查看尾
    42. QDataType QueueBack(Queue* pq);
    43.  
    44. //判断是否为空
    45. bool QueueEmpty(Queue* pq);
    46.  
    47. //查看节点长度
    48. int QueueSize(Queue* pq);
    49.  
    50.  
    51. //初始化  -- 到现在有三种不用二级指针来初始化结构体了 返回值、头节点
    52. void QueueInit(Queue* pq)
    53. {
    54. 	assert(pq);	//因为这里是自己创立的节点是不可能为空的，为空就是出问题了
    55. 	pq->head = pq->tail = NULL;
    56. 	pq->size = 0;
    57. }
    58.  
    59. //销毁
    60. void QueueDestroy(Queue* pq)
    61. {
    62. 	assert(pq);
    63. 	QNode* cur = pq->head;
    64. 	while (cur)
    65. 	{
    66. 		QNode* del = cur;
    67. 		cur = cur->next;
    68. 		free(del);
    69. 	}
    70.  
    71. 	pq->head = pq->tail = NULL;	//要改变什么就需要什么的指针，这里置空就可以了
    72. }
    73.  
    74. //入队列 -- 根据队列的性质 只尾插
    75. void QueuePush(Queue* pq, QDataType x)
    76. {
    77. 	assert(pq);
    78. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    79. 	if (newnode == NULL)
    80. 	{
    81. 		perror("malloc fail");
    82. 		exit(-1);
    83. 	}
    84. 	else
    85. 	{
    86. 		newnode->data = x;
    87. 		newnode->next = NULL;	//这里置空，下面就不需要置空了
    88. 	}
    89.  
    90. 	if (pq->tail == NULL)
    91. 	{
    92. 		pq->head = pq->tail = newnode;
    93. 	}
    94. 	else
    95. 	{
    96. 		pq->tail->next = newnode;
    97. 		pq->tail = newnode;
    98. 	}
    99.  
    100. 	pq->size++;
    101. }
    102.  
    103. //出队列 -- 根据队列的性质 只头删
    104. void QueuePop(Queue* pq)
    105. {
    106. 	assert(pq);
    107. 	assert(!QueueEmpty(pq));
    108.  
    109. 	if (pq->head->next == NULL)	//防止只剩下一个节点时候再删，就会导致野指针
    110. 	{
    111. 		free(pq->head);
    112. 		pq->tail = pq->head = NULL;
    113. 	}
    114. 	else
    115. 	{
    116. 		QNode* del = pq->head;
    117. 		pq->head = pq->head->next;
    118.  
    119. 		free(del);
    120. 		del = NULL;
    121. 	}
    122.  
    123. 	pq->size--;
    124. }
    125.  
    126. //查看头
    127. QDataType QueueFront(Queue* pq)
    128. {
    129. 	assert(pq);
    130. 	assert(!QueueEmpty(pq));
    131.  
    132. 	return pq->head->data;
    133. }
    134.  
    135. //查看尾
    136. QDataType QueueBack(Queue* pq)
    137. {
    138. 	assert(pq);
    139. 	assert(!QueueEmpty(pq));
    140.  
    141. 	return pq->tail->data;
    142. }
    143.  
    144. //判断是否为空
    145. bool QueueEmpty(Queue* pq)
    146. {
    147. 	assert(pq);
    148.  
    149. 	return pq->head == NULL && pq->tail == NULL; //理论上两个都应该为空才为空，一般一个为空就都会为空，不是就出问题了
    150. }
    151.  
    152. //查看节点长度
    153. int QueueSize(Queue* pq)
    154. {
    155. 	assert(pq);
    156.  
    157. 	//这样写就变为O(N)级别了 为此需要稍作修改
    158. 	//QNode* cur = pq->head;
    159. 	//int n = 0;
    160. 	//while (cur)
    161. 	//{
    162. 	//	++n;
    163. 	//	cur = cur->next;
    164. 	//}
    165.  
    166. 	//return n;
    167.  
    168. 	return pq->size;
    169. }
    170.  
    171.  
    172.  
    173.  
    174.  
    175.  
    176.  
    177. typedef struct {    //这是一个匿名结构体，不过重命名了所以后面可以继续使用
    178.     Queue q1;
    179.     Queue q2;
    180.  
    181. } MyStack;
    182.  
    183.  
    184. MyStack* myStackCreate() {
    185.     MyStack* obj = (MyStack*)malloc(sizeof(MyStack));   //开辟空间，建立联系，不然出函数就销毁了
    186.     QueueInit(&obj->q1); //初始化里面的结构体
    187.     QueueInit(&obj->q2);
    188.  
    189.     return obj;
    190. }
    191.  
    192. void myStackPush(MyStack* obj, int x) {
    193.     if(!QueueEmpty(&obj->q1))    //如果q1不为空就继续放数据
    194.     {
    195.         QueuePush(&obj->q1 , x);
    196.     }
    197.     else
    198.     {
    199.         QueuePush(&obj->q2 , x);
    200.     }
    201.  
    202. }
    203.  
    204. int myStackPop(MyStack* obj) {
    205.     Queue* Empty = &obj->q1;
    206.     Queue* nonEmpty = &obj->q2;
    207.     if(!QueueEmpty(&obj->q1))   //假设一个为空，再后面判断赋值，使得对应的指针为空
    208.     {
    209.         Empty = &obj->q2;
    210.         nonEmpty = &obj->q1;
    211.     }
    212.  
    213.     //把非空的队列的数据倒到空的队列中去 -- 只要倒n-1个就行了，最后一个弹出来
    214.     while(QueueSize(nonEmpty) > 1)
    215.     {
    216.         QueuePush(Empty ,QueueFront(nonEmpty));
    217.         QueuePop(nonEmpty);
    218.     }
    219.  
    220.     int top = QueueFront(nonEmpty);
    221.     QueuePop(nonEmpty); //top已经保留了数据，弹出去不影响
    222.     return top;
    223. }
    224.  
    225. int myStackTop(MyStack* obj) {
    226.  
    227.     if(!QueueEmpty(&obj->q1))    //如果队列里面不为就出返回队列尾部的数据
    228.     {
    229.         return QueueBack(&obj->q1);
    230.     }
    231.     else
    232.     {
    233.         return  QueueBack(&obj->q2);
    234.     }
    235.  
    236.  
    237. }
    238.  
    239. bool myStackEmpty(MyStack* obj) {
    240.     //两个为空才为空，因为这里会报持一个队列为空
    241.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    242. }
    243.  
    244. void myStackFree(MyStack* obj) {
    245. //这里要单独把释放，因为它们开辟的空间仅仅释放obj是释放不掉的
    246.     QueueDestroy(&obj->q1);
    247.     QueueDestroy(&obj->q2);
    248.  
    249.     free(obj);
    250. }
    251.

     232. 用栈实现队列

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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) ，即使其中一个操作可能花费较长时间。

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/implement-queue-using-stacks

     

    描述

     

    代码

    1.  
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7.  
    8. typedef int STDataType;
    9. typedef struct Stack
    10. {
    11. 	STDataType* a;
    12. 	int top;		//数据
    13. 	int capacity;	//空间容量
    14. }ST;
    15.  
    16. //初始化
    17. void StackInit(ST* ps);
    18.  
    19. //销毁
    20. void StackDestroy(ST* ps);
    21.  
    22. //入栈
    23. void StackPush(ST* ps , STDataType x);	//根据栈的概念 栈只有一个地方可以插入
    24.  
    25. //出栈
    26. void StackPop(ST* ps);
    27.  
    28. //访问Top位置
    29. STDataType StackTop(ST* ps);
    30.  
    31. //检查是否为空
    32. bool StackEmpty(ST* ps);
    33.  
    34. //查看数据数量
    35. int StackSize(ST* ps);	//调用函数来实现 -- 数据结构建议不要直接访问结构数据，一定要通过函数接口访问
    36. 						//解耦 -- 高内聚，低耦合
    37.  
    38.  
    39. //初始化
    40. void StackInit(ST* ps)
    41. {
    42. 	assert(ps);
    43. 	ps->a = NULL;
    44. 	ps->capacity = ps->top = 0;
    45. }
    46.  
    47. //销毁
    48. void StackDestroy(ST* ps)
    49. {
    50. 	assert(ps);
    51.  
    52. 	free(ps->a);
    53. 	ps->a = NULL;
    54. 	ps->capacity = ps->top = 0;
    55. }
    56.  
    57. //入栈
    58. void StackPush(ST* ps, STDataType x)
    59. {
    60. 	assert(ps);
    61. 	//扩容
    62. 	if (ps->top == ps->capacity)	//根据初始化的内容来判断
    63. 	{
    64. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    65. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
    66. 		if (tmp == NULL)
    67. 		{
    68. 			perror("realloc fail");
    69. 			exit(-1);
    70. 		}
    71. 		ps->a = tmp;
    72. 		ps->capacity = newCapacity;
    73. 	}
    74.  
    75.  
    76. 	ps->a[ps->top] = x;
    77. 	ps->top++;
    78.  
    79. }
    80.  
    81. //出栈
    82. void StackPop(ST* ps)
    83. {
    84. 	assert(ps);
    85. 	assert(!StackEmpty(ps));
    86.  
    87. 	--ps->top;
    88. }
    89.  
    90. //访问Top位置
    91. STDataType StackTop(ST* ps)
    92. {
    93. 	assert(ps);
    94. 	assert(!StackEmpty(ps));
    95.  
    96. 	return ps->a[ps->top - 1];
    97. }
    98.  
    99. //检查是否为空
    100. bool StackEmpty(ST* ps)
    101. {
    102. 	assert(ps);
    103. 	return ps->top == 0;
    104. }
    105.  
    106. //查看数据数量
    107. int StackSize(ST* ps)
    108. {
    109. 	assert(ps);
    110.  
    111. 	return ps->top; //这里的top刚好是数据的下一个位置，自然就是数据个数
    112. }
    113.  
    114.  
    115.  
    116. typedef struct {
    117.     ST pushST;
    118.     ST popST;
    119. } MyQueue;
    120.  
    121.  
    122. MyQueue* myQueueCreate() {
    123.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    124.     StackInit(&obj->pushST);
    125.     StackInit(&obj->popST);
    126.  
    127.     return obj;
    128. }
    129.  
    130. void myQueuePush(MyQueue* obj, int x) {
    131.  
    132.     StackPush(&obj->pushST,x);    //把数据放到pushST里面，专门放数据
    133.  
    134. }
    135.  
    136. //额外写的一个接口函数，专门用来倒数据的
    137. void PushTToPopST(MyQueue* obj)
    138. {
    139.     if(StackEmpty(&obj->popST))
    140.     {
    141.         while(!StackEmpty(&obj->pushST))
    142.         {
    143.             StackPush(&obj->popST, StackTop(&obj->pushST));
    144.             StackPop(&obj->pushST);
    145.         }
    146.  
    147.     }
    148.  
    149. }
    150.  
    151. int myQueuePop(MyQueue* obj) {
    152.     PushTToPopST(obj);
    153.  
    154.     int front = StackTop(&obj->popST);
    155.     StackPop(&obj->popST);
    156.  
    157.     return front;
    158. }
    159.  
    160. int myQueuePeek(MyQueue* obj) {
    161.  
    162.     PushTToPopST(obj);
    163.  
    164.     return StackTop(&obj->popST);
    165.  
    166. }
    167.  
    168. bool myQueueEmpty(MyQueue* obj) {
    169.  
    170.     return  StackEmpty(&obj->pushST)
    171.         &&  StackEmpty(&obj->popST);
    172. }
    173.  
    174. void myQueueFree(MyQueue* obj) {
    175.     StackDestroy(&obj->popST);
    176.     StackDestroy(&obj->pushST);
    177.  
    178.     free(obj);
    179. }

    622. 设计循环队列

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

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

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/design-circular-queue

    描述

     

    代码

    1. typedef struct {
    2.     int* a;
    3.     int front;  //头部
    4.     int back;   //尾部
    5.     int N;  //存储空间
    6. } MyCircularQueue;
    7.  
    8.  
    9. MyCircularQueue* myCircularQueueCreate(int k) {
    10.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    11.     obj->a = (int*)malloc(sizeof(int)*(k+1)); //多开一个数据空间
    12.     obj->front = obj->back = 0;
    13.     obj->N = k+1;   //实际空间长度
    14.  
    15.     return obj;
    16. }
    17.  
    18. //这两个接口从下面移到了上面
    19. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    20.  
    21.     return obj->front == obj->back; //当两个相等的时候就为空，因为back指的是下一个位置
    22. }
    23.  
    24. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    25.  
    26.         return  (obj->back+1)% obj->N == obj->front;
    27. }
    28.  
    29. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    30.     if(myCircularQueueIsFull(obj))
    31.         return false;
    32.     
    33.     obj->a[obj->back] = value;
    34.     obj->back++;
    35.     obj->back %= obj->N;    //控制back位置，到尾的时候就回到0的位置
    36.  
    37.     return true;
    38. }
    39.  
    40. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    41.  
    42.     if(myCircularQueueIsEmpty(obj))
    43.         return false;
    44.  
    45.     obj->front++;
    46.     //控制front位置，假如到了空间尾以后，back回到0的位置
    47.     obj->front %= obj->N;
    48.  
    49.     return true;
    50. }
    51.  
    52. //返回队头的数据
    53. int myCircularQueueFront(MyCircularQueue* obj) {
    54.         if(myCircularQueueIsEmpty(obj))
    55.             return -1;  //题目要求失败返回-1
    56.         else
    57.             return obj->a[obj->front];
    58.  
    59. }
    60.  
    61. //返回队尾的数据
    62. int myCircularQueueRear(MyCircularQueue* obj) {
    63.         if(myCircularQueueIsEmpty(obj))
    64.             return -1;
    65.         else
    66.             return obj->a[(obj->back -1 +obj->N)% obj->N] ;   //返回前一个位置的数据，因为这里实现的back指向尾的后一个，但是要注意端点的情况
    67. }
    68.  
    69.  
    70.  
    71. void myCircularQueueFree(MyCircularQueue* obj) {
    72.     free(obj->a);
    73.     free(obj);
    74. }

    补录一些概念题目

    下面有一道题目是与 int myCircularQueueRear(MyCircularQueue* obj) 这个接口相关的

     

    选择查看答案 

    3.D
    4.B
    5.B

    结束语 

    世事一场大梦，人生几度秋凉？

                                                   苏轼《西江月》

  • 相关阅读:
    数据结构——3道栈和队列OJ题
    Activiti工作流引擎详解与应用
    【数学建模】MATLAB应用实战系列（八十八）-组合权重法应用案例（附MATLAB和Python代码）
    qsort函数使用方法总结
    卡尔曼滤波介绍
    简化磁盘分区管理的 6 个分区管理器软件！
    2022年全国职业院校技能大赛：网络系统管理项目-模块B--Windows样题2
    JDBC学习篇(四)
    HTML基础笔记
    高性能同轴高清 ISP芯片XS5012A参数
  • 原文地址：https://blog.csdn.net/weixin_67595436/article/details/126242512