• 数据结构之队列

    目录

    队列的定义与结构

      队列的实现

    队列的结构

    初始化空队列

    销毁队列

    队尾入队列

    队头出队列

    获取队列头部元素

    获取队列尾部元素

    判断队列是否为空

    获取队列长度

    栈与队列经典试题

    队列实现栈

    栈实现队列

    队列的定义与结构

    队列是一种先进先出（First In First Out）的顺序表，队列只允许在表的一端进行插入，而在另一端删除元素；队列中允许插入的一端叫做队尾，允许删除的一端称为队头；假设队列为q=(a1,a2,a3,......,an)，那么a1就是对头元素，an就是队尾元素；

    入队列的顺序为a1,a2,a3,.....an，出队列的顺序为a1,a2,a3,......an退出；

      队列的实现

    思考：选择数组还是链表去实现队列?

    若选择数组实现队列，当元素出队列时，头部与尾部都要移动元素，时间复杂度为O(N)；

    若选择链表实现队列，通过定义队头指针和队尾指针，入队列与出队列的时间复杂度为O(1);

    采用单链表的思考：

    队列在尾部添加元素，在头部删除元素（尾进头出)；采用链表头作为队列的头部，因为链表头部容易执行删除操作(出队)；链表尾作为队列的尾部，执行插入操作（入队)；但是执行插入操作时，首先得遍历整个链表，找到最后一个链表结点（尾结点)，才能执行插入操作（入队列），为了减少遍历，需要维护一个尾指针，指向链表尾部；使用单列表实现一个队列，链表需要维护俩个指针，头指针和尾指针；头指针指向链表头部，用于出队列；尾指针指向链表尾部，用于入队列；

    • 空队列示意图

    •  空队列插入第一个元素示意图

    • 入队（单链表尾插）

    • 出队 （单链表头删）

    队列的结构

    1. typedef int QDataType;
    2. typedef struct QueueNode
    3. {
    4. 	QDataType data;//数据域
    5. 	struct QueueNode* next;//指针域-指向下一个队列结点
    6. }QueueNode;
    7.  
    8. //当进行出队列操作(头删),需要修改队头指针，但是对于形参的修改不影响实参，只能传递二级指针；
    9. //采取如下方案:将对头指针,队尾指针封装成结构体,只需要修改结构体指针即可修改结构体变量;
    10. typedef struct Queue
    11. {
    12. 	QueueNode* head;//队头指针
    13. 	QueueNode* tail;//队尾指针
    14. 	int size;//获取队列的长度
    15. }Queue;

    初始化空队列

    当队头指针head与队尾指针均为空指针，且队列的长度为0，此时链队列为空；

    1. void InitQueue(Queue* ps)
    2. {
    3. 	assert(ps != NULL);
    4.  
    5. 	ps->tail = ps->head = NULL;
    6. 	ps->size = 0;
    7. }

    销毁队列

    1. void DestroyQueue(Queue* ps)
    2. {
    3. 	assert(ps != NULL);
    4. 	QueueNode* cur = ps->head;
    5. 	while (cur != NULL)
    6. 	{
    7. 		QueueNode* next = cur->next;
    8. 		free(cur);
    9. 		cur= next;
    10. 	}
    11. 	ps->head = NULL;
    12. 	ps->tail = NULL;
    13. 	ps->size = 0;
    14. }

    队尾入队列

    1. //队尾入队列(尾插)
    2. void QueuePush(Queue* ps, QDataType x)
    3. {
    4. 	assert(ps != NULL);
    5. 	//创建新队列结点
    6. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    7. 	if (newnode == NULL)
    8. 	{
    9. 		perror("malloc failed:");
    10. 		exit(-1);
    11. 	}
    12. 	newnode->data = x;
    13. 	newnode->next = NULL;
    14. 	//入队列(尾插)
    15. 	//空队列时通过赋值完成尾插，队列中存在队列结点,按照逻辑关系完成连接;
    16. 	if (ps->tail == NULL)
    17. 	{
    18. 		ps->head = ps->tail = newnode;
    19. 	}
    20. 	else
    21. 	{
    22. 		ps->tail->next = newnode;
    23. 		ps->tail = newnode;
    24. 	}
    25. 	ps->size++;
    26. }

    队头出队列

    1. //队头出队列(头删)
    2. void QueuePop(Queue* ps)
    3. {
    4. 	assert(ps != NULL);
    5.  
    6. 	//空队列不可删
    7. 	assert(ps->tail != NULL);
    8.  
    9. 	//出队列
    10. 	//队列中只有一个队列结点
    11. 	if (ps->head->next == NULL)
    12. 	{
    13. 		free(ps->head);
    14. 		ps->head = ps->tail = NULL;
    15. 	}
    16. 	//队列中有两个以上队列结点
    17. 	else
    18. 	{
    19. 		QueueNode* next = ps->head->next;
    20. 		free(ps->head);
    21. 		ps->head = next;
    22. 	}
    23. 	ps->size--;
    24. }

    获取队列头部元素

    1. //获取队列头部元素
    2. QDataType QueueFront(Queue* ps)
    3. {
    4. 	assert(ps != NULL);
    5. 	//队列不为空
    6. 	assert(ps->head != NULL);
    7.  
    8. 	return ps->head->data;
    9. }

    获取队列尾部元素

    1. //获取队列尾部元素
    2. QDataType QueueBack(Queue* ps)
    3. {
    4. 	assert(ps != NULL);
    5. 	//队列不为空
    6. 	assert(ps->tail != NULL);
    7.  
    8. 	return ps->tail->data;
    9. }

    判断队列是否为空

    队列为空返回true，队列不为空false；

    1. //判断队列是否为空
    2. bool QueueEmpty(Queue* ps)
    3. {
    4. 	assert(ps);
    5. 	if (ps->tail == NULL)
    6. 	{
    7. 		return true;
    8. 	}
    9. 	return false;
    10. }

    获取队列长度

    1. //获取队列长度
    2. int QueueLength(Queue* ps)
    3. {
    4. 	assert(ps);
    5.  
    6. 	return ps->size;
    7. }

    栈与队列经典试题

    • 队列实现栈

    题目描述：

    请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）；

    实现 MyStack 类：

    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的，返回 true ；否则，返回 false

    题目链接:力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

    假设栈中入栈顺序为A B C D；则出栈顺序为D C B A； 如何用队列达到这种效果?

    首先将栈中的数据全部存放于一个队列，其次将存放数据的队列取对头元素入空队列，直至原先存放数据的队列只剩一个数据为止；

    此时原先的队列只剩一个元素，调用QueuePop()函数就可达到StackPop()函数的效果，但仅仅是一个元素达到了后进先出，将元素D删除后，回到原先假设情形；

     继续将非空队列中的数据放入空队列，直至非空队列只剩1个元素，调用QueuePop()函数删除仅剩元素；

    按此循环，直至两个队列全部为空；这样达到了出栈顺序为D C B A；

    假设栈中入栈顺序为A B C D，出栈两个元素即先删除D，后删除C；然后再入栈元素E， 那么元素E应该送入那个队列？才能完成出栈顺序为D C E B A？

    为了维持原先逻辑的一致性，选择将元素E送入到非空队列；然后继续按照原先逻辑pop数据；

     

     思路总结：

    数据入队列时，首先判断出那个队列不是空队列，然后将数据送入非空队列；

    数据出队列时，非空队列的前size-1个数据全部插入到空队列，然后删除非空队列仅剩的一个元素；两个队列始终保持一个为空；

    （注：队列定义时size为队列中有效数据的个数）

    1. typedef struct 
    2. {
    3.   Queue q1;
    4.   Queue q2;
    5. } MyStack;
    6.  
    7. MyStack* myStackCreate() 
    8. {
    9.    MyStack* p=(MyStack*)malloc(sizeof(MyStack));
    10.  
    11.    InitQueue(&(p->q1));
    12.    InitQueue(&(p->q2));
    13.    return p;
    14. }
    15.  
    16. //那个队列不为空，数据尾插到那个队列
    17. void myStackPush(MyStack* obj, int x) 
    18. {
    19. if(!QueueEmpty(&(obj->q1)))
    20. {
    21.    QueuePush(&(obj->q1),x);
    22. }
    23. //队列q1为空，无论队列q2为不为空，数据尾插到q2;
    24. else
    25. {
    26.     QueuePush(&(obj->q2),x);
    27. }
    28. }
    29.  
    30. int myStackPop(MyStack* obj) 
    31. {
    32.    //首先判断那个是空队列，假设法;
    33.    Queue* Empty=&(obj->q1);
    34.    Queue* NonEmpty=&(obj->q2);
    35.    if(!QueueEmpty(&(obj->q1)))
    36.    {
    37.        Empty=&(obj->q2);
    38.        NonEmpty=&(obj->q1);
    39.    }
    40.   //空队列为Empty，非空队列为NonEmpty;
    41.   //由于队列中包含队列的长度,需要将非空队列的前size-1个数据插入到空队列;
    42.   //队列每出一个数据,长度自动减一，当非空队列大于1个元素，不断将非空队列的数据插入到空队列；
    43.   while(QueueLength(NonEmpty)>1)
    44.   {
    45.       QueuePush(Empty,QueueFront(NonEmpty));
    46.       QueuePop(NonEmpty);
    47.   }
    48.   //非空队列只剩一个元素
    49.   int top=QueueBack(NonEmpty);
    50.   QueuePop(NonEmpty);
    51.   return top;
    52. }
    53.  
    54. int myStackTop(MyStack* obj) 
    55. {
    56.     //由于队列始终保持一个为空,取非空队列的对头元素即为栈顶元素
    57.    if(!QueueEmpty(&(obj->q1)))
    58.    {
    59.        return QueueBack(&(obj->q1));
    60.    }
    61.    else
    62.    {
    63.        return QueueBack(&(obj->q2));
    64.    }
    65. }
    66.  
    67. bool myStackEmpty(MyStack* obj) 
    68. {
    69.     //栈为空当且仅当两个队列皆为空
    70.    return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2));
    71. }
    72.  
    73. void myStackFree(MyStack* obj) 
    74. {
    75.    DestroyQueue(&(obj->q1));
    76.    DestroyQueue(&(obj->q2));
    77.  
    78.    free(obj);
    79. }

    • 栈实现队列

    题目描述：

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

    实现 MyQueue 类：

    • void push(int x) 将元素 x 推到队列的末尾
    • int pop() 从队列的开头移除并返回元素
    • int peek() 返回队列开头的元素
    • boolean empty() 如果队列为空，返回 true ；否则，返回 false

    题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

    假设队列中入队列顺序为A B C D；则出队列顺序为A B C D； 如何用栈达到这种效果?

    首先将队列中的数据全部存放于一个栈（pushstack），其次将存放数据的栈取栈顶元素依次入空栈(popstack)，直至原先存放数据的栈为空；

    此时popstack栈不断pop(删除）数据，直至popstack栈为空；达到了入队列顺序为A B C D ，出队列顺序为A B C D ；

     假设队列中入队列顺序为A B C D，出队列两个元素即先删除A，后删除B；然后再入队列元素E， 那么元素E应该送入那个栈？才能完成出队列顺序为A B C D E？

    数据E只能存放于空栈pushstack，只有当非空栈数据pop(删除)结束,然后将pushstack中的数据E插入到popstack栈，才能完成出队列顺序为A B C D E;

     思路总结：

    数据先送入到pushstack,不断入栈，当需要出数据时，为达到先入先出的效果，将pushstack栈中的数据全部送入popstack栈中，如果此时还有数据需要入栈,全部送入pushstack中,然后不断从popstack栈中pop(删除)数据,当popstack栈为空时,再将pushstack栈中的数据全部送入popstack栈中,按此循环; 
    1. typedef struct 
    2. {
    3.     Stack pushstack;//入数据
    4.     Stack popstack;//出数据
    5. } MyQueue;
    6.  
    7. //初始化队列
    8. MyQueue* myQueueCreate() 
    9. {
    10.     MyQueue* pst=(MyQueue*)malloc(sizeof(MyQueue));
    11.     InitStack(&(pst->popstack));
    12.     InitStack(&(pst->pushstack));
    13.     return pst;
    14. }
    15.  
    16. //数据入栈时全部存放于pushstack;
    17. void myQueuePush(MyQueue* obj, int x) 
    18. {
    19.     StackPush(&(obj->pushstack),x);
    20. }
    21.  
    22. //首先判断popstack栈是否为空，若popstack栈为空
    23. //需要将pushstack栈中的数据全部送入popstack栈中;
    24. //若popstack栈不为空,直接出数据,直到popstack为空;
    25. int myQueuePop(MyQueue* obj) 
    26. {
    27.   if(StackEmpty(&(obj->popstack)))
    28.   {
    29.     //捯数据,将pushstack栈中的数据全部放入popstack栈中;
    30.    while(!StackEmpty(&(obj->pushstack)))
    31.    {
    32.        StackPush(&(obj->popstack),StackTop(&(obj->pushstack)));
    33.        StackPop(&(obj->pushstack));//干掉pushstack栈中栈顶元素
    34.    }
    35.   }
    36.   //popstack栈不为空
    37.    int top=StackTop(&(obj->popstack));
    38.    StackPop(&(obj->popstack));
    39.    return top;
    40. }
    41.  
    42. //获取队头数据即popstack栈中即将出栈的第一个数据;
    43. int myQueuePeek(MyQueue* obj)
    44. {
    45.   if(StackEmpty(&(obj->popstack)))
    46.   {
    47.     //捯数据,将pushstack栈中的数据全部放入popstack栈中;
    48.    while(!StackEmpty(&(obj->pushstack)))
    49.    {
    50.        StackPush(&(obj->popstack),StackTop(&(obj->pushstack)));
    51.        StackPop(&(obj->pushstack));//干掉pushstack栈中栈顶元素
    52.    }
    53.   }
    54.   //popstack栈不为空
    55.    return StackTop(&(obj->popstack));
    56. }
    57.  
    58. //若队列为空当且仅当popstack与pushstack都为空;
    59. bool myQueueEmpty(MyQueue* obj) 
    60. {
    61.    return StackEmpty(&(obj->pushstack))&&StackEmpty(&(obj->popstack));
    62. }
    63. //销毁队列
    64. void myQueueFree(MyQueue* obj) 
    65. {
    66.     DestroyStack(&(obj->pushstack));
    67.     DestroyStack(&(obj->popstack));
    68.     free(obj);
    69. }

                                                         

  • 相关阅读:
    纳睿雷达冲刺上市：产能利用率不足仍要扩产，毛利率持续下滑
    node写接口之文章的查询接口
    Linux C select 的学习
    JSON使用
    Win10不能访问共享硬盘怎么办
    P5718 【深基4.例2】找最小值
    Ansible安装管理和模块的使用
    WPF中的DataContext
    Day18.2：对象创建的内存分析图解
    git打tag和版本控制规范
  • 原文地址：https://blog.csdn.net/m0_58963318/article/details/133711554