devbox
在线问答5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

栈和队列及其应用_int isemptyqueue(queue

作者：在线问答5 | 2024-07-23 08:30:50

赞

踩

int isemptyqueue(queue

栈和队列基本接口的实现

栈

Stack.h

  1. #pragma once
  2.  
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<assert.h>
  6.  
  7. typedef int _STdatatype;
  8.  
  9. typedef struct Stack
  10. {
  11. 	_STdatatype * _a;
  12. 	int _top;
  13. 	int _capacity;
  14. }Stack;
  15.  
  16. void InitStack(Stack * ps);
  17. void DestoryStack(Stack * ps);
  18.  
  19. void PushStack(Stack * ps, _STdatatype x);
  20. void PopStack(Stack * ps);
  21.  
  22. _STdatatype TopStack(Stack * ps);
  23.  
  24. int isEmptyStack(Stack * ps);
  25. int SizeStack(Stack * ps);

Stack.c

  1. #include"Stack.h"
  2.  
  3. void InitStack(Stack * ps)
  4. {
  5. 	assert(ps);
  6. 	ps->_a = (_STdatatype *)malloc(sizeof(_STdatatype) * 4);
  7. 	assert(ps->_a);
  8. 	ps->_top = 0;
  9. 	ps->_capacity = 4;
  10. }
  11.  
  12. void DestoryStack(Stack * ps)
  13. {
  14. 	assert(ps);
  15. 	if (ps->_a)
  16. 	{
  17. 		free(ps->_a);
  18. 		ps->_a = NULL;
  19. 		ps->_top = 0;
  20. 		ps->_capacity = 0;
  21. 	}
  22. }
  23.  
  24. void PushStack(Stack * ps, _STdatatype x)
  25. {
  26. 	assert(ps);
  27. 	if (ps->_top == ps->_capacity)
  28. 	{
  29. 		ps->_a = (_STdatatype *)realloc(ps->_a, sizeof(_STdatatype) * 2 * ps->_capacity);
  30. 		ps->_capacity *= 2;
  31. 	}
  32. 	ps->_a[ps->_top] = x;
  33. 	ps->_top++;
  34. }
  35.  
  36. void PopStack(Stack * ps)
  37. {
  38. 	assert(ps && ps->_top > 0);
  39. 	ps->_top--;
  40. }
  41.  
  42. _STdatatype TopStack(Stack * ps)
  43. {
  44. 	assert(ps && ps->_top > 0);
  45. 	return ps->_a[ps->_top - 1];
  46. }
  47.  
  48. int isEmptyStack(Stack * ps)
  49. {
  50. 	assert(ps);
  51. 	return ps->_top == 0 ? 0 : 1;
  52. }
  53.  
  54. int SizeStack(Stack * ps)
  55. {
  56. 	assert(ps);
  57. 	return ps->_top;
  58. }

队列

Queue.h

  1. #pragma once
  2.  
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<assert.h>
  6.  
  7. typedef int _QTdatatype;
  8.  
  9. typedef struct QueueNode
  10. {
  11. 	_QTdatatype _data;
  12. 	struct QueueNode * next;
  13. }QueueNode;
  14.  
  15. typedef struct Queue
  16. {
  17. 	QueueNode * _front;
  18. 	QueueNode * _back;
  19. }Queue;
  20.  
  21. QueueNode * BuyQueueNode(_QTdatatype x);
  22.  
  23. void InitQueue(Queue * pq);
  24. void DestoryQueue(Queue * pq);
  25.  
  26. void PushQueue(Queue * pq, _QTdatatype x);
  27. void PopQueue(Queue * pq);
  28.  
  29. _QTdatatype FrontQueue(Queue * pq);
  30. _QTdatatype BackQueue(Queue * pq);
  31.  
  32. int isEmptyQueue(Queue * pq);
  33. int SizeQueue(Queue * pq);

Queue.c

  1. #include"Queue.h"
  2.  
  3. QueueNode * BuyQueueNode(_QTdatatype x)
  4. {
  5. 	QueueNode * node = (QueueNode *)malloc(sizeof(QueueNode));
  6. 	assert(node);
  7. 	node->next = NULL;
  8. 	node->_data = x;
  9. 	return node;
  10. }
  11.  
  12. void InitQueue(Queue * pq)
  13. {
  14. 	assert(pq);
  15. 	pq->_front = NULL;
  16. 	pq->_back = NULL;
  17. }
  18.  
  19. void DestoryQueue(Queue * pq)
  20. {
  21. 	QueueNode * cur;
  22. 	assert(pq);
  23. 	cur = pq->_front;
  24. 	while (cur)
  25. 	{
  26. 		free(cur);
  27. 		cur = cur->next;
  28. 	}
  29. 	free(cur);
  30. 	pq->_front = pq->_back = NULL;
  31. }
  32.  
  33. void PushQueue(Queue * pq, _QTdatatype x)
  34. {
  35. 	QueueNode * node = BuyQueueNode(x);
  36. 	assert(pq);
  37. 	if (pq->_front == NULL)
  38. 	{
  39. 		pq->_front = node;
  40. 		pq->_back = node;
  41. 	}
  42. 	else
  43. 	{
  44. 		pq->_back->next = node;
  45. 		pq->_back = node;
  46. 	}
  47. }
  48.  
  49. void PopQueue(Queue * pq)
  50. {
  51. 	QueueNode * next;
  52. 	assert(pq);
  53. 	next = pq->_front->next;
  54. 	free(pq->_front);
  55. 	pq->_front = next;
  56. 	if (next == NULL)
  57. 	{
  58. 		pq->_back = NULL;
  59. 	}
  60. }
  61.  
  62. _QTdatatype FrontQueue(Queue * pq)
  63. {
  64. 	assert(pq);
  65. 	return pq->_front->_data;
  66. }
  67.  
  68. _QTdatatype BackQueue(Queue * pq)
  69. {
  70. 	assert(pq);
  71. 	return pq->_back->_data;
  72. }
  73.  
  74. int isEmptyQueue(Queue * pq)
  75. {
  76. 	assert(pq);
  77. 	return pq->_front == NULL ? 0 : 1;
  78. }
  79.  
  80. int SizeQueue(Queue * pq)
  81. {
  82. 	int size = 0;
  83. 	QueueNode * cur;
  84. 	assert(pq);
  85. 	cur = pq->_front;
  86. 	while (cur)
  87. 	{
  88. 		size++;
  89. 		cur = cur->next;
  90. 	}
  91. 	return size;
  92. }

用两个栈实现一个队列

QueueByTwoStack.h

  1. #pragma once
  2.  
  3. #include"Stack.h"
  4.  
  5. typedef struct QueueByTwoStack
  6. {
  7. 	Stack s1;
  8. 	Stack s2;
  9. }QueueByTwoStack;
  10.  
  11.  
  12. void QueueByTwoStackInit(QueueByTwoStack * qts);
  13. void QueueByTwoStackDestory(QueueByTwoStack * qts);
  14.  
  15. void QueueByTwoStackPush(QueueByTwoStack * qts, _STdatatype x);
  16. void QueueByTwoStackPop(QueueByTwoStack * qts);
  17. _STdatatype QueueByTwoStackFront(QueueByTwoStack * qts);
  18.  
  19. int QueueByTwoStackEmpty(QueueByTwoStack * qts);
  20. int QueueByTwoStackSize(QueueByTwoStack * qts);

QueueByTwoStack.c

  1. #include"QueueByTwoStack.h"
  2.  
  3. void QueueByTwoStackInit(QueueByTwoStack * qts)
  4. {
  5. 	assert(qts);
  6. 	InitStack(&qts->s1);
  7. 	InitStack(&qts->s2);
  8. }
  9.  
  10. void QueueByTwoStackDestory(QueueByTwoStack * qts)
  11. {
  12. 	assert(qts);
  13. 	DestoryStack(&qts->s1);
  14. 	DestoryStack(&qts->s2);
  15. }
  16.  
  17. void QueueByTwoStackPush(QueueByTwoStack * qts, _STdatatype x)
  18. {
  19. 	assert(qts);
  20. 	PushStack(&qts->s1, x);
  21. }
  22.  
  23. void QueueByTwoStackPop(QueueByTwoStack * qts)
  24. {
  25. 	assert(qts);
  26. 	if (isEmptyStack(&qts->s2) == 0)
  27. 	{
  28. 		while (isEmptyStack(&qts->s1))
  29. 		{
  30. 			PushStack(&qts->s2, TopStack(&qts->s1));
  31. 			PopStack(&qts->s1);
  32. 		}
  33. 	}
  34. 	PopStack(&qts->s2);
  35. }
  36.  
  37. _STdatatype QueueByTwoStackFront(QueueByTwoStack * qts)
  38. {
  39. 	assert(qts);
  40. 	if (isEmptyStack(&qts->s2) == 0)
  41. 	{
  42. 		while (isEmptyStack(&qts->s1))
  43. 		{
  44. 			PushStack(&qts->s2, TopStack(&qts->s1));
  45. 			PopStack(&qts->s1);
  46. 		}
  47. 	}
  48. 	return TopStack(&qts->s2);
  49. }
  50.  
  51. int QueueByTwoStackEmpty(QueueByTwoStack * qts)
  52. {
  53. 	assert(qts);
  54. 	return isEmptyStack(&qts->s1) | isEmptyStack(&qts->s2);
  55. }
  56.  
  57. int QueueByTwoStackSize(QueueByTwoStack * qts)
  58. {
  59. 	assert(qts);
  60. 	return SizeStack(&qts->s1) + SizeStack(&qts->s2);
  61. }

用两个队列实现一个栈

StackByTwoQueue.h

  1. #pragma once
  2.  
  3. #include"Queue.h"
  4.  
  5. typedef struct StackByTwoQueue
  6. {
  7. 	Queue q1;
  8. 	Queue q2;
  9. }StackByTwoQueue;
  10.  
  11. void StackByTwoQueueInit(StackByTwoQueue * stq);
  12. void StackByTwoQueueDestory(StackByTwoQueue * stq);
  13.  
  14. void StackByTwoQueuePush(StackByTwoQueue * stq, _QTdatatype x);
  15. void StackByTwoQueuePop(StackByTwoQueue * stq);
  16. _QTdatatype StackByTwoQueueTop(StackByTwoQueue * stq);
  17.  
  18. int StackByTwoQueueEmpty(StackByTwoQueue * stq);
  19. int StackByTwoQueueSize(StackByTwoQueue * stq);

StackByTwoQueue.c

  1. #include"StackByTwoQueue.h"
  2.  
  3. void StackByTwoQueueInit(StackByTwoQueue * stq)
  4. {
  5. 	assert(stq);
  6. 	InitQueue(&stq->q1);
  7. 	InitQueue(&stq->q2);
  8. }
  9.  
  10. void StackByTwoQueueDestory(StackByTwoQueue * stq)
  11. {
  12. 	assert(stq);
  13. 	DestoryQueue(&stq->q1);
  14. 	DestoryQueue(&stq->q2);
  15. }
  16.  
  17. void StackByTwoQueuePush(StackByTwoQueue * stq, _QTdatatype x)
  18. {
  19. 	assert(stq);
  20. 	if (isEmptyQueue(&stq->q1) != 0)
  21. 	{
  22. 		PushQueue(&stq->q1, x);
  23. 	}
  24. 	else
  25. 	{
  26. 		PushQueue(&stq->q2, x);
  27. 	}
  28. }
  29.  
  30. void StackByTwoQueuePop(StackByTwoQueue * stq)
  31. {
  32. 	Queue * empty = &stq->q1, *noempty = &stq->q2;
  33. 	assert(stq);
  34. 	if (isEmptyQueue(&stq->q1) != 0)
  35. 	{
  36. 		empty = &stq->q2;
  37. 		noempty = &stq->q1;
  38. 	}
  39. 	while (SizeQueue(noempty) > 1)
  40. 	{
  41. 		PushQueue(empty, FrontQueue(noempty));
  42. 		PopQueue(noempty);
  43. 	}
  44. 	PopQueue(noempty);
  45. }
  46.  
  47. _QTdatatype StackByTwoQueueTop(StackByTwoQueue * stq)
  48. {
  49. 	assert(stq);
  50. 	if (isEmptyQueue(&stq->q1))
  51. 	{
  52. 		return BackQueue(&stq->q1);
  53. 	}
  54. 	else
  55. 	{
  56. 		return BackQueue(&stq->q2);
  57. 	}
  58. }
  59.  
  60. int StackByTwoQueueEmpty(StackByTwoQueue * stq)
  61. {
  62. 	assert(stq);
  63. 	return isEmptyQueue(&stq->q1) | isEmptyQueue(&stq->q2);
  64. }
  65.  
  66. int StackByTwoQueueSize(StackByTwoQueue * stq)
  67. {
  68. 	assert(stq);
  69. 	return SizeQueue(&stq->q1) + SizeQueue(&stq->q2);
  70. }

测试代码

test.c

  1. #include"Stack.h"
  2. #include"Queue.h"
  3. #include"QueueByTwoStack.h"
  4. #include"StackByTwoQueue.h"
  5.  
  6. void testStack()
  7. {
  8. 	Stack s;
  9. 	InitStack(&s);
  10. 	PushStack(&s, 1);
  11. 	PushStack(&s, 2);
  12. 	PushStack(&s, 3);
  13. 	PushStack(&s, 4);
  14. 	PushStack(&s, 5);
  15. 	PushStack(&s, 6);
  16. 	printf("%d %d\n", isEmptyStack(&s), SizeStack(&s));
  17. 	while (isEmptyStack(&s))
  18. 	{
  19. 		printf("%d ",TopStack(&s));
  20. 		PopStack(&s);
  21. 	}
  22. 	printf("\n");
  23. 	printf("%d %d\n", isEmptyStack(&s), SizeStack(&s));
  24. 	DestoryStack(&s);
  25. }
  26.  
  27. void testQueue()
  28. {
  29. 	Queue q;
  30. 	InitQueue(&q);
  31. 	PushQueue(&q, 1);
  32. 	PushQueue(&q, 2);
  33. 	PushQueue(&q, 3);
  34. 	PushQueue(&q, 4);
  35. 	PushQueue(&q, 5);
  36. 	PushQueue(&q, 6);
  37. 	printf("%d %d\n", isEmptyQueue(&q), SizeQueue(&q));
  38. 	while (isEmptyQueue(&q))
  39. 	{
  40. 		printf("%d ", FrontQueue(&q));
  41. 		PopQueue(&q);
  42. 	}
  43. 	printf("\n");
  44. 	printf("%d %d\n", isEmptyQueue(&q), SizeQueue(&q));
  45. 	DestoryQueue(&q);
  46. }
  47.  
  48. void testStackByTwoQueue()
  49. {
  50. 	QueueByTwoStack qts;
  51. 	QueueByTwoStackInit(&qts);
  52. 	QueueByTwoStackPush(&qts, 1);
  53. 	QueueByTwoStackPush(&qts, 2);
  54. 	QueueByTwoStackPush(&qts, 3);
  55. 	QueueByTwoStackPush(&qts, 4);
  56. 	printf("%d %d\n", QueueByTwoStackEmpty(&qts), QueueByTwoStackSize(&qts));
  57. 	while (QueueByTwoStackEmpty(&qts))
  58. 	{
  59. 		printf("%d ",QueueByTwoStackFront(&qts));
  60. 		QueueByTwoStackPop(&qts);
  61. 	}
  62. 	printf("\n");
  63. 	QueueByTwoStackPush(&qts, 5);
  64. 	QueueByTwoStackPush(&qts, 6);
  65. 	printf("%d %d\n", QueueByTwoStackEmpty(&qts), QueueByTwoStackSize(&qts));
  66. 	while (QueueByTwoStackEmpty(&qts))
  67. 	{
  68. 		printf("%d ", QueueByTwoStackFront(&qts));
  69. 		QueueByTwoStackPop(&qts);
  70. 	}
  71. 	printf("\n");
  72. 	printf("%d %d\n", QueueByTwoStackEmpty(&qts), QueueByTwoStackSize(&qts));
  73. 	QueueByTwoStackDestory(&qts);
  74. }
  75.  
  76. void testQueueByTwoStack()
  77. {
  78. 	StackByTwoQueue stq;
  79. 	StackByTwoQueueInit(&stq);
  80. 	StackByTwoQueuePush(&stq, 1);
  81. 	StackByTwoQueuePush(&stq, 2);
  82. 	StackByTwoQueuePush(&stq, 3);
  83. 	StackByTwoQueuePush(&stq, 4);
  84. 	printf("%d %d\n",StackByTwoQueueEmpty(&stq),StackByTwoQueueSize(&stq));
  85. 	while (StackByTwoQueueEmpty(&stq))
  86. 	{
  87. 		printf("%d ", StackByTwoQueueTop(&stq));
  88. 		StackByTwoQueuePop(&stq);
  89. 	}
  90. 	printf("\n");
  91. 	StackByTwoQueuePush(&stq, 5);
  92. 	StackByTwoQueuePush(&stq, 6);
  93. 	printf("%d %d\n", StackByTwoQueueEmpty(&stq), StackByTwoQueueSize(&stq));
  94. 	while (StackByTwoQueueEmpty(&stq))
  95. 	{
  96. 		printf("%d ", StackByTwoQueueTop(&stq));
  97. 		StackByTwoQueuePop(&stq);
  98. 	}
  99. 	printf("\n");
  100. 	printf("%d %d\n", StackByTwoQueueEmpty(&stq), StackByTwoQueueSize(&stq));
  101. 	StackByTwoQueueDestory(&stq);
  102. }
  103.  
  104. int main()
  105. {
  106. 	testStack();
  107. 	testQueue();
  108. 	testStackByTwoQueue();
  109. 	testQueueByTwoStack();
  110. 	return 0;
  111. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/869043
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号