首页 > 其他分享 >队列

队列

时间:2022-10-25 21:00:41浏览次数:48  
标签:return 队列 ElemType int front rear

4、队列

队列(Queue)是只允许在一段插入另一端删除的线性表

先进先出(FIFO)

4.1、顺序队列

队列定义和初始化

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

#define MaxSize 10
#define ElemType int
#define true 1
#define false 0


//定义一个队列
typedef struct{
    ElemType data[MaxSize];
    int front,rear;//front 对头   rear 对尾
}SqQueue;

//初始化一个队列
int InitSqQueue(SqQueue *Q){
    (*Q).front = (*Q).rear = 0;
    return true;
}

//判断队列是否为空
int QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front) return true;
    else return false;
}

入队 出队 获取队头

//入队操作
int EnQueue(SqQueue *Q,ElemType e){
    if((Q->rear+1)%MaxSize == Q->front) return false;//队列已经满了
    Q->data[Q->rear] = e;       //入队操作
    Q->rear = (Q->rear+1)%MaxSize;  //队尾指针后移
    return true;
}

//出队操作
int DeQueue(SqQueue *Q,ElemType *e){
    if(Q->rear == Q->front) return false;//如果队列为空,就出队失败
    *e = Q->data[Q->front]; //出队的数据
    Q->front = (Q->front+1)%MaxSize;    //头头后移
    return true;
}

//获取对头元素
int GetHead(SqQueue Q,ElemType *e){
    if(Q.rear == Q.front) return false;//如果队头等于对尾为空,获取失败
    *e = Q.data[Q.front]; //队头的数据
    return true;
}

测试

int main(){
    SqQueue Q;
    printf("没有初始化队列是否为空:%d\n",QueueEmpty(Q));
    InitSqQueue(&Q);
    printf("初始化后队列是否为空:%d\n",QueueEmpty(Q));

    printf("初始化队列后的队头:%d\n",Q.front);
    printf("初始化队列后的队尾:%d\n",Q.rear);

    EnQueue(&Q,1);
    EnQueue(&Q,2);//入队
    printf("入队列后的队尾:%d\n",Q.rear);
    
    ElemType x;
    DeQueue(&Q,&x);
    printf("出队的元素:%d\n",x);
    GetHead(Q,&x);
    printf("队头元素:%d\n",x);

    return 0;
}

//结果:
没有初始化队列是否为空:0
初始化后队列是否为空:1
初始化队列后的队头:0
初始化队列后的队尾:0
入队列后的队尾:2
出队的元素:1
队头元素:2

4.2、链表队列

定义和初始化

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

#define ElemType int
#define true 1
#define false 0

//结点
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

//链队列定义
typedef struct{
    LinkNode *front,*rear;//*front 队头指针, *rear 队尾指针
}LinkQueue;

//初始化带头结点的队列
int InitLinkQueue(LinkQueue *Q){
    (*Q).front = (*Q).rear = (LinkNode *)malloc(sizeof(LinkNode));
    if((*Q).front == NULL || (*Q).rear == NULL) return false;
    (*Q).front->next = NULL;
    return true;
}

//初始化不带头结点的队列
int InitLinkQueue1(LinkQueue *Q){
    (*Q).front = NULL;
    (*Q).rear = NULL;
    return true;
}

//带头结点判断是否为空
int IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear) return true;
    else return false;
}
//不带头结点判断是否为空
int IsEmpty1(LinkQueue Q){
    if(Q.front == NULL) return true;
    else return false;
}

入队 、出队

//带头结点入队操作
int EnQueue(LinkQueue *Q,ElemType e){
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL) return false;//分配内存失败
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}
//不带头结点入队操作
int EnQueue1(LinkQueue *Q,ElemType e){
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL) return false;//分配内存失败
    p->data = e;
    p->next = NULL;
    if(Q->front == NULL){
        Q->front = p;
        Q->rear = p;
    }else{
        Q->rear->next = p;
        Q->rear = p;
    }
}

//带头结点出队操作
int DeQueue(LinkQueue *Q,ElemType *e){
    if(Q->front == Q->rear) return false;//队列为空,出队失败
    LinkNode *p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(Q->rear == p){       //如果出队的元素是对尾元素,需要特殊处理
        Q->rear = Q->front;
    }
    free(p);//释放片
    return true;
}
//不带头结点出队操作
int DeQueue1(LinkQueue *Q,ElemType *e){
    if(Q->front == Q->rear) return false;//队列为空,出队失败
    LinkNode *p = Q->front;
    *e = p->data;
    Q->front = p->next;
    if(Q->rear == p){
        Q->front = NULL;
        Q->rear =NULL;
    }
    free(p);
    return true;
}

//获取对头元素
int GetHead(LinkQueue Q,ElemType *e){
    if(Q.front == Q.rear) return false;//队列为空,出队失败
    *e = Q.front->next->data;
    return true;
}

测试

int main(){
    LinkQueue Q;
    InitLinkQueue(&Q);
    printf("链队列是否为空:%d \n",IsEmpty(Q));

    EnQueue(&Q,11);
    EnQueue(&Q,22);
    printf("链队列是否为空:%d \n",IsEmpty(Q));

    ElemType x;
    DeQueue(&Q,&x);
    printf("链队列出队:%d \n",x);

    ElemType y;
    GetHead(Q,&y);
    printf("链队列的队头元素:%d \n",y);
    
    return 0;
}

//结果
链队列是否为空:1 
链队列是否为空:0 
链队列出队:11 
链队列的队头元素:22 

4.3、双端队列

双端队列:

只允许从两端插入两端删除的线性表

输入受限的双端队列:

只允许从一段进行插入两端进行删除的线性表

输出受限的双端队列:

只允许从两端进行插入一端进行删除的线性表

标签:return,队列,ElemType,int,front,rear
From: https://www.cnblogs.com/shuisanya/p/16826299.html

相关文章

  • 刷题 栈和队列3
    代码随想录LeetCode239. 滑动窗口最大值carl优先级队列#单调队列思路优先级队列解法:窗口移动过程中,不断将新元素加入优先级队列,如果最大值不在范围内,则弹出最大......
  • 我摊牌了!真正的灰度队列实现方案!全网你都搜不到!
    背景目前,公司方面RPC调用如Dubbo、Feign已经能支持基于灰度的调用,但是MQ还没有支持灰度的能力,因此导致在测试和生产环境业务验证、消息隔离方面体验比较差,因此我们......
  • js异步编程,eventLoop,消息队列,宏任务,微任务
    1.单线程的JavaScriptJavaScript是一门单线程语言,起因是设计之初js只用来操作dom,对表单进行简单的校验。在这种执行环境简单的情况下,自然就选择了单线程来处理程序......
  • Nodejs+Redis实现简易消息队列
    前言消息队列是存储数据的一个中间件,可以理解为一个容器。生产者生产消息投递到队列中,消费者可以拉取消息进行消费,如果消费者目前没有消费的打算,则消息队列会保留消息,直......
  • CF 253B(队列上维护2个指针后移)
    B.实验误差timelimitpertestmemorylimitpertestinputoutput小明做实验......
  • BZOJ 3192([JLOI2013]删除物品-双堆转头并头队列)
    3192:[JLOI2013]删除物品TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 123  Solved: 77[​​Submit​​][​​Status​​][​​Discuss​​]Descr......
  • 7-2 队列实现回文
    编写一个程序判断一个字符串是否是回文。回文是指一个字符序列以中间字符为基准两边字符完全相同,如字符序列"ABCDEDCBA"就是回文,而字符序列"ABCDEDBAC"就不是回文。空格不......
  • 【数据结构-队列】队列的基本操作
    目录1顺序表实现队列(循环队列)1.1定义1.2初始化1.3判队空1.4判队满1.5出队1.6入队1.7队长2单向链表实现队列2.1定义2.2初始化2.3判队空2.4判队满2.5出队2.6......
  • 阻塞队列介绍
    阻塞队列(BlockingQueue)是一个支持两个附加操作的队列。这两个附加的操作支持阻塞的插入和移除方法。1)支持阻塞的插入方法:意思是当队列满时,队列会阻塞插入元素的线程,直到队列......
  • 数据结构 玩转数据结构 3-5 数组队列
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13422 1重点关注1.1队列的特性FIFO,先进先出,水管 1.2队列的实现参考......