首页 > 其他分享 >队列

队列

时间：2023-08-18 16:45:13浏览次数：36  
标签：return 队列 queue cal array stack rear

队列：

只有两个口进出数据，一个专门进入数据，另一个专门出数据，先进先出，FIFO表

1. 顺序队列：

数据项 ：

存储元素的连续内存的首地址

容量

队头位置    (出队)

队尾位置    (入队)

[元素数量]

运算：创建、销毁、清空、出队、入队、队空、队满、队头、队尾、元素数量

需要注意的问题

1、存储元素是由一维数组+队头位置front+队尾位置rear来表示，入队rear+1,出队front+1，为了让队列能够反复使用，我们需要把一维数组想象成一个环，因此+1后都需要对容量cal求余

front = (front+1)%cal

rear = (rear+1)%cal

2、判断队空和队满问题

如果不处理该问题，那么队空和队满的条件都是 front==rear，就无法区分是队空还是队满

方法1：存储元素的内存多增加一个位置空间(常考)

队空：front==rear

队满：(rear+1)%cal == front

代价：需要额外申请存储一个元素的内存

计算数量：(rear-front+cal)%cal

队尾数据下标：(rear-1+cal)%cal

方法2：顺序队列结构中增加一个记录元素数量的数据项，通过数量与容量对比判断队空、队满

设计顺序队列
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TYPE int

//    顺序队列结构
typedef struct ArrayQueue
{
    TYPE* ptr;
    size_t cal;        //    容量
    size_t front;    //    队头位置head\begin
    size_t rear;    //    队尾位置tail\back
}ArrayQueue;

//    创建顺序队列
ArrayQueue* create_array_queue(size_t cal)
{
    //    申请队列结构内存
    ArrayQueue* queue = malloc(sizeof(ArrayQueue));
    //    申请存储队列元素的内存
    queue->ptr = malloc(sizeof(TYPE)*(cal+1));
    //    初始化容量
    queue->cal = cal+1;

    queue->front = 0;
    queue->rear = 0;

    return queue;
}

//    销毁
void destroy_array_queue(ArrayQueue* queue)
{
    free(queue->ptr);
    free(queue);
}
//    队空
bool empty_array_queue(ArrayQueue* queue)
{
    return queue->front == queue->rear;
}

//    队满
bool full_array_queue(ArrayQueue* queue)
{
    return (queue->rear+1)%queue->cal == queue->front;    
}

//    入队
bool push_array_queue(ArrayQueue* queue,TYPE data)
{
    if(full_array_queue(queue)) return false;

    queue->ptr[queue->rear] = data;
    queue->rear = (queue->rear+1)%queue->cal;
    return true;
}

//    出队
bool pop_array_queue(ArrayQueue* queue)
{
    if(empty_array_queue(queue)) return false;
    queue->front = (queue->front+1)%queue->cal;
    return true;
}

//    队头
TYPE head_array_queue(ArrayQueue* queue)
{
    return queue->ptr[queue->front];    
}

//    队尾
TYPE tail_array_queue(ArrayQueue* queue)
{
    return queue->ptr[(queue->rear - 1 + queue->cal)%queue->cal];    
}

//    数量
size_t size_array_queue(ArrayQueue* queue)
{
    return (queue->rear - queue->front + queue->cal)%queue->cal;
}

2.链式队列：

由若干个节点组成的队列结构，只能操作队头节点、队尾节点

链式队列结构：

队头指针

队尾指针

节点数量

运算：创建、销毁、队空、入队、出队、队头、队尾、数量

设计链式队列
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TYPE int

//    节点结构
typedef struct Node
{
    TYPE data;
    struct Node* next;
}Node;

//    创建节点
Node* create_node(TYPE data)
{
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

//    设计链式队列结构
typedef struct ListQueue
{
    Node* head;    //    队头指针
    Node* tail;    //    队尾指针
    size_t cnt;    //    节点数量
}ListQueue;

//    创建队列
ListQueue* create_list_queue(void)
{
    ListQueue* queue = malloc(sizeof(ListQueue));
    queue->head = NULL;
    queue->tail = NULL;
    queue->cnt = 0;
    return queue;
}


//    队空
bool empty_list_queue(ListQueue* queue)
{
    return 0 == queue->cnt;
}

//    入队
void push_list_queue(ListQueue* queue,TYPE data)
{
    Node* node = create_node(data);
    if(0 == queue->cnt)
    {
        queue->head = node;
        queue->tail = node;
    }
    else
    {
        queue->tail->next = node;
        queue->tail = node;
    }
    queue->cnt++;
}

//    出队
bool pop_list_queue(ListQueue* queue)
{
    if(empty_list_queue(queue))     return false;
    Node* temp = queue->head;
    queue->head = temp->next;
    free(temp);
    queue->cnt--;
    if(0 == queue->cnt) queue->tail = NULL;
    return true;
}

//    队头
TYPE head_list_queue(ListQueue* queue)
{
    return queue->head->data;
}

//    队尾
TYPE tail_list_queue(ListQueue* queue)
{
    return queue->tail->data;
}

//    数量
size_t size_list_queue(ListQueue* queue)
{
    return queue->cnt;
}

//    销毁队列
void destroy_list_queue(ListQueue* queue)
{
    while(pop_list_queue(queue));
    free(queue);
}

3.队列的应用：

1、数据排队处理-消息排队

2、树的层序遍历

3、图的广度优先遍历BFS

4、封装线程池、数据池

4.常考的笔试题、面试题：（喜欢考）

请使用两个栈来模拟一个队列的出队、入队功能(栈结构的功能都已实现，可以直接使用)

typedef struct Queue
{
     ArrayStack* s1;
     ArrayStack* s2;
}Queue;

1、s1负责入队、s2负责出队

2、当s2为空s1非空时，出队时，从s1转移到s2，s1需要全部转移到s2

3、当s1、s2非空时，优先出s2，直到s2出完，可以继续从s1转移到s2继续出队，直到s1、s2都为空才队空。

4、s2空s1满时，入队时需要s1全部转移到s2,入s1

5、s1s2满不入队，s1满s2非空也不入队

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TYPE int

//	设计顺序栈结构
typedef struct ArrayStack
{
	TYPE* ptr;	
	size_t cal;		//	容量
	size_t top;		//	栈顶位置 指向即将要入栈的位置
}ArrayStack;

//	创建
ArrayStack* create_array_stack(size_t cal)
{
	//	为顺序栈结构分配内存
	ArrayStack* stack = malloc(sizeof(ArrayStack));
	//	为存储数据元素分配内存
	stack->ptr = malloc(sizeof(TYPE)*cal);
	stack->cal = cal;
	stack->top = 0;
	return stack;
}

//	销毁
void destroy_array_stack(ArrayStack* stack)
{
	free(stack->ptr);
	free(stack);
}

//	栈空
bool empty_array_stack(ArrayStack* stack)
{
	return !stack->top;	
}

//	栈满
bool full_array_stack(ArrayStack* stack)
{
	return stack->top >= stack->cal;
}

//	入栈
bool push_array_stack(ArrayStack* stack,TYPE data)
{
	if(full_array_stack(stack)) return false;
	stack->ptr[stack->top++] = data;
	return true;
}

//	出栈
bool pop_array_stack(ArrayStack* stack)
{
	if(empty_array_stack(stack)) return false;
	stack->top--;
	return true;
}

//	栈顶
bool top_array_stack(ArrayStack* stack,TYPE* data)
{
	if(empty_array_stack(stack)) return false;
	*data = stack->ptr[stack->top-1];
	return true;
}

//	数量
size_t size_array_stack(ArrayStack* stack)
{
	return stack->top;
}

标签：return,队列,queue,cal,array,stack,rear
From： https://www.cnblogs.com/wangqiuji/p/17640940.html

相关文章

  • day10 - 栈与队列part01
    232. 用栈实现队列详解classMyQueue{public:stack<int>st_in;stack<int>st_out;MyQueue(){}voidpush(intx){st_in.push(x);}intpop(){if(st_out.empty()){while(!st_in.empt......
  • 关于云原生开源开发者沙龙「微服务X消息队列专场」的延期通知
    作者：微服务X消息队列各位报名参会的同学，大家好：非常感谢大家对本期云原生开源开发者沙龙「微服务X消息队列专场」的关注与支持。因故原定于8月12日（周六）举办的沙龙延期举行。具体时间和举办地点如下：阿里云云原生开源开发者沙龙微服务X消息队列专场深圳站，推迟于8月27日（......
  • Redis 过期监听 + 加阻塞队列
    https://redis.io/docs/manual/keyspace-notifications/ 简单一句话就是要订阅key失效事件 应用场景：在线客服中开启会话后，如果客户一段时间未回复，则结束会话。为了保证会话结束的时效性，通过redis订阅key失效事件处理        配置notify-keyspace-eventsE......
  • 栈与队列
    栈与队列前言 栈与队列作为线性表结构的代表，在计算机领域应用广泛。我们耳熟能详的系统栈，进程处理等计算机操作系统底层实现原理都是间接或者直接使用了相关数据结构或其思想，下面让我们来介绍这两种数据结构。栈结构定义  栈(stack)是限定仅在表尾进行插入或者删除的线性......
  • 队列的实现方式（先进先出 FIFO）--环形队列
    博客地址：https://www.cnblogs.com/zylyehuo/#-*-coding:utf-8-*-classQueue:def__init__(self,size=100):self.queue=[0for_inrange(size)]self.size=sizeself.rear=0#队尾指针self.front=0#队首指针......
  • 队列的内置模块（deque）--双向队列
    博客地址：https://www.cnblogs.com/zylyehuo/#-*-coding:utf-8-*-fromcollectionsimportdequeq=deque([1,2,3,4,5],5)q.append(6)#队尾进队print(q.popleft())#队首出队#用于双向队列q.appendleft(1)#队首进队q.pop()#队尾出队......
  • 利用队列的内置模块（deque）模拟 Linux 下的 tail 命令（输出文件中最后几行的内容）
    博客地址：https://www.cnblogs.com/zylyehuo/#-*-coding:utf-8-*-fromcollectionsimportdequedeftail(n):#n：指定输出文件中最后几行withopen('test.txt','r')asf:q=deque(f,n)returnqforlineintail(5):print......
  • 栈和队列
    栈和队列1，栈(stack)栈是限定仅在表尾进行插入或者删除操作的线性表栈 :线性表->一对一的关系-》数组链表栈是有限制的线性表(阉割版的线性表)栈更重要的是一种思想先进后出，后进先出 在程序设计或算法中，会经常用到这种思想“撸串”“死胡同堵车”“压子弹” 栈顶(top)：进行插入或......
  • RabbitMq的死信队列
    参考博客：https://blog.csdn.net/weixin_59074080/article/details/130673121https://blog.csdn.net/m0_46979453/article/details/127229005https://zhuanlan.zhihu.com/p/582787597?utm_id=0什么是死信队列正常情况下，一条消息自生产者发布到broke，然后转发到队列中，最后被订阅......
  • 【单调队列】 单调队列的“扫描线”理解
    【单调队列】单调队列的“扫描线”理解  “如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理比你强，而且比你影响时间更长。某种意义上，数学思维是生活中的思考的延伸。  算法学习笔记(66):单调队列。引用Pecco的算法笔记。  在这里给出一种扫描线......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99