• 力扣在线OJ——栈和队列

    目录

    🍁一、用两个队列实现栈

    🌕（一）、题目（力扣链接：用队列实现栈 ）

    🌕（二）、注意

    🌕（三）、解答

    ⭐️1.注意事项

    ⭐️2.第一个接口——匿名结构体

    ⭐️3.第二个接口——MyStack* myStackCreate()

    ⭐️4.第三个接口——void myStackPush(MyStack* obj, int x)

    ⭐️5.第四个接口——int myStackPop(MyStack* obj)

    ⭐️6.第五个接口——int myStackTop(MyStack* obj)

    ⭐️7.第六个接口——bool myStackEmpty(MyStack* obj)

    ⭐️8.第七个接口——void myStackFree(MyStack* obj)

    🌕（四）、第一题源代码

    ⭐️1.代码：

    ⭐️2.运行结果：

    🍁二、用栈实现队列

    🌕（一）、题目（力扣链接：用栈实现队列）

    🌕（二）、思路

    🌕（三）、解答

    ⭐️1.第一个接口——typedef struct

    ⭐️2.第二个接口——MyQueue* myQueueCreate()

    ⭐️3.第三个接口——void myQueuePush(MyQueue* obj, int x)

    ⭐️4.第四个接口——int myQueuePop(MyQueue* obj)

    ⭐️5.第五个接口——int myQueuePeek(MyQueue* obj)

    ⭐️6.第六个接口——bool myQueueEmpty(MyQueue* obj)

    ⭐️7.第七个接口——void myQueueFree(MyQueue* obj)

    🌕（四）、第二题源代码

    🍁一、用两个队列实现栈

    🌕（一）、题目（力扣链接：用队列实现栈 ）

    🌕（二）、注意

    与以前不同的是，这次的OJ的练习给了几个函数接口，这几个函数接口就是栈的操作的接口，我们需要用队列来实现，如下：

    这需要我们根据函数名来猜测一下每个函数的作用是什么，分析清楚了才能去考虑如何写代码，这大大增加了难度。

    🌕（三）、解答

    ⭐️1.注意事项

    （1）.这道题的意思就是，这里又两个队列，并且只提供了队列操作的几个接口，如下：

    然后叫我们实现出一个栈；

    （2）.首先我们没有队列，所以可以将上一次我们实现的队列复制粘贴过来，因为C语言库里面没有，所以我们要自己实现，等以后我们学习C++，就可以直接使用C++的库里面的各种东西，比如栈和队列就可以直接使用；

    ⭐️2.第一个接口——匿名结构体

    这是一个匿名结构体，感兴趣的小伙伴可以去了解一下，我们是可以更改里面的内容的，我们需要两个队列，所以把里面的内容改为两个队列；

    这样后续，我们可以通过MyStack栈来操作两个队列，即用两个队列实现栈。

    ⭐️3.第二个接口——MyStack* myStackCreate()

    ①：看函数名的意思就是“我的栈的初始化”；

    ②:操作很简单，首先先创建一个MyStack栈的指针，然后为其动态分配空间；

    然后在使用我们自己的队列接口Queueinit，对栈的成员Que1和Que2进行初始化：

    1. //栈的初始化
    2. MyStack* myStackCreate() {
    3. MyStack *pst=(MyStack*)malloc(sizeof(MyStack));
    4. Queueinit(&pst->q1);
    5. Queueinit(&pst->q2);
    6. return pst;
    7. }
    ⭐️4.第三个接口——void myStackPush(MyStack* obj, int x)

    ①：很显然就是“入栈操作”；

    ②：入栈很简单，我们只需要将入栈的元素入到不为空的队列中即可；

    这样就会呈现出一个队列为空，一个队列不为空的局面，方便我们后出栈的思路：

    1.  
    2. //入栈
    3. void myStackPush(MyStack* obj, int x) {
    4. //根据思路分析，哪个队列不为空，就入队哪个队列
    5. if(!QueueEmpty(&obj->q1))
    6. {
    7.     QueuePush(&obj->q1,x);
    8. }
    9. else
    10. {
    11.     QueuePush(&obj->q2,x);
    12. }
    13. }
    ⭐️5.第四个接口——int myStackPop(MyStack* obj)

    ①：按函数名就是“出栈操作”的意思；

    ②：根据栈和队列的结构：

    栈为后进先出，队列为先进先出；

    所以想要出栈，即为出队队列的队尾元素；

    这里又有两个队列，所以可以想到一个思路：

    ①：首先将不为空的队列的前size-1个元素导入空队列中：

    ②：此时之前不为空的队列中还剩下一个元素，而此元素即为我们要出栈的元素：

    ③：完成一轮后，之前不为空的队列就变为空队列，之前的空队列就变为不为空队列了，之后循环操作即可：

    1. //出栈
    2. int myStackPop(MyStack* obj) {
    3. 	//根据思路分析，将不为空的队列一的前Size-1个元素导入空队列二；
    4. 	//再将不为空的队列一剩余的一个元素出队返回，即为出栈操作；
    5.  
    6. 	//首先我们不知道哪个队列为空，所以我们可以使用“假设法”找出空队列
    7. 	Que* empty = &obj->q1;
    8. 	Que* noempty = &obj->q2;
    9. 	if (!QueueEmpty(&obj->q1))
    10. 	{
    11. 		empty = &obj->q2;
    12. 		noempty = &obj->q1;
    13. 	}
    14.  
    15. 	//然后将不为空的队列的前size-1个元素导入空队列
    16. 	while (QueueSize(noempty) > 1)
    17. 	{
    18. 		//取不为空队列的队头，导入空队列
    19. 		QueuePush(empty, QueueFront(noempty));
    20. 		//不为空队列出队，导入下一个元素
    21. 		QueuePop(noempty);
    22. 	}
    23.  
    24. 	//到这里，不为空的队列只剩下一个元素，即我们需要出栈的元素；
    25.  
    26. 	//保存该元素
    27. 	int top = QueueFront(noempty);
    28. 	//出队
    29. 	QueuePop(noempty);
    30. 	//返回
    31. 	return top;
    32. }
    ⭐️6.第五个接口——int myStackTop(MyStack* obj)

    ①：看函数名意为“返回栈顶元素”；

    ②：思路：根据栈和队列的使用规则或者上述出栈操作的思路，我们应该清楚，栈的栈顶即为队列的队尾元素；

    ③：步骤：所以我们只需要找到不为空的队列然后返回其队尾元素即可；

    1.  
    2. //返回栈顶元素
    3. int myStackTop(MyStack* obj) {
    4. 	//因为栈为后进先出，队列为先进先出，所以要返回栈顶元素，即返回不为空队列的队尾元素
    5. 	if (!QueueEmpty(&obj->q1))
    6. 	{
    7. 		return QueueBack(&obj->q1);
    8. 	}
    9. 	else
    10. 	{
    11. 		return QueueBack(&obj->q2);
    12. 	}
    13. }
    ⭐️7.第六个接口——bool myStackEmpty(MyStack* obj)

    ①：看函数名意为“判断栈空”

    ②:只需要看两个队列是否同时为空，若两个队列同时为空，则栈空；

    1. //栈的判空
    2. bool myStackEmpty(MyStack* obj) {
    3. 	//两队列为空，即栈为空，所以直接用逻辑值判断
    4. 	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    5. }
    ⭐️8.第七个接口——void myStackFree(MyStack* obj)

    ①：函数名意为“栈的销毁”；

    ②：我们要注意，除了要释放动态开辟的MyStack空间，之前还要将两个队列给释放掉；

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

    🌕（四）、第一题源代码

    ⭐️1.代码：
    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7.  
    8. typedef int QDatatype;
    9. typedef struct QueueNode
    10. {
    11. 	struct QueueNode* next;
    12. 	QDatatype data;
    13. }QNode;
    14.  
    15. typedef struct Queue
    16. {
    17. 	QNode* head;//头指针，指向首结点
    18. 	QNode* tail;//尾指针，指向为结点
    19. 	int size;//记录队列长度
    20. }Que;
    21.  
    22. //初始化
    23. void Queueinit(Que* ps);
    24.  
    25. //销毁
    26. void QueueDestroy(Que* ps);
    27.  
    28. //入队
    29. void QueuePush(Que* ps, QDatatype x);
    30.  
    31. //出队
    32. void QueuePop(Que* ps);
    33.  
    34. //取队头
    35. QDatatype QueueFront(Que* ps);
    36.  
    37. //取队尾
    38. QDatatype QueueBack(Que* ps);
    39.  
    40. //判空
    41. bool QueueEmpty(Que* ps);
    42.  
    43. //获取队列元素个数
    44. int QueueSize(Que* ps);
    45.  
    46.  
    47. //初始化
    48. void Queueinit(Que* ps)
    49. {
    50. 	assert(ps);
    51. 	ps->head = ps->tail = NULL;
    52. 	ps->size = 0;
    53. }
    54.  
    55. //销毁
    56. void QueueDestroy(Que* ps)
    57. {
    58. 	assert(ps);
    59. 	QNode* cur = ps->head;
    60. 	//先保存下一个结点，在释放当前结点，在重定位
    61. 	while (cur)
    62. 	{
    63. 		QNode* Qnext = cur->next;
    64. 		free(cur);
    65. 		cur = Qnext;
    66. 	}
    67. 	ps->head = ps->tail = NULL;
    68. 	ps->size = 0;
    69. }
    70.  
    71. //入队
    72. void QueuePush(Que* ps, QDatatype x)
    73. {
    74. 	assert(ps);
    75. 	//创建一个新结点
    76. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    77. 	if (newnode == NULL)
    78. 	{
    79. 		perror("malloc");
    80. 		return;
    81. 	}
    82. 	//因为是在尾结点入队，所以入队之后结点next域要置空
    83. 	newnode->data = x;
    84. 	newnode->next = NULL;
    85. 	//第一次插入是结构体指针之间的赋值,之后才是结构体成员的赋值，所以要分情况
    86. 	//记住tail指针始终指向尾结点，所以入队之后要对tail指针重定位
    87. 	if (ps->tail == NULL)
    88. 	{
    89. 		ps->head = ps->tail = newnode;
    90. 	}
    91. 	else
    92. 	{
    93. 		ps->tail->next = newnode;
    94. 		ps->tail = newnode;
    95. 	}
    96. 	//入队后元素数量+1
    97. 	ps->size++;
    98. }
    99.  
    100. //出队
    101. void QueuePop(Que* ps)
    102. {
    103. 	assert(ps);
    104. 	//检查队列是否为空，若为空则assert函数报错提示
    105. 	assert(!QueueEmpty(ps));
    106. 	//队列不为空，进行尾删
    107. 	//当对列只剩下一个元素时,要注意head和tail指针都要指向NULL，所以为了安全起见，进行分类讨论
    108. 	if (ps->head->next == NULL)
    109. 	{
    110. 		free(ps->head);
    111. 		//注意free释放的是该指针指向的空间，而不是释掉该指针
    112. 		ps->head = ps->tail = NULL;
    113. 	}
    114. 	else
    115. 	{
    116. 		QNode* next = ps->head->next;
    117. 		free(ps->head);
    118. 		ps->head = next;
    119. 	}
    120. 	//出队列，元素数量-1
    121. 	ps->size--;
    122. }
    123.  
    124. //取队头
    125. QDatatype QueueFront(Que* ps)
    126. {
    127. 	assert(ps);
    128. 	//检查队列为不为空
    129. 	assert(!QueueEmpty(ps));
    130. 	//返回首结点的data域
    131. 	return ps->head->data;
    132. }
    133.  
    134. //取队尾
    135. QDatatype QueueBack(Que* ps)
    136. {
    137. 	assert(ps);
    138. 	//检查队列为不为空
    139. 	assert(!QueueEmpty(ps));
    140. 	//返回尾结点的data域
    141. 	return ps->tail->data;
    142. }
    143.  
    144.  
    145. //判空
    146. bool QueueEmpty(Que* ps)
    147. {
    148. 	assert(ps);
    149. 	//为空返回真，不为空返回假
    150. 	return ps->head == NULL;
    151. }
    152.  
    153. //获取队列元素个数
    154. int QueueSize(Que* ps)
    155. {
    156. 	assert(ps);
    157. 	return ps->size;
    158. }
    159.  
    160.  
    161.  
    162.  
    163.  
    164.  
    165. typedef struct {
    166. 	Que q1;
    167. 	Que q2;
    168. } MyStack;
    169.  
    170. //栈的初始化
    171. MyStack* myStackCreate() {
    172. 	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    173. 	Queueinit(&pst->q1);
    174. 	Queueinit(&pst->q2);
    175. 	return pst;
    176. }
    177.  
    178. //入栈
    179. void myStackPush(MyStack* obj, int x) {
    180. 	//根据思路分析，哪个队列不为空，就入队哪个队列
    181. 	if (!QueueEmpty(&obj->q1))
    182. 	{
    183. 		QueuePush(&obj->q1, x);
    184. 	}
    185. 	else
    186. 	{
    187. 		QueuePush(&obj->q2, x);
    188. 	}
    189. }
    190.  
    191. //出栈
    192. int myStackPop(MyStack* obj) {
    193. 	//根据思路分析，将不为空的队列一的前Size-1个元素导入空队列二；
    194. 	//再将不为空的队列一剩余的一个元素出队返回，即为出栈操作；
    195.  
    196. 	//首先我们不知道哪个队列为空，所以我们可以使用“假设法”找出空队列
    197. 	Que* empty = &obj->q1;
    198. 	Que* noempty = &obj->q2;
    199. 	if (!QueueEmpty(&obj->q1))
    200. 	{
    201. 		empty = &obj->q2;
    202. 		noempty = &obj->q1;
    203. 	}
    204.  
    205. 	//然后将不为空的队列的前size-1个元素导入空队列
    206. 	while (QueueSize(noempty) > 1)
    207. 	{
    208. 		//取不为空队列的队头，导入空队列
    209. 		QueuePush(empty, QueueFront(noempty));
    210. 		//不为空队列出队，导入下一个元素
    211. 		QueuePop(noempty);
    212. 	}
    213.  
    214. 	//到这里，不为空的队列只剩下一个元素，即我们需要出栈的元素；
    215.  
    216. 	//保存该元素
    217. 	int top = QueueFront(noempty);
    218. 	//出队
    219. 	QueuePop(noempty);
    220. 	//返回
    221. 	return top;
    222. }
    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. bool myStackEmpty(MyStack* obj) {
    239. 	//两队列为空，即栈为空，所以直接用逻辑值判断
    240. 	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    241. }
    242.  
    243. //栈的销毁
    244. void myStackFree(MyStack* obj) {
    245. 	QueueDestroy(&obj->q1);
    246. 	QueueDestroy(&obj->q2);
    247. 	free(obj);
    248. }
    249.  
    250. int main()
    251. {
    252. 	MyStack pst = {0};
    253. 	MyStack* ppst = &pst;
    254. 	ppst=myStackCreate(&pst);
    255. 	myStackPush(ppst, 1);
    256. 	myStackPush(ppst, 2);
    257. 	myStackPush(ppst, 3);
    258. 	myStackPush(ppst, 4);
    259.  
    260. 	while (!myStackEmpty(ppst))
    261. 	{
    262. 		printf("%d ", myStackTop(ppst));
    263. 		myStackPop(ppst);
    264. 	}
    265. 	printf("\n");
    266. 	myStackFree(ppst);
    267.  
    268. 	return;
    269. }
    ⭐️2.运行结果：

    🍁二、用栈实现队列

    🌕（一）、题目（力扣链接：用栈实现队列）

    🌕（二）、思路

    第一题是用队列实现栈，而这道题是用栈实现队列，所以两道题有很多相似的地方，小编就快速实现，只要把第一题搞懂了，这道题实现起来非常简单：

    ①：由第一题我们想到拿一个栈接收数据，一个栈为空，然后在导数据的方式引入思考：

    导完数据后：

    到这一步当我们再想重复操作时，就发现不同了，因为栈是后进先出，所以导完一次数据后，顺序会返过来，这时，我们只需要依次对q2进行出栈，即可实现队列的先进先出结构：

    入队的时候为6 5 4 3 2 1，而这样的操作出队的时候也为 6 5 4 3 2 1；

    所以我们会产生一个新的思路：

    将q1栈用于存储入队的数据，再将栈q1中的数据出栈，然后入栈到q2中；

    当要出队时，只需要对q2进行出栈操作即为出队操作，当q2为空时，就将栈q1中的数据导过来；

    把思路理清，图画标准，接下来实现起来就方便多了；

    🌕（三）、解答

    ⭐️1.第一个接口——typedef struct

    ①：首先我们可以将以前实现过的栈的各个操作复制粘贴进来，没有的小伙伴可以直接看小编的源代码；

    ②：跟第一题一样，没有栈，我们就定义出两个栈q1和q2；

    1. typedef struct {
    2. 	ST q1;
    3. 	ST q2;
    4.  
    5. } MyQueue;
    ⭐️2.第二个接口——MyQueue* myQueueCreate()

    ①：意为“初始化操作”,与第一题相同；

    1. //初始化
    2. MyQueue* myQueueCreate() {
    3. 	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    4. 	STinit(&obj->q1);
    5. 	STinit(&obj->q2);
    6. 	return obj;
    7. }
    ⭐️3.第三个接口——void myQueuePush(MyQueue* obj, int x)

    ①：意为“入队操作”；

    ②：因为栈q1和栈q2的功能是区分开的，所以对于入队操作，我们只需对q1进行入栈操作区即可：

    1. //入队
    2. void myQueuePush(MyQueue* obj, int x) {
    3. 	//根据思路分析，我们直接将队列数据入栈到保存栈q1（即两个栈中，负责保存数据的栈）即可
    4. 	STPush(&obj->q1, x);
    5. }
    ⭐️4.第四个接口——int myQueuePop(MyQueue* obj)

    ①：意为“出队操作”；

    ②：上面我们都分析过了，只需要按照步骤来即可：

    1. //出队
    2. int myQueuePop(MyQueue* obj) {
    3. 	//根据思路分析，我们直接出栈q2即为出队操作，直到q2为空时，再将q1中的数据导入q2
    4.  
    5. 	//先判断q2是否栈空，如果栈空，则将q1的数据导入q2，再出栈
    6. 	if (STEmpty(&obj->q2))
    7. 	{
    8. 		while (!STEmpty(&obj->q1))
    9. 		{
    10. 			//取q1栈顶元素，入栈到q2
    11. 			STPush(&obj->q2, STTop(&obj->q1));
    12. 			//q1出栈，以便下次导入数据
    13. 			STPop(&obj->q1);
    14. 		}
    15. 	}
    16. 	//因为不仅要出队，还要返回出队元素，所以先取栈顶元素保存，再出栈
    17. 	int top = STTop(&obj->q2);
    18. 	STPop(&obj->q2);
    19. 	return top;
    20. }
    ⭐️5.第五个接口——int myQueuePeek(MyQueue* obj)

    ①：意为“取队头操作”；

    ②：只需要对q2进行出栈并返回即可：

    1.  
    2. //取队头元素
    3. int myQueuePeek(MyQueue* obj) {
    4. 	//根据栈和队列的结构，队头元素即为上述出栈的元素
    5. 	//先判断q2是否栈空，如果栈空，则将q1的数据导入q2，再出栈
    6.  
    7. 	//导数据
    8. 	if (STEmpty(&obj->q2))
    9. 	{
    10. 		while (!STEmpty(&obj->q1))
    11. 		{
    12. 			//取q1栈顶元素，入栈到q2
    13. 			STPush(&obj->q2, STTop(&obj->q1));
    14. 			//q1出栈，以便下次导入数据
    15. 			STPop(&obj->q1);
    16. 		}
    17. 	}
    18. 	return STTop(&obj->q2);
    19. }
    ⭐️6.第六个接口——bool myQueueEmpty(MyQueue* obj)

    ①：意为“判断队空操作”；

    ②：操作与第一题相同：

    1. //判断队空
    2. bool myQueueEmpty(MyQueue* obj) {
    3. 	//只有当两个栈都为空时，队列才为空
    4. 	return STEmpty(&obj->q1) && STEmpty(&obj->q2);
    5. }
    ⭐️7.第七个接口——void myQueueFree(MyQueue* obj)

    ①：意为“队列的销毁”；

    ②：操作与第一题相同：

    1.  
    2. //销毁
    3. void myQueueFree(MyQueue* obj) {
    4. 	//不仅要释放队列,还要销毁两个栈
    5. 	STDestroy(&obj->q1);
    6. 	STDestroy(&obj->q2);
    7. 	free(obj);
    8. }

    🌕（四）、第二题源代码

    1.  
    2. //二、用栈实现队列
    3. typedef int DataType;
    4. typedef struct Stack
    5. {
    6. 	DataType* a;
    7. 	int top;//指向栈顶
    8. 	int catacity;//现有空间大小
    9. }ST;
    10.  
    11. //初始化
    12. void STinit(ST* ps);
    13.  
    14. //销毁
    15. void STDestroy(ST* ps);
    16.  
    17. //入栈
    18. void STPush(ST* ps, DataType x);
    19.  
    20. //出栈
    21. void STPop(ST* ps);
    22.  
    23. //获取栈的元素个数
    24. int STSize(ST* ps);
    25.  
    26. //判断是否为栈空
    27. bool STEmpty(ST* ps);
    28.  
    29. //获取栈顶元素
    30. DataType STTop(ST* ps);
    31.  
    32. //初始化
    33. void STinit(ST* ps)
    34. {
    35. 	assert(ps);
    36. 	//刚开始没有元素，所以top指向0
    37. 	ps->top = 0;
    38. 	ps->catacity = 0;
    39. 	ps->a = NULL;
    40. }
    41.  
    42. //销毁
    43. void STDestroy(ST* ps)
    44. {
    45. 	assert(ps);
    46. 	free(ps->a);
    47. 	ps->top = 0;
    48. 	ps->catacity = 0;
    49. }
    50.  
    51. //入栈
    52. void STPush(ST* ps, DataType x)
    53. {
    54. 	assert(ps);
    55. 	//空间满了进行增容
    56. 	if (ps->top == ps->catacity)
    57. 	{
    58. 		//第一次catacity值为0，所以判断一下给予赋值
    59. 		int newCatacity = (ps->catacity == 0 ? 4 : ps->catacity * 2);
    60. 		//使用realloc函数进行增容，刚开始a为NULL的话realloc函数的作用和malloc相同
    61. 		DataType* tmp = realloc(ps->a, sizeof(DataType) * newCatacity);
    62. 		//检查是否增容成功
    63. 		if (tmp == NULL)
    64. 		{
    65. 			perror("realloc");
    66. 			return;
    67. 		}
    68. 		ps->a = tmp;
    69. 		ps->catacity = newCatacity;
    70. 	}
    71. 	//插入
    72. 	ps->a[ps->top] = x;
    73. 	ps->top++;
    74. }
    75.  
    76. //出栈
    77. void STPop(ST* ps)
    78. {
    79. 	assert(ps);
    80. 	//ps->top==0时为空栈
    81. 	if (0 == ps->top)
    82. 	{
    83. 		printf("栈为空，出栈失败!\n");
    84. 		return;
    85. 	}
    86. 	//出栈
    87. 	--ps->top;
    88. }
    89.  
    90. //获取栈的元素个数
    91. int STSize(ST* ps)
    92. {
    93. 	assert(ps);
    94. 	return ps->top;
    95. }
    96.  
    97. //判断是否为栈空
    98. bool STEmpty(ST* ps)
    99. {
    100. 	assert(ps);
    101. 	return ps->top == 0;
    102. }
    103.  
    104. //获取栈顶元素
    105. DataType STTop(ST* ps)
    106. {
    107. 	assert(ps);
    108.  
    109. 	if (0 == ps->top)
    110. 	{
    111. 		printf("栈为空，获取失败!\n");
    112. 		exit(-1);
    113. 	}
    114. 	return ps->a[ps->top - 1];
    115. }
    116.  
    117. typedef struct {
    118. 	ST q1;
    119. 	ST q2;
    120.  
    121. } MyQueue;
    122.  
    123. //初始化
    124. MyQueue* myQueueCreate() {
    125. 	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    126. 	STinit(&obj->q1);
    127. 	STinit(&obj->q2);
    128. 	return obj;
    129. }
    130.  
    131. //入队
    132. void myQueuePush(MyQueue* obj, int x) {
    133. 	//根据思路分析，我们直接将队列数据入栈到保存栈q1（即两个栈中，负责保存数据的栈）即可
    134. 	STPush(&obj->q1, x);
    135. }
    136.  
    137. //出队
    138. int myQueuePop(MyQueue* obj) {
    139. 	//根据思路分析，我们直接出栈q2即为出队操作，直到q2为空时，再将q1中的数据导入q2
    140.  
    141. 	//先判断q2是否栈空，如果栈空，则将q1的数据导入q2，再出栈
    142. 	if (STEmpty(&obj->q2))
    143. 	{
    144. 		while (!STEmpty(&obj->q1))
    145. 		{
    146. 			//取q1栈顶元素，入栈到q2
    147. 			STPush(&obj->q2, STTop(&obj->q1));
    148. 			//q1出栈，以便下次导入数据
    149. 			STPop(&obj->q1);
    150. 		}
    151. 	}
    152. 	//因为不仅要出队，还要返回出队元素，所以先取栈顶元素保存，再出栈
    153. 	int top = STTop(&obj->q2);
    154. 	STPop(&obj->q2);
    155. 	return top;
    156. }
    157.  
    158. //取队头元素
    159. int myQueuePeek(MyQueue* obj) {
    160. 	//根据栈和队列的结构，队头元素即为上述出栈的元素
    161. 	//先判断q2是否栈空，如果栈空，则将q1的数据导入q2，再出栈
    162.  
    163. 	//导数据
    164. 	if (STEmpty(&obj->q2))
    165. 	{
    166. 		while (!STEmpty(&obj->q1))
    167. 		{
    168. 			//取q1栈顶元素，入栈到q2
    169. 			STPush(&obj->q2, STTop(&obj->q1));
    170. 			//q1出栈，以便下次导入数据
    171. 			STPop(&obj->q1);
    172. 		}
    173. 	}
    174. 	return STTop(&obj->q2);
    175. }
    176.  
    177. //判断队空
    178. bool myQueueEmpty(MyQueue* obj) {
    179. 	//只有当两个栈都为空时，队列才为空
    180. 	return STEmpty(&obj->q1) && STEmpty(&obj->q2);
    181. }
    182.  
    183. //销毁
    184. void myQueueFree(MyQueue* obj) {
    185. 	//不仅要释放队列,还要销毁两个栈
    186. 	STDestroy(&obj->q1);
    187. 	STDestroy(&obj->q2);
    188. 	free(obj);
    189. }
    190.  
    191. int main()
    192. {
    193. 	MyQueue st = { 0 };
    194. 	MyQueue* pst = &st;
    195. 	pst = myQueueCreate(&st);
    196. 	myQueuePush(pst, 1);
    197. 	myQueuePush(pst, 2);
    198. 	myQueuePush(pst, 3);
    199. 	myQueuePush(pst, 4);
    200.  
    201. 	while (!myQueueEmpty(pst))
    202. 	{
    203. 		printf("%d ", myQueuePeek(pst));
    204. 		myQueuePop(pst);
    205.  
    206. 	}
    207. 	printf("\n");
    208. 	myQueueFree(pst);
    209. 	return 0;
    210. }

  • 相关阅读:
    自动化测试年薪50万你敢想吗？阿里P7都不淡定了...
    python数据类型及用法
    vue3的7种路由守卫使用大全
    9--OpenCV:图像基本操作之①阈值②形态学操作(腐蚀\膨胀,开、闭)
    C# 之 FileInfo API参考
    一体化运维管理平台：为企业提供全面监控和运维服务
    全面掌握胶囊网络：从基础理论到PyTorch实战
    【C++修炼之路】6. 内存管理
    halcon脚本-边缘及骨架的识别【附源码】
    【在线教育】课程封面上传图片到阿里云OSS
  • 原文地址：https://blog.csdn.net/hffh123/article/details/134048373