第三章队列

队列的顺序实现

数据结构定义

typedef struct LinkNode{ //定义结点
    int data;
    struct LinkNode *next;
}LinkNode;
typedef struct { //再另设一个结构代表队列
    LinkNode *front, *rear;
    //front指向队头结点前一个结点，rear指向队尾结点
}LinkQueue;

初始化队列

void InitQueue(LinkQueue &Q){
    Q.front = (LinkNode*)malloc(sizeof(LinkNode));
    Q.rear = Q.front;
    Q.front->next = NULL;
}

判队空

bool IsEmpty(LinkQueue Q){
    if (Q.front == Q.rear) return true;
    return false;
}

入队

void EnQueue(LinkQueue &Q, int x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x ;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}

出队

bool DeQueue(LinkQueue &Q, int &x){
    if(Q.front==Q.rear) return false;
    LinkNode *p = Q.front->next;  //front指向第一个结点的前一个结点
    x = p->data;
    Q.front->next = p->next;
    if(Q.rear == p)  //如果是一个结点，出队后队列为空了
        Q.rear = Q.front;
    free(p);
    return true;
}

循环队列的实现

顺序队列的缺点

 入队和出队时，front和rear均后移，造成假上溢

解决方案

 将顺序表假想为首尾相连的环，每当front来到MaxSize-1时继续前进到0
    通过取余运算实现

数据结构定义

#define MaxSize 50
typedef struct{
    int data[MaxSize];
    int front, rear;
}SqQueue;

初始化队列

void InitQueue(SqQueue &Q){
    Q.front = 0;
    Q.rear = 0;
}

判队空

bool IsEmpty(SqQueue Q){
    if (Q.front==Q.rear) return true;
    return false;
}

入队

bool EnQueue(SqQueue &Q, int x){
    if ((Q.rear+1)%MaxSize == Q.front) //队满
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear+1)&MaxSize;
    return true;
}

出队

bool DeQueue(SqQueue &Q, int &x){
    if(Q.front==Q.rear) //队空
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    return false;
}

王道课后习题

3.2.1 在循环队列中设置标志tag

数据结构不变，只是添加一个变量，区分是什么操作导致的front==rear

int tag = 0;

入队

bool tag_EnQueue(SqQueue &Q, int x){
    if (Q.rear == Q.front && tag == 1) //队满
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear+1)&MaxSize;
    tag = 1;
    return true;
}

出队

bool DeQueue(SqQueue &Q, int &x){
    if(Q.front==Q.rear && tag==0) //队空
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    tag = 0;
    return false;
}

3.2.2 用栈实现队列中的元素逆置

将队列Q的元素出队后立即入栈，再出栈后入队

void reverse_Q(SqStack &S, LinkQueue Q){
    int x;
    while(!IsEmpty(Q)){ //将Q中元素依次入栈
        DeQueue(Q, x);
        Push(S, x);
    }
    while (!StackEmpty(S)) { //将S中的元素输出完成逆置
        Pop(S, x);
        Push(S, x);
    }
}

3.2.3 用两个栈来模拟一个队列

入队

bool two_EnQueue(SqStack &S1, SqStack &S2, int e){
    if(S1.top == MAXSIZE-1 && !StackEmpty(S2)) //S1满了且S2不为空
        return false;
    else if(S1.top != MAXSIZE-1) {//S1没满，直接入栈
        Push(S1, e);
        return true;
    }
    //还要补上S1栈满，但是S2为空时，可以直接将S1中元素移入S2等待输出
    else if(S1.top == MAXSIZE-1 && StackEmpty(S2)){
        int x=0;
        while(!StackEmpty(S1)){//将S1中的元素移到S2中去
            Pop(S1, x);
            Push(S2, x);
        }
        Push(S1, e);//将新入队的元素入S1
        return true;
    }
    return false;
}

出队

bool two_DeQueue(SqStack &S1, SqStack &S2, int &e){
    if(!StackEmpty(S2)){//S2不为空直接输出
        Pop(S2, e);
        return true;
    }
    else if (StackEmpty(S2) && !StackEmpty(S1)){ //S2为空，但S1不为空
        while(!StackEmpty(S1)){  //将S1中的元素移入S2
            Pop(S1, e);
            Push(S2, e);
        }
        Pop(S2, e);
        return true;
    }
    else
        return false;
}