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

    目录

    一、队列的概念及结构

    二、队列的实现

     拓展：循环队列

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

    一、队列的概念及结构

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

    二、队列的实现

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

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

    1. #pragma once
    2.  
    3. //Queue.h
    4. // 链式结构：表示队列
    5.  
    6. #include 
    7. #include 
    8. #include 
    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. }

  • 相关阅读:
    Java继承中方法的覆盖重写~注意事项
    Java真的不难（四十五）SpringMVC的入门
    【安全】容器中二进制漏洞检测方案
    每章一篇博客带你拿下吉林大学JAVAEE期末（三：JSP）
    vulnhub之DC9
    selenium 对当前已经打开的窗口进行调试
    GlusterFS SnapShot 调研
    Java 第三阶段增强分析需求，代码实现能力【JDBC】
    剑指 Offer 06. 从尾到头打印链表
    Day 251/300 《图解HTTP》读书笔记（三）
  • 原文地址：https://blog.csdn.net/m0_74265792/article/details/132767070