美文网首页
06--队列

06--队列

作者: 清风烈酒2157 | 来源:发表于2020-12-15 08:35 被阅读0次

    [toc]

    队列

    队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

    顺序队列

    顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，如图所示

    5906cf9f961d502bd5e12b4d7f27e7f6

    每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

    • 顺序队列中的溢出现象：
      • "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
      • "真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
      • "假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

    循环队列

    在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。

    f625f32b40801c86a9bf9f44fb50a308

    在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。队空和队满的情况如图

    50c9687a49abb1a10951c11166a998b9

    循环队列顺序存储

    取模运算 才能有循环的感觉

    初始化 宏定义
    
#include "SqStack.h"
typedef struct CircularQueue{
    YZSElemType *data; //存储内存分配基地址
    int front;      //队列头索引
    int rear;       //队列尾索引
}CircularQueue;
//typedef struct CircularQueue * CQueue;
YZStatus InitCQuene(CircularQueue *Q);
YZStatus ClearQueue(CircularQueue *Q);
YZStatus IsEmptyQueue(CircularQueue Q);
YZStatus GetQueueLegth(CircularQueue Q,int *Length);
YZStatus GetTopQuene(CircularQueue Q,YZSElemType *e);
YZStatus PushQuene(CircularQueue *Q,YZSElemType e);
YZStatus PopQuene(CircularQueue *Q,YZSElemType *e);
YZStatus QueueTraverse(CircularQueue Q);

//1.1 初始化
YZStatus InitCQuene(CircularQueue *Q){
    Q->data = malloc(sizeof(YZSElemType)*MAXSIZE);
    if ( Q->data == NULL ) return ERROR;
    Q->front = 0;
    Q->rear = 0;
 
    return OK;
}
    清空
    //1.2 清空
YZStatus ClearQueue(CircularQueue *Q){
    Q->front = Q->rear = 0;
    return OK;;
}
    是否为空
    //1.3 是否为空
YZStatus IsEmptyQueue(CircularQueue Q){
    if(Q.front == Q.rear) return TRUE;
    return FALSE;
}
    长度
    //1.4 长度
YZStatus GetQueueLegth(CircularQueue Q,int *Length){
     if(Q.front == Q.rear) return 0;
    // 算出栈顶 栈尾之间的差值 就是未用的空间
     *Length = (Q.rear-Q.front+MAXSIZE) % MAXSIZE;
     return OK;
}
    队列顶部元素
    //1.5 获取队列front元素
YZStatus GetTopQuene(CircularQueue Q,YZSElemType *e){
    if(Q.front == Q.rear) return ERROR;
    *e = Q.data[Q.front];
    return OK;
}
    入队
    YZStatus PushQuene(CircularQueue *Q,YZSElemType e){
      if(((Q->rear+1)%MAXSIZE) == Q->front) return ERROR;
       Q->data[Q->rear] = e;
       Q->rear = (Q->rear+1)%MAXSIZE;
       return OK;
}
    出队
    //1.7出队列
YZStatus PopQuene(CircularQueue *Q,YZSElemType *e){
      if(Q->front == Q->rear) return ERROR;
       *e = Q->data[Q->front];
       Q->front = (Q->front+1)%MAXSIZE;
       return OK;
}
    遍历
    YZStatus QueueTraverse(CircularQueue Q){
    if(Q.front == Q.rear) return ERROR;
     int I;
    i = Q.front;
    while (i != Q.rear) {
        printf("%d   ",Q.data[I]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
    
}

    循环队列链式存储

    e089d9da4099a152ff7c745b8efe899d

    出队列,首节点指向首元节点下一个节点,是否首节点下一个节点
    入队列,尾插法

    初始化 宏定义

    一些头文件 宏定义 结构体构造

    #include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int YZStatus;
typedef int YZSElemType; /* SElemType类型根据实际情况而定，这里假设为int */
typedef struct QNode{
   YZSElemType data;
   struct QNode * next;
   
}QNode,*LinkQNode;
typedef struct LinkQueue{
   LinkQNode front;
   LinkQNode rear;
   
}LinkQueue;
YZStatus InitLinkQueue(LinkQueue *Q);
YZStatus DestoryLinkQueue(LinkQueue *Q);
YZStatus ClearLinkQueue(LinkQueue *Q);
YZStatus isEmptyLinkQueue(LinkQueue Q);
int ReturnLengthLinkQueue(LinkQueue Q);
YZStatus EnQueue(LinkQueue *Q,YZSElemType e);
YZStatus DeQueue(LinkQueue *Q,YZSElemType *e);
YZStatus GetHeadQueue(LinkQueue Q,YZSElemType *e);
YZStatus TraverseQueue(LinkQueue Q);

    初始化

    YZStatus InitLinkQueue(LinkQueue *Q){
    
    Q->front = Q->rear =    (LinkQNode)malloc(sizeof(QNode));
    if(Q->front == NULL) return ERROR;
    Q->front->next = NULL;
    return OK;
}
    销毁
    YZStatus DestoryLinkQueue(LinkQueue *Q){
    
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
  
}
    清空
    YZStatus ClearLinkQueue(LinkQueue *Q){
    LinkQNode q,p;
    Q->rear = Q->front;
    q = Q->front->next;
    //头尾在一块指向空
    Q->front->next = NULL;
    
    while (q) {
        p = q->next;
        free(q);
        q = p;
    }
    return OK;
  
}
    判空
    YZStatus isEmptyLinkQueue(LinkQueue Q){
    if(Q.rear == Q.front){
        return TRUE;
    }
    return FALSE;
  
}
    队列长度
    int ReturnLengthLinkQueue(LinkQueue Q){
    LinkQNode q;
    q = Q.front;//从头结点开始
    int I=0;
    while (q != Q.rear) {
        I++;
        q = q->next;
    }
    return I;
}
    入队
    YZStatus EnQueue(LinkQueue *Q,YZSElemType e){
  
    LinkQNode temp = (LinkQNode)malloc(sizeof(QNode));
    if (!temp){return ERROR;}
    temp->data = e;
    temp->next = NULL;
    Q->rear->next = temp;
    Q->rear = temp;
    return OK;
}
    出队
    YZStatus DeQueue(LinkQueue *Q,YZSElemType *e){
    if (Q->rear == Q->front) {
        return ERROR;
    }
    LinkQNode q;
    q = Q->front->next;
    Q->front->next = q->next;
    *e = q->data;
    //队尾
    if(q==Q->rear){
        
        Q->rear = Q->front;
        
    }
    free(q);
    
    return OK;
}
    遍历
    
YZStatus TraverseQueue(LinkQueue Q){
    LinkQNode q;
    q = Q.front->next;//从头结点开始
   
    while (q) {
        printf("%d\n",q->data);
        q = q->next;
    }
    return OK;

}
    队列头
    YZStatus GetHeadQueue(LinkQueue Q,YZSElemType *e){
    if (Q.rear == Q.front) {
        return ERROR;
    }
    LinkQNode q;
     q  = Q.front->next;//从头结点开始
    *e = q->data;
    return OK;
}

    示例

    LinkQueue Q;
    InitLinkQueue(&Q);
    for (int i=1; i<=10; i++) {
        EnQueue(&Q, i);
    }
     printf("\n");
    TraverseQueue(Q);
    int e;
    GetHeadQueue(Q, &e);
    printf("队列顶%d\n",e);
    DeQueue(&Q, &e);
    printf("出队%d\n",e);

    打印

    1
2
3
4
5
6
7
8
9
10
队列顶1
出队1

    相关文章

      网友评论

          本文标题：06--队列

          本文链接：https://www.haomeiwen.com/subject/jpuigktx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|06--队列|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！