队列

定义

队列是一种特殊的线性表,其插入和删除操作分别在线性表的两端进行,插入称为入队(enqueue),删除称为出兑(dequeue),允许入队的一端称为队尾(rear),允许出队的一端称为队头(front);

假溢出问题

首先初始化一个空队列,然后c1,c2,c3,c4,c5,c6入队,然后c1,c2,c3,c4相继出队,这就造成了队列已满的假象,其实0-3位置是空的.
为了解决这个问题,我们一般采用循环队列的方法,

循环队列
image.png

我们判空的条件是Q->rear == Q->front,那么循环队列会出现在队满的情况下Q->rear == Q->front,这就造成了无法判空的问题,那么为了解决这个问题,我们可以牺牲一个存储单元,当存储数据数量等于队列最大长度-1的情况下我们就认为已经满了无法在进行入队操作

image.png

所以:

• 判断队空: Q.front = Q.rear
• 判断队满: (Q.rear+1)%maxSize = Q.front

队列同栈一样也分为顺序存储,链式存储

顺序队列

定义

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

typedef struct {
    QElemType data[MAXSIZE];
    int front;          //头
    int rear;           //尾
}SQueue;

初始化空队列

Status initQueue(SQueue *Q){
   Q->front = 0;
   Q->rear = 0;
   return OK;
}

清空队列

Status clearQueue(SQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

队列判空

Status queueEmpty(SQueue Q){
    return Q.front == Q.rear ? TRUE : FALSE;
}

队列长度

int queueLength(SQueue Q){
    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}

队列入队

Status enQueue(SQueue *Q,QElemType e){
   //如果队满直接返回error
   if ((Q->rear + 1) % MAXSIZE == Q->front) {
       return ERROR;
   }
   Q->data[Q->rear] = e;
   //将队尾往后移
   Q->rear = (Q->rear + 1)%MAXSIZE;
   return OK;
}

队列出队

Status deQueue(SQueue *Q,QElemType *e){
    //如果为空直接返回error
    if (Q->rear == Q->front) {
        return  ERROR;
    }
    *e = Q->data[Q->front];
    //将队头往后移
    Q->front = (Q->front + 1)%MAXSIZE;
    return OK;
}

队列遍历

Status queueTravel(SQueue Q){
    int i = Q.front;
    while (i != Q.rear) {
        printf("%d  \n",Q.data[i]);
        i = (i+1)%MAXSIZE;
    }
    return OK;
}

函数调用

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    QElemType e;
    SQueue Q;
    initQueue(&Q);
    for (int i = 0; i < 11; i++) {
        enQueue(&Q, i+1);
    }
    queueTravel(Q);
    printf("队列长度%d\n",queueLength(Q));
    printf("队列是否为空%d\n",queueEmpty(Q));
    deQueue(&Q, &e);
    deQueue(&Q, &e);
    queueTravel(Q);
    printf("队列长度%d\n",queueLength(Q));
    return 0;
}

链式队列

定义

//这里的队列都是带有头结点的,
typedef struct QueueNode{
    QElemType data;
    struct QueueNode *next;
}QueueNode;
typedef QueueNode * QueuePtr;
typedef struct {
    QueueNode *front;
    QueueNode *rear;
}LinkQueue;

初始化空队列

Status initQueue(LinkQueue *Q){
    Q->front = malloc(sizeof(QueueNode));
    Q->rear = Q->front;
    //如果没开辟成功返回error
    if (Q->front == NULL) {
        return ERROR;
    }
    //将front和rear设置为null
    Q->front->next = NULL;
    return OK;
}

队列的销毁与清空

Status destoryQueue(LinkQueue *Q){
    QueuePtr temp;
    while (Q->front) {
        temp = Q->front->next;
        free(Q->front);
        Q->front = temp;
    }
    return OK;
}
Status clearQueue(LinkQueue *Q){
    QueuePtr p,q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    return OK;
}

队列的判空

Status queueEmpty(LinkQueue *Q){
    return Q->front == Q->rear;
}

获取队列长度

int queueLength(LinkQueue Q){
    int count = 0;
    QueuePtr p;
    p = Q.front;
    while (p != Q.rear) {
        count ++;
        p = p->next;
    }
    return count;
}

队列入队

Status enQueue(LinkQueue *Q,QElemType e){
    QueuePtr temp = malloc(sizeof(QueueNode));
    if (!temp) return ERROR;
    temp->data = e;
    temp->next = NULL;
    //将temp加入队列
    Q->rear->next = temp;
    //将rear后移
    Q->rear = temp;
    return OK;
}

队列出队

Status deQueue(LinkQueue *Q,QElemType *e){
    if (Q->front == Q->rear) return ERROR;
    QueuePtr temp = Q->front->next;
    *e = temp->data;
    //将front后移
    Q->front->next = temp->next;
    //若队头就是队尾,则删除后将rear指向头结点.
    if (temp == Q->rear) {
        Q->rear = temp;
    }
    free(temp);
    return OK;
}

队列遍历

Status queueTravel(LinkQueue Q){
   QueuePtr p;
   p = Q.front->next;
   while (p) {
       printf("%d\n",p->data);
       p = p->next;
       
   }
   return OK;
}

调用

int main(int argc, const char * argv[]) {
    // insert code here...
    LinkQueue Q;
    QElemType e;
    initQueue(&Q);
    enQueue(&Q, 1);
    enQueue(&Q, 2);
    enQueue(&Q, 3);
    enQueue(&Q, 5);
    queueTravel(Q);
    deQueue(&Q, &e);
    queueTravel(Q);
    return 0;
}