队列

基本概念

逻辑结构

定义

• 队列(Queue)：只允许在表的一端进行插入，另一端进行删除操作的线性表。
• 队头(Front)：线性表允许进行删除的一端。
• 队尾(Rear)：允许进行插入的一端。
• 空队列：不含任何元素的空表。

特点

先进先出(First In First Out,FIFO)

基本操作

1. InitQueue(&Q)：初始化。
2. QueueEmpty(Q)：判断队列Q是否为空，empty->true。
3. EnQueue(&Q,x)：进栈，队未满则加入x使之成为新队头。
4. DeQueue(&Q,&x)：出栈，删除队头元素并用x返回。
5. GetHead(Q,&x)：获取对头元素,非空则用x返回。
6. DestroyQueue(&S)：销毁栈，释放占用的存储空间。

存储结构

顺序存储

顺序队列

1. 顺序存储
2. 用一组地址连续的存储单元存放数据元素，同时设两个指针front, rear，分别指示队头元素和队尾元素下一个的位置。
3. 假溢出

//只能判断队空
QueueEmpty(){
  Q.front==Q.rear==0;
}

循环队列

1. 逻辑上视为一个环

//初始化
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;
}
////////牺牲一个单元区分队空队满/////////////
//判队空
bool isEmpty(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;
    //模运算将存储空间在逻辑上变成了‘环状’
    //队尾指针后移
    Q.rear=(Q.rear+1)%MaxSize;
    //牺牲了一个存储单元
    //队列中元素个数：(Q.rear-Q.front+MaxSize)% 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;
}

/////增设表示元素个数的数据成员/////
//队空：Q.size==0
//队满：Q.Size==MaxSize
/////增设tag数据成员///////////
//初始化：rear==front==tag==0;
//删除：tag=0;
//插入：tag=1;
//队空：front==rear && tag==0
//队满：front==rear && tag==1

链式存储

链队列

1. 同时带有队头指针和队尾指针的单链表。
2. 头指针指向头节点，尾指针指向队尾节点。
3. 适合数据元素变动大的情形，不会发生上溢的情形。
4. 带头结点的单链表、不带头结点的单链表。
5. 入队时第一个元素入队，出队时最后一个元素出队。

////带头结点//////

//初始化
void InitQueue(LinkQueue &Q){
    //建立头结点
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
    
    //不带头结点
    //Q.front = NULL;
    //Q.rear = NULL;
}

//判队空
//队空返回true，队满返回false
bool IsEmpty(LinkQueue Q){
    //不带头结点
    //if(Q.front==NULL)
    if(Q.front==Q.rear)
        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;
	Q.rear=s;
}	*/
    Q.rear->next=s;
    Q.rear=s; 
}

//出队
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q,front==Q.rear) return false;
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    //队中只有一个结点
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return true;
    /*LinkNode *p=Q.front;
    x=p->data;
    Q.front=p->next;
    if(Q.rear==p){
    	Q.front=null;
    	Q.rear=null;
    }*/
}

双端队列

两端都可以进行入队和出队操作的队列。

线性结构。

分为前端和后端，两端都可以入队和出队。

输出受限的双端队列、输入受限的双端队列。从某个端点插入的元素只能从该端点删除：两个栈底相接的栈。

在栈中合法的输出序列，双端队列中必定合法。

数据运算