数据结构-线性表-队列

定义

队列也是一种操作受限的线性表

队列是只允许在一端进行插入、在另一端进行删除的线性表

入队、出队

生活中的例子：在食堂打饭

相关术语：队头（允许删除的一端）、队尾（允许插入的一端）、空队列

队列的特点：先进先出(First In First Out)或称FIFO

队列的基本操作：

InitQueue(&Q) 初始化队列

Destroy(&Q) 销毁队列

EnQueue(&Q,x) 入队

DeQueue(&Q,&x) 出队

GetHead(Q,&x) 读队头元素

QueueEmpty(Q) 判断是否为空队

循环队列元素个数的计算

(rear+MaxSize-front)%MaxSize

顺序存储

#include <stdio.h>

#define MaxSize 10  //定义队列中元素的最大个数

typedef int ElemType;   //数据类型定义

typedef struct {
    ElemType data[MaxSize]; //用静态数组存储队列元素
    int front,rear; //队头指针和队尾指针
    //int size; 记录队列当前长度
    //  初始化时：rear = front = 0;   size = 0;
    //  插入成功：size ++;
    //  删除成功：size --;
    //int tag;
    //  tag值为0，表示最近进行的是删除操作；
    //  tag值为1，表示最近进行的是插入操作；
    //  只有插入操作，才有可能导致队列变满；
    //  只有删除操作，才有可能导致队列变空；
    //  队满条件：front == rear && tag == 1
    //  队空条件：front == rear && tag == 0
    //front指向队头元素
    //rear指向队尾元素的后一个位置
    //也就是下一个应该插入的位置
} SqQueue;  //顺序队

//初始化队列
void InitQueue(SqQueue &Q){
    //初始时，队头、队尾指针指向0
    Q.rear = Q.front = 0;   
}

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

//入队操作
bool EnQueue(SqQueue &Q, ElemType x){
    //循环队列队满的条件
    //队尾指针的再下一个位置是队头
    if((Q.rear+1)%MaxSize==Q.front){    
        return false;   //队满则报错
    }
    Q.data[Q.rear] = x; //将x插入队尾
    Q.rear = (Q.rear + 1)%MaxSize;    //队尾指针后移
    return true;
}

//出队操作
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear == Q.front){  //判断队空
        return false;   //队空则报错
    }
    x=Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    return true;
}

//获取队头元素的值，用x返回
bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear == Q.front){
        return false;   //队空则报错
    }
    x = Q.data[Q.front];
    return true;
}

void testQueue(){
    SqQueue Q;  //声明一个队列（顺序存储）
    InitQueue(Q);   //初始化队列
    //...后续操作...
}

int main(void){
    //保证编译通过
    return 0;
}

 链式存储

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

typedef int ElemType;

typedef struct LinkNode{    //链式队列结点
    ElemType data;
    struct LinkNode * next;
}LinkNode;

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

//初始化队列（带头结点）
void InitQueue(LinkQueue &Q){
    //初始化的时候front, rear都指向头结点
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next == NULL;
}

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

//新元素入队（带头结点）
bool EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;   //新结点插入到rear之后
    Q.rear = s; //修改表尾指针
}

//队头元素出队（带头结点）
bool Dequeue(LinkQueue &Q, ElemType &x){
    if(Q.front == Q.rear){
        return false;   //空队则报错
    }
    LinkNode *p = Q.front->next;
    x = p->data;    //用变量x返回队头元素
    Q.front->next = p->next;    //修改头结点的next指针
    if(Q.rear == p){    //此次是最后一个结点出队
        Q.rear = Q.front;   //修改rear指针
    }
    free(p);    //释放结点空间
    return true;
}

#if 0
//判断队列是否为空（不带头结点）
void InitQueue(LinkQueue &Q){
    //初始化的时候front, rear都指向NULL
    Q.front = NULL;
    Q.rear = NULL;
}

//判断队列是否为空（不带头结点）
bool IsEmpty(LinkQueue Q){
    if(Q.front == NULL){
        return true;
    }else{
        return false;
    }
}

//新元素入队，不带头结点
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next =NULL;
    //不带头结点的队列
    //第一个元素入队时要特殊处理
    if(Q.front == NULL){
        Q.front = s;    //在空队列中插入第一个元素
        Q.rear = s; //修改队头结点指针
    }else{
        Q.rear->next = s;   //新结点插入到rear之后
        Q.rear = s; //修改rear指针
    }
}

//队头元素出队（不带头结点）
bool DeQueue(LinkQuene &Q, ElemType &x){
    if(Q.front == NULL){
        return false;   //空队则报错
    }
    LinkNode *p = Q.front;  //p指向此次出队的结点
    x = p->data;    //用变量x返回队头元素
    Q.front = p->next;    //修改front指针
    if(Q.rear == p){    //此次是最后一个元素出队
        Q.front = NULL;   //front指向NULL
        Q.rear = NULL;  //rear指向NULL
    }
    free(p);    //释放结点空间
    return true;
}
#endif

void testLinkQueue(){
    LinkQueue Q;    //声明一个队列
    InitQueue(Q);   //初始化队列
    //...后续操作...
}

int main(void){
    //保证程序的正常编译
    return 0;
}

 双端队列

双端队列：只允许从两端插入，两端删除的线性表

输入受限的双端队列：只允许从一端插入，两端删除的线性表

输出受限的双端队列：允许从两端插入，从一端删除的线性表

考点：考察输出序列是否合法

栈中合法的序列，双端队列中也一定合法

在栈中非法的序列，在双端队列中可能合法