• 【C语言】栈和队列的相互实现

    目录

    用队列实现栈

    代码实现

    完整代码

    用栈实现队列

     代码实现

    完整代码

    用队列实现栈

    力扣链接：用队列实现栈

    这个题目，使用队列模拟实现栈，我们是使用C语言来实现，由于C语言没有相应的库所以我们要先手写一个队列出来，在此之前我们还要对队列和栈的性质有所了解 ，可以参考我之前写的文章——（队列的模拟实现）和（栈的模拟实现）

    方法：两个队列

    为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。所以我们可以使用两个队列实现栈的操作，其中一个队列用来存储栈内的元素，另一个队列用来倒数据。

    入栈操作：把数据入队到其中一个队列中，另一个队列保持为空队列。

    出栈操作：将存储了栈内元素的队列倒到另一个空的队列中，当倒了只剩下一个数据时停止，将这个数据出队就达到了出栈的效果。

      

    代码实现

     创建两个队列

    1. typedef struct
    2.  {
    3.     Queue q1;
    4.     Queue q2;
    5. } MyStack;

    初始化 

    1. MyStack* myStackCreate() {
    2.     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    3.     QueueInit(&obj->q1);
    4.     QueueInit(&obj->q2);
    5.     return obj;
    6. }

     首先看一下这样写行不行？

    这样写当然是不行的，因为它是带返回值的，所以我们要返回我们创建的地址，但是st是局部变量，出了这个函数就销毁了，那你接受到的只能是野指针。

    所以这里只能用静态的或者malloc动态的，出了这个函数也不会被销毁，但是malloc更好，那我们就用malloc的，然后初始化这两个队列 就行了。

    入栈

    1. void myStackPush(MyStack* obj, int x) {
    2.     if(!QueueEmpty(&obj->q1))
    3.     {
    4.         QueuePush(&obj->q1,x);
    5.     }
    6.     else
    7.     {
    8.         QueuePush(&obj->q2,x);
    9.     }
    10. }

     入栈就很简单了，我们就向队列不为空的入数据，如果两个队列都为空，向哪个队列入数据都行。

    出栈

    1. int myStackPop(MyStack* obj) {
    2.     Queue* emptyQ=&obj->q1;
    3.     Queue* nonEmptyQ=&obj->q2;
    4.     if(!QueueEmpty(&obj->q1))
    5.     {
    6.         emptyQ=&obj->q2;
    7.         nonEmptyQ=&obj->q1;
    8.     }
    9.     while(QueueSize(nonEmptyQ)>1)
    10.     {
    11.         QueuePush(emptyQ,QueueFront(nonEmptyQ));
    12.         QueuePop(nonEmptyQ);
    13.     }
    14.     int top=QueueFront(nonEmptyQ);
    15.     QueuePop(nonEmptyQ);
    16.     return top;
    17. }

     这里就需要倒数据了，但是我们不知道哪个为空，哪个不为空，我们可以用假设法。先假设一个为空 ，一个不为空，再来一个if语句判断一下，确定哪个为空，哪个不为空。然后将非空队列的数据倒入空的队列中去，当非空对列倒的只剩下一个数据时就停止，最后pop掉这个数据。

     获取栈顶元素

    1. int myStackTop(MyStack* obj) {
    2.     if(!QueueEmpty(&obj->q1))
    3.     {
    4.        return QueueBack(&obj->q1);
    5.     }
    6.     else
    7.     {
    8.        return QueueBack(&obj->q2);
    9.     }
    10. }

    因为我们是用队列来模拟实现栈的，那我们既可以取到对头的数据，也可以取到队尾的数据，这里我们只用取队尾的数据就行了，只需判断哪个不为空，取那个就行。 

    判空 

    1. bool myStackEmpty(MyStack* obj) {
    2.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    3. }

    注意这里是&&而不是|| ，我们是用两个队列来模拟栈，只有当两个队列都为空时，栈才是空。

    销毁栈

    1. void myStackFree(MyStack* obj) {
    2.     QueueDestroy(&obj->q1);
    3.     QueueDestroy(&obj->q2);
    4.  
    5.     free(obj);
    6. }

     我们不仅要销毁这两个队列，还要free掉队列中指针指向的链表。

    完整代码

    1.  
    2. typedef int QDataType;
    3. typedef struct QueueNode
    4. {
    5. 	struct QueueNode* next;
    6. 	QDataType data;
    7. }QNode;
    8.  
    9. typedef struct Queue
    10. {
    11. 	int size;
    12. 	QNode* head;
    13. 	QNode* tail;
    14. }Queue;
    15.  
    16. //初始化队列
    17. void QueueInit(Queue* pq);
    18.  
    19. //销毁队列
    20. void QueueDestroy(Queue* pq);
    21.  
    22. //对尾入队列
    23. void QueuePush(Queue* pq, QDataType x);
    24.  
    25. //对头出队列
    26. void QueuePop(Queue* pq);
    27.  
    28. //获取对列头部元素
    29. QDataType QueueFront(Queue* pq);
    30.  
    31. //获取队列队尾元素
    32. QDataType QueueBack(Queue* pq);
    33.  
    34. //判空
    35. bool QueueEmpty(Queue* pq);
    36.  
    37. //获取队列中有效元素的个数
    38. int QueueSize(Queue* pq);
    39.  
    40. void QueueInit(Queue* pq)
    41. {
    42. 	assert(pq);
    43. 	pq->size = 0;
    44. 	pq->head = pq->tail = NULL;
    45. }
    46.  
    47. void QueueDestroy(Queue* pq)
    48. {
    49. 	assert(pq);
    50. 	QNode* cur = pq->head;
    51. 	while (cur)
    52. 	{
    53. 		QNode* next = cur->next;
    54. 		free(cur);
    55. 		cur = next;
    56. 	}
    57. 	pq->head = pq->tail = NULL;
    58. }
    59.  
    60. void QueuePush(Queue* pq, QDataType x)
    61. {
    62. 	assert(pq);
    63. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    64. 	if (newnode == NULL)
    65. 	{
    66. 		printf("malloc fail\n");
    67. 		exit(-1);
    68. 	}
    69. 	newnode->data = x;
    70. 	newnode->next = NULL;
    71.  
    72. 	if (pq->tail == NULL)
    73. 	{
    74. 		pq->head = pq->tail = newnode;
    75. 	}
    76. 	else
    77. 	{
    78. 		pq->tail->next = newnode;
    79. 		pq->tail = newnode;
    80. 	}
    81. 	pq->size++;
    82. }
    83.  
    84. void QueuePop(Queue* pq)
    85. {
    86. 	assert(pq);
    87. 	assert(!QueueEmpty(pq));
    88.  
    89. 	//1.一个节点
    90. 	if (pq->head->next == NULL)
    91. 	{
    92. 		free(pq->head);
    93. 		pq->head = pq->tail = NULL;//避免野指针问题
    94. 	}
    95. 	//2.多个节点
    96. 	else
    97. 	{
    98. 		QNode* next = pq->head->next;
    99. 		free(pq->head);
    100. 		pq->head = next;
    101. 	}
    102. 	pq->size--;
    103. }
    104.  
    105. QDataType QueueFront(Queue* pq)
    106. {
    107. 	assert(pq);
    108. 	assert(!QueueEmpty(pq));
    109. 	return pq->head->data;
    110. }
    111.  
    112. QDataType QueueBack(Queue* pq)
    113. {
    114. 	assert(pq);
    115. 	assert(!QueueEmpty(pq));
    116. 	return pq->tail->data;
    117. }
    118.  
    119. bool QueueEmpty(Queue* pq)
    120. {
    121. 	assert(pq);
    122. 	return pq->head == NULL;
    123. }
    124.  
    125. int QueueSize(Queue* pq)
    126. {
    127. 	assert(pq);
    128. 	/*int size = 0;
    129. 	QNode* cur = pq->head;
    130. 	while (cur)
    131. 	{
    132. 		size++;
    133. 		cur = cur->next;
    134. 	}*/
    135. 	return pq->size;
    136. }
    137.  
    138. typedef struct
    139.  {
    140.     Queue q1;
    141.     Queue q2;
    142. } MyStack;
    143.  
    144.  
    145. MyStack* myStackCreate() {
    146.     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    147.     QueueInit(&obj->q1);
    148.     QueueInit(&obj->q2);
    149.     return obj;
    150. }
    151.  
    152. void myStackPush(MyStack* obj, int x) {
    153.     if(!QueueEmpty(&obj->q1))
    154.     {
    155.         QueuePush(&obj->q1,x);
    156.     }
    157.     else
    158.     {
    159.         QueuePush(&obj->q2,x);
    160.     }
    161. }
    162.  
    163. int myStackPop(MyStack* obj) {
    164.     Queue* emptyQ=&obj->q1;
    165.     Queue* nonEmptyQ=&obj->q2;
    166.     if(!QueueEmpty(&obj->q1))
    167.     {
    168.         emptyQ=&obj->q2;
    169.         nonEmptyQ=&obj->q1;
    170.     }
    171.     while(QueueSize(nonEmptyQ)>1)
    172.     {
    173.         QueuePush(emptyQ,QueueFront(nonEmptyQ));
    174.         QueuePop(nonEmptyQ);
    175.     }
    176.     int top=QueueFront(nonEmptyQ);
    177.     QueuePop(nonEmptyQ);
    178.     return top;
    179. }
    180.  
    181. int myStackTop(MyStack* obj) {
    182.     if(!QueueEmpty(&obj->q1))
    183.     {
    184.        return QueueBack(&obj->q1);
    185.     }
    186.     else
    187.     {
    188.        return QueueBack(&obj->q2);
    189.     }
    190. }
    191.  
    192. bool myStackEmpty(MyStack* obj) {
    193.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    194. }
    195.  
    196. void myStackFree(MyStack* obj) {
    197.     QueueDestroy(&obj->q1);
    198.     QueueDestroy(&obj->q2);
    199.  
    200.     free(obj);
    201. }

    用栈实现队列

    力扣链接：用栈实现队列

    这个题目是用栈实现队列，我们依然使用C语言来写，C语言没有相应的库，所以我们还是要先手写一个栈才能实现题目中要求的函数接口。

    方法：两个栈

    一个队列是先进先出，一个栈是先进后出，新进的数据肯定是在栈底。我们可以这样做，指定一个栈专门进数据，指定另外一个栈专门出数据。

    入队操作：向push栈中入数据。

     出对操作：将push栈中的数据全部倒入pop栈中，pop栈中数据的顺序刚好与push栈中的数据顺序相反，正好满足队列的性质，最后在push栈的栈顶出数据就行了。

     

     代码实现

    创建两个栈

    1. typedef struct {
    2.     ST pushst;
    3.     ST popst;
    4. } MyQueue;

     指定一个栈专门进数据，指定另外一个栈专门出数据。

    初始化

    1. MyQueue* myQueueCreate() {
    2.     MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    3.     StackInit(&obj->pushst);
    4.     StackInit(&obj->popst);
    5.     return obj;
    6. }

    销毁队列

    1. void myQueueFree(MyQueue* obj) {
    2.     StackDestroy(&obj->popst);
    3.     StackDestroy(&obj->pushst);
    4.     free(obj);
    5. }

    初始化和销毁队列的方法和上面题目的方法一致，就不多讲了。

    入队

    1. void myQueuePush(MyQueue* obj, int x) {
    2.     StackPush(&obj->pushst,x);
    3. }

     入对只需要push进栈就行啦。

    出队

    1. int myQueuePop(MyQueue* obj) {
    2.     if(StackEmpty(&obj->popst))
    3.     {
    4.         //如果pop栈为空，则把push栈的数据倒过来
    5.         while(!StackEmpty(&obj->pushst))
    6.         {
    7.             StackPush(&obj->popst,StackTop(&obj->pushst));
    8.             StackPop(&obj->pushst);
    9.         }
    10.     }
    11.     int front=StackTop(&obj->popst);
    12.     StackPop(&obj->popst);
    13.     return front;
    14. }

     首先要判断一下popst栈为不为空，如果为空，则把push栈的数据倒过来，不为空就直接在pop栈出数据。

    取对头元素

    1. int myQueuePeek(MyQueue* obj) {
    2.      if(StackEmpty(&obj->popst))
    3.     {
    4.         //如果pop栈为空，则把push栈的数据倒过来
    5.         while(!StackEmpty(&obj->pushst))
    6.         {
    7.             StackPush(&obj->popst,StackTop(&obj->pushst));
    8.             StackPop(&obj->pushst);
    9.         }
    10.     }
    11.     return StackTop(&obj->popst);
    12. }

     这个就简单了，只需要取pop栈的栈顶的数据返回就可以了。

    判空

    1. bool myQueueEmpty(MyQueue* obj) {
    2.     return StackEmpty(&obj->popst)&&StackEmpty(&obj->pushst);
    3. }

    两个栈等于一个队列，所以两个栈都需要判空。 和上面的题目一样。

    完整代码

    1.  
    2. typedef int STDataType;
    3. typedef struct Stack
    4. {
    5. 	STDataType* a;
    6. 	int top;
    7. 	int capacity;
    8. }ST;
    9.  
    10. //初始化栈
    11. void StackInit(ST* ps);
    12.  
    13. //销毁栈
    14. void StackDestroy(ST* ps);
    15.  
    16. //进栈
    17. void StackPush(ST* ps, STDataType x);
    18.  
    19. //出栈
    20. void StackPop(ST* ps);
    21.  
    22. //获取栈顶元素
    23. STDataType StackTop(ST* ps);
    24.  
    25. //判空
    26. bool StackEmpty(ST* ps);
    27.  
    28. //栈的元素个数
    29. int StackSize(ST* ps);
    30. void StackInit(ST* ps)
    31. {
    32. 	assert(ps);
    33. 	ps->a = NULL;
    34. 	ps->top = 0;
    35. 	ps->capacity = 0;
    36. }
    37.  
    38. void StackDestroy(ST* ps)
    39. {
    40. 	assert(ps);
    41. 	free(ps->a);
    42. 	ps->a = NULL;
    43. 	ps->top = ps->capacity = 0;
    44. }
    45.  
    46. void StackPush(ST* ps, STDataType x)
    47. {
    48. 	assert(ps);
    49. 	if (ps->top == ps->capacity)
    50. 	{
    51. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    52. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)* newcapacity);
    53. 		if (tmp == NULL)
    54. 		{
    55. 			printf("realloc fail\n");
    56. 			exit(-1);
    57. 		}
    58. 		ps->a = tmp;
    59. 		ps->capacity = newcapacity;
    60. 	}
    61. 	ps->a[ps->top] = x;
    62. 	ps->top++;
    63. }
    64.  
    65. void StackPop(ST* ps)
    66. {
    67. 	assert(ps);
    68. 	assert(!StackEmpty(ps));
    69. 	ps->top--;
    70. }
    71.  
    72. STDataType StackTop(ST* ps)
    73. {
    74. 	assert(ps);
    75. 	assert(!StackEmpty(ps));
    76. 	return ps->a[ps->top - 1];
    77. }
    78.  
    79. bool StackEmpty(ST* ps)
    80. {
    81. 	assert(ps);
    82. 	return ps->top == 0;
    83. }
    84.  
    85. int StackSize(ST* ps)
    86. {
    87. 	assert(ps);
    88. 	return ps->top;
    89. }
    90.  
    91. typedef struct {
    92.     ST pushst;
    93.     ST popst;
    94. } MyQueue;
    95.  
    96.  
    97. MyQueue* myQueueCreate() {
    98.     MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    99.     StackInit(&obj->pushst);
    100.     StackInit(&obj->popst);
    101.     return obj;
    102. }
    103.  
    104. void myQueuePush(MyQueue* obj, int x) {
    105.     StackPush(&obj->pushst,x);
    106. }
    107.  
    108. int myQueuePop(MyQueue* obj) {
    109.     if(StackEmpty(&obj->popst))
    110.     {
    111.         //如果pop栈为空，则把push栈的数据倒过来
    112.         while(!StackEmpty(&obj->pushst))
    113.         {
    114.             StackPush(&obj->popst,StackTop(&obj->pushst));
    115.             StackPop(&obj->pushst);
    116.         }
    117.     }
    118.     int front=StackTop(&obj->popst);
    119.     StackPop(&obj->popst);
    120.     return front;
    121. }
    122.  
    123. int myQueuePeek(MyQueue* obj) {
    124.      if(StackEmpty(&obj->popst))
    125.     {
    126.         //如果pop栈为空，则把push栈的数据倒过来
    127.         while(!StackEmpty(&obj->pushst))
    128.         {
    129.             StackPush(&obj->popst,StackTop(&obj->pushst));
    130.             StackPop(&obj->pushst);
    131.         }
    132.     }
    133.     return StackTop(&obj->popst);
    134. }
    135.  
    136. bool myQueueEmpty(MyQueue* obj) {
    137.     return StackEmpty(&obj->popst)&&StackEmpty(&obj->pushst);
    138. }
    139.  
    140. void myQueueFree(MyQueue* obj) {
    141.     StackDestroy(&obj->popst);
    142.     StackDestroy(&obj->pushst);
    143.     free(obj);
    144. }

    总结：这两个题目是很相似的，你会写其中一个，那么另一个也不是什么难事。

  • 相关阅读:
    vscode Markdown使用
    MyCat2搭建读写分离
    Linux常用的命令和一些基础知识
    为什么程序员会秃头？盘点程序员糟心的几大因素
    PicGo+Gitee+Typora搭建云图床
    【Java】基础练习 --- Stream练习
    【CUDA编程】CUDA内存模型
    AIGC——ComfyUI 安装与基础使用
    BE节点经常挂掉：[IO_ERROR]failed to list /proc/27349/fd/: No such file or directory
    数据中台基础
  • 原文地址：https://blog.csdn.net/m0_62537611/article/details/125523833