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

数据结构之队列的实现（附源码）_队列的实现代码

作者：繁依Fanyi0 | 2024-05-15 05:24:20

赞

踩

队列的实现代码

目录

一、队列的概念及结构

二、队列的实现

 拓展：循环队列

三、初学的队列以及栈和队列结合的练习题

一、队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

二、队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

 具体代码如下（C语言实现）：

  1. #pragma once
  2.  
  3. //Queue.h
  4. // 链式结构：表示队列
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <assert.h>
  9.  
  10. typedef int QDateType;
  11.  
  12. typedef struct QListNode
  13. {
  14. 	struct QListNode* _next;
  15. 	QDateType _data;
  16. }QNode;
  17.  
  18. // 队列的结构 
  19. typedef struct Queue
  20. {
  21. 	QNode* _front;//队头
  22. 	QNode* _rear;//队尾
  23. 	int size;
  24. }Queue;
  25.  
  26. // 初始化队列 
  27. void QueueInit(Queue* q);
  28. // 队尾入队列 
  29. void QueuePush(Queue* q, QDateType data);
  30. // 队头出队列 
  31. void QueuePop(Queue* q);
  32. // 获取队列头部元素 
  33. QDateType QueueFront(Queue* q);
  34. // 获取队列队尾元素 
  35. QDateType QueueBack(Queue* q);
  36. // 获取队列中有效元素个数 
  37. int QueueSize(Queue* q);
  38. // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
  39. int QueueEmpty(Queue* q);
  40. // 销毁队列 
  41. void QueueDestroy(Queue* q);
  1. //Queue.c
  2. #include "Queue.h"
  3.  
  4. void QueueInit(Queue* q)
  5. {
  6. 	assert(q);
  7. 	q->_front = NULL;
  8. 	q->_rear = NULL;
  9. 	q->size = 0;
  10. }
  11.  
  12. void QueuePush(Queue* q, QDateType data)
  13. {
  14. 	assert(q);
  15. 	QNode* tmp = (QNode*)malloc(sizeof(QNode));
  16. 	if (tmp == NULL)
  17. 	{
  18. 		perror("tmp malloc");
  19. 		exit(-1);
  20. 	}
  21. 	tmp->_data = data;
  22. 	tmp->_next = NULL;
  23.  
  24. 	if (q->_rear == NULL)
  25. 	{
  26. 		q->_front = q->_rear = tmp;
  27. 	}
  28. 	else
  29. 	{
  30. 		q->_rear->_next = tmp;
  31. 		q->_rear = tmp;
  32. 	}
  33. 	q->size++;
  34. }
  35.  
  36. void QueuePop(Queue* q)
  37. {
  38. 	assert(q);
  39. 	assert(QueueEmpty(q));
  40. 	if (q->_front->_next == NULL)
  41. 	{
  42. 		free(q->_front);
  43. 		q->_front = q->_rear = NULL;
  44. 	}
  45. 	else
  46. 	{
  47. 		QNode* next = q->_front->_next;
  48. 		free(q->_front);
  49. 		q->_front = next;
  50. 	}
  51. 	q->size--;
  52. }
  53.  
  54. QDateType QueueFront(Queue* q)
  55. {
  56. 	assert(q);
  57. 	assert(QueueEmpty(q));
  58. 	return q->_front->_data;
  59. }
  60.  
  61. QDateType QueueBack(Queue* q)
  62. {
  63. 	assert(q);
  64. 	assert(QueueEmpty(q));
  65. 	return q->_rear->_data;
  66. }
  67.  
  68. int QueueSize(Queue* q)
  69. {
  70. 	assert(q);
  71. 	return q->size;
  72. }
  73.  
  74. int QueueEmpty(Queue* q)
  75. {
  76. 	assert(q);
  77. 	return q->size;
  78. }
  79.  
  80. void QueueDestroy(Queue* q)
  81. {
  82. 	assert(q);
  83. 	QNode* cur = q->_front;
  84. 	while (cur)
  85. 	{
  86. 		Queue* next = cur->_next;
  87. 		free(cur);
  88. 		cur = next;
  89. 	}
  90. 	q->_front = q->_rear = NULL;
  91. 	q->size = 0;
  92. }
  1. //test.c
  2. #include "Queue.h"
  3.  
  4.  
  5. void test02()
  6. {
  7. 	Queue q1;
  8. 	QueueInit(&q1);
  9.  
  10. 	QueuePush(&q1, 1);
  11. 	QueuePush(&q1, 2);
  12. 	QueuePush(&q1, 3);
  13. 	QueuePush(&q1, 4);
  14. 	QueuePush(&q1, 5);
  15.  
  16. 	QueuePop(&q1);
  17.  
  18. 	while (QueueEmpty(&q1))
  19. 	{
  20. 		printf("%d ", QueueFront(&q1));
  21. 		QueuePop(&q1);
  22. 	}
  23. 	printf("\n");
  24. 	QueueDestroy(&q1);
  25. }
  26.  
  27. int main()
  28. {
  29. 	test02();
  30.  
  31. 	return 0;
  32. }

 拓展：循环队列

如上图所示：循环队列的节点数一般会比要求的节点数多一个，以便区分空的循环队列和满的循环队列。空的循环队列front和rear指向同一个节点，满的循环队列可以理解为rear = front + 1。

三、初学的队列以及栈和队列结合的练习题

题目一：设计循环队列

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。
  1. typedef struct 
  2. {
  3.     int* a;
  4.     int front;
  5.     int rear;
  6.     int k;
  7. } MyCircularQueue;
  8.  
  9.  
  10. MyCircularQueue* myCircularQueueCreate(int k) 
  11. {
  12.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  13.     obj->a = (int*)malloc(sizeof(int)*(k+1));
  14.     obj->front = obj->rear = 0;
  15.     obj->k = k;
  16.  
  17.     return obj;
  18. }
  19.  
  20. bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
  21. {
  22.     //front和rear相等即为空
  23.     return obj->front == obj->rear;    
  24. }
  25.  
  26. bool myCircularQueueIsFull(MyCircularQueue* obj) 
  27. {
  28.     //数学方法判满
  29.     return (obj->rear + 1) % (obj->k + 1) == obj->front;
  30. }
  31.  
  32. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
  33. {
  34.     if(myCircularQueueIsFull(obj))
  35.     return false;
  36.     obj->a[obj->rear] = value;
  37.     ++obj->rear;
  38.     //不然rear可能越界
  39.     obj->rear %= (obj->k+1);
  40.  
  41.     return true;
  42. }
  43.  
  44. bool myCircularQueueDeQueue(MyCircularQueue* obj) 
  45. {
  46.     if(myCircularQueueIsEmpty(obj))
  47.     return false;
  48.     obj->front++;
  49.     obj->front %= (obj->k+1);
  50.     return true; 
  51. }
  52.  
  53. int myCircularQueueFront(MyCircularQueue* obj) 
  54. {
  55.     if(myCircularQueueIsEmpty(obj))
  56.     return -1;
  57.     else
  58.     return obj->a[obj->front];
  59. }
  60.  
  61. int myCircularQueueRear(MyCircularQueue* obj) 
  62. {
  63.     if(myCircularQueueIsEmpty(obj))
  64.     return -1;
  65.     else
  66.     //数学方法
  67.     return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
  68. }
  69.  
  70. void myCircularQueueFree(MyCircularQueue* obj) 
  71. {
  72.     free(obj->a);
  73.     free(obj);
  74. }

题目二：用队列实现栈

思路：用两个队列，保持一个队列为空一个不为空，当要出栈的时候就将不为空的队列中除了队尾的元素全都入到为空的队列中，然后将唯一的那个元素出栈。

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

题目三：用栈实现队列

思路：使用两个栈，一个push栈一个pop栈，先往push栈中堆入元素，出队时，先将push栈中的元素先pop到pop栈中，再从pop栈中pop元素，其间再有元素堆入入到push栈中。

  1. typedef int STDataType;
  2. typedef struct Stack
  3. {
  4. 	STDataType* _a;
  5. 	int _top;		// 栈顶
  6. 	int _capacity;  // 容量 
  7. }Stack;
  8.  
  9. void StackInit(Stack* ps)
  10. {
  11. 	assert(ps);
  12. 	ps->_a = NULL;
  13. 	ps->_top = 0;
  14. 	ps->_capacity = 0;
  15. }
  16.  
  17. void StackPush(Stack* ps, STDataType data)
  18. {
  19. 	assert(ps);
  20. 	if (ps->_capacity == ps->_top)
  21. 	{
  22. 		int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
  23. 		STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * newCapacity);
  24.  
  25. 		if (tmp == NULL)
  26. 		{
  27. 			perror("realloc fail");
  28. 			exit(-1);
  29. 		}
  30. 		ps->_a = tmp;
  31. 		ps->_capacity = newCapacity;
  32. 	}
  33.  
  34. 	ps->_a[ps->_top] = data;
  35. 	ps->_top++;
  36. }
  37.  
  38. void StackPop(Stack* ps)
  39. {
  40. 	assert(ps);
  41. 	assert(ps->_top > 0);
  42. 	ps->_top--;
  43. }
  44.  
  45. STDataType StackTop(Stack* ps)
  46. {
  47. 	assert(ps);
  48. 	assert(ps->_top > 0);
  49. 	return ps->_a[ps->_top - 1];
  50. }
  51.  
  52. int StackSize(Stack* ps)
  53. {
  54. 	assert(ps);
  55. 	return ps->_top;
  56. }
  57.  
  58. int StackEmpty(Stack* ps)
  59. {
  60. 	return ps->_top;
  61. }
  62.  
  63. void StackDestroy(Stack* ps)
  64. {
  65. 	assert(ps);
  66. 	free(ps->_a);
  67. 	ps->_a = NULL;
  68. 	ps->_capacity = 0;
  69. 	ps->_top = 0;
  70. }
  71.  
  72.  
  73. typedef struct 
  74. {
  75.     Stack pushst;
  76.     Stack popst;
  77. } MyQueue;
  78.  
  79.  
  80. MyQueue* myQueueCreate() 
  81. {
  82.     MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
  83.     StackInit(&obj->pushst);
  84.     StackInit(&obj->popst);
  85.     return obj;
  86. }
  87.  
  88. void myQueuePush(MyQueue* obj, int x) 
  89. {
  90.     StackPush(&obj->pushst, x);
  91. }
  92.  
  93. int myQueuePeek(MyQueue* obj) 
  94. {
  95.     //pop栈为空就往其中堆入元素
  96.     if(StackEmpty(&obj->popst) == 0)
  97.     {
  98.         while(StackEmpty(&obj->pushst) > 0)
  99.         {
  100.             StackPush(&obj->popst, StackTop(&obj->pushst));
  101.             StackPop(&obj->pushst);
  102.         }
  103.     }
  104.     return StackTop(&obj->popst);
  105. }
  106.  
  107. int myQueuePop(MyQueue* obj) 
  108. {
  109.     int front = myQueuePeek(obj);
  110.     StackPop(&obj->popst);
  111.     return front;
  112. }
  113.  
  114.  
  115. bool myQueueEmpty(MyQueue* obj) 
  116. {
  117.     int ret1, ret2;
  118.     if(StackEmpty(&obj->pushst) == 0)
  119.     ret1 = 0;
  120.     else
  121.     ret1 = 1;
  122.     if(StackEmpty(&obj->popst) == 0)
  123.     ret2 = 0;
  124.     else
  125.     ret2 = 1;
  126.     if(ret1 == 0 && ret2 == 0)
  127.     return true;
  128.     else
  129.     return false; 
  130. }
  131.  
  132. void myQueueFree(MyQueue* obj) 
  133. {
  134.     StackDestroy(&obj->pushst);
  135.     StackDestroy(&obj->popst);
  136.     free(obj);
  137. }

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

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

  

闽ICP备14008679号