队列

只允许在一端插入，一端删除的线性表

队头:允许删除的一端
队尾:允许插入的一端
先进先出(FIFO)

队列的顺序实现

1
2
3
4
5


#define Maxsize 10
typedef struct{
    ELemType data[Maxsize];//静态数组
    int front,rear;
}*SqQueue;

初始化

1
2
3
4
5
6


SqQueue InitQueue(SqQueue S){
    S=(SqQueue)malloc(sizeof(struct queue));
    S->front=0; //队头队尾指针都设为0
    S->rear=0;
    return S;
}

入队

1
2
3
4
5
6
7
8


bool EnQueue(SqQueue S,ElemType x){
    if((S->rear+1)%Maxsize==S->front){ //队列的判满条件
        return false; 
    }
    S->data[S->rear]=x;
    S->rear=(S->rear+1)%Maxsize;
    return true;
}

出队

1
2
3
4
5
6
7


bool DeQueue(SqQueue S,ElemType *x){
    if(S->rear==S->front){  //队列的判空条件
        return false;
    }
    *(x)=S->data[S->front];
    S->front=(S->front+1)%Maxsize;
}

队列的元素个数=(rear+Maxsize-front)%Maxsize

判断队空队满

rear==front，队空；（rear+1)%Maxsize==front，队满，这将浪费一个存储空间
额外设置size初始值0，每次插入size++，删除，size--，size直接指明队列的元素数量
额外设置tag初始值0，最近插入后tag设为1，最近删除后tag设为0；同样根据rear==front，额外判断此时tag的值就可判断是队空还是队满

模运算将存储空间在逻辑上改造为环状

队列的链式实现

单链表的阉割版(指增删操作)

1
2
3
4


typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

1
2
3


typedef struct{
    LinkNode *front,*rear;
}*LinkQueue;

初始化(带头节点)

1
2
3
4
5
6


LinkQueue InitQueue(LinkQueue Q){
    Q=(LinkQueue)malloc(sizeof(LinkQueue));
    Q->front=Q->rear=(LinkNode)malloc(sizeof(struct _LinkNode));
    Q->front->next=NULL;
    return Q;
}

入队

从尾指针插入！

1
2
3
4
5
6
7
8


void Enqueue(LinkQueue Q,int x){
    LinkNode new;
    new=(LinkNode)malloc(sizeof(struct _LinkNode));
    new->data=x;
    new->next=NULL;
    Q->rear->next=new;
    Q->rear=new;
}

出队

从头指针删除！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


//这里是使用的是带头节点的链队列
int Dequeue(LinkQueue Q){
    if(Q->front==Q->rear){ //判空返回-1，即非法出队
        return -1;
    }
    LinkNode p=Q->front->next; //找到队头结点
    int x;
    x=p->data;
    Q->front->next=p->next; //准备出队
    if(Q->rear==p){        //删最后一个元素也需要修改队尾指针
        Q->rear=Q->front;
    }
    free(p);
    return x;
}

双端队列

主要考察输出序列合法性的判断