Quartz 5

第三章 队列

Properties1
tags基础知识, 数据结构

4 min read

3.2 队列 Queue

基础概念

相关提炼内容见 queue。

队列的基本概念

队列的定义

  • 队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除
  • 向队列中插入元素称为入队或进队
  • 删除元素称为出队或离队
  • 特性：先进先出 First In First Out, FIFO

队列常见的基本操作

  • InitQueue(&Q)：初始化队列
  • DestoryQueue(&Q)：销毁队列
  • ClearQueue(&Q)：清空队列
  • QueueLength(Q)：求队列长度
  • GetHead(Q,&e)：得到队头元素
  • EnQueue(&Q, e)：插入元素
  • DeQueue(&Q, &e)：删除元素

队列的顺序存储结构

结点类型定义

#define MAXSIZE 100 // 最大队列长度
typedef struct{
    QElemType *base; // 初始化的动态分配存储空间
    int front;       // 队头指针
    int rear;        // 队尾指针
} SqQueue;

循环队列

  • 利用模运算（%）
  • 为了区分是队空还是队满，有三种处理方式
    • 牺牲一个单元来区分队空和队满
    • 类型中增设表示元素个数的数据成员
    • 类型中增设 tag 数据成员

循环队列的操作

初始化

void InitQueue(SqQueue &Q){
    Q.base = new QElemType[MAXSIZE];
    if(!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

判队空

bool isEmpty(SqQueue Q){
    if(Q.rear == Q.front) return true;  // 队空
    else return false;
}

入队

bool EnQueue(SqQueue &Q, QElemType e){
if((Q.rear+1) % MAXQSIZE == Q.front) return false; // 队满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return true;
}

出队

bool DeQueue(SqQueue &Q, QElemType &e){
if(Q.rear == Q.front) return false; // 队空
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return true
}

队列的链式存储结构

结点类型定义

typedef struct {
    ElemType data;
    struct LinkNode* next;
}LinkNode;
 
typedef struct{
    LinkNode *front, *rear;
}LinkQueue;

链式队列的基本操作

初始化

void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = new QElemType;
    If(!Q.front) return exit(OVERFLOW);
    Q.front -> next = NULL;
}

判队空

bool isEmpty(LinkQueue Q){
    if(Q.front == Q.rear) return true;
    else return false;

入队

void EnQueue(LinkQueue &Q, QElemType e){
    QNode* p;
    p = new QNode;
    if(!p) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}

出队

void DeQueue(LinkQueue &Q, QElemType &e){
    if(Q.front == Q.rear) return ERROR;
    QNode* p;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front;// 这个情况比较特殊
    delete p;
}
  • 双端队列
    • 双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构
    • 将队列的两端分别称为前端和后端，两端都可以入队和出队
    • 输出受限的双端队列：允许在一端进行插入和删除，另一端只允许插入
    • 输入受限的双端队列：允许在一端进行插入和删除，另一端只允许删除

Graph View

Backlinks