8.队列

第一章 自测&关键词回顾

第二章 手撕

第一节 链式存储队列

• queue.h
• queue.c
• test

再封装的思想: Node还是链表中的节点, 只是用front和rear记录了下头和尾(替代了原来Node* phead(无头)的记录)

// 无头单链表+再封装 实现队列
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;
typedef struct Node {
    DataType data;
    struct Node *next;
} Node;

// 再封装(这个才是实际上的"队列")
// 再封装的思想,Node还是链表, 只是用front和rear记录了下头和尾
typedef struct Queue {
    Node *front;
    Node *rear;
    int queueSize;  // 队列大小
} Queue;

// 1.初始化
Queue *init(void);
// 2.销毁
void destory(Queue *q);
// 3.遍历
void traverse(Queue *q);
// 4.入队
void push(Queue *q, DataType data);
// 5.出队
void pop(Queue *q);
// 6.获取队头元素
DataType peek(Queue *q);
// 7.判空
bool empty(Queue *q);
// 8.获取队列元素个数
int size(Queue *q);

#include "queue.h"

// 1.初始化
Queue *init(void) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    q->queueSize = 0;
    return q;
}
// 2.销毁
void destory(Queue *q) {
    while (q->front) {
        Node *temp = q->front;
        q->front = q->front->next;
        free(temp);
    }
    free(q);
}
// 3.遍历
void traverse(Queue *q) {
    Node *pmove = q->front;
    while (pmove) {
        printf("%d->", pmove->data);
        pmove = pmove->next;
    }
    printf("END Size:%d\n", q->queueSize);
}
// 4.入队(尾插)
void push(Queue *q, DataType data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    if (q->front == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    q->queueSize++;
}
// 5.出队(头删)
void pop(Queue *q) {
    assert(q->front && "queue is empty!");
    Node *temp = q->front;
    q->front = q->front->next;
    if(q->front == NULL) { // 如果删空了,尾指针也要指向NULL
        q->rear = NULL;
    }

    free(temp);
    q->queueSize--;
}
// 6.获取队头元素
DataType peek(Queue *q) {
    assert(q->front && "queue is empty!");
    return q->front->data;
}
// 7.判空
bool empty(Queue *q) {
    return q->front == NULL;
}
// 8.获取队列元素个数
int size(Queue *q) {
    return q->queueSize;
}

#include "queue.h"

void test(void) {
    Queue *q = init();
    push(q, 1);
    push(q, 2);
    push(q, 3);
    push(q, 4);
    traverse(q);
    pop(q);
    printf("size: %d\n", size(q));
    pop(q);
    pop(q);
    printf("peek: %d\n", peek(q));
    pop(q);
    traverse(q);
    printf("empty? %s\n", empty(q) ? "true" : "false");

    destory(q);
}

int main() {
    test();
    return 0;
}

第二节 数组存储队列

• 数组实现存储队列
• 真正去用时

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

typedef int DataType;
typedef struct Queue {
    DataType *queue;
    int front;    // 指向下一元素出队的位置
    int rear;     // 指向队尾元素
    int maxSize;  // 数组的最大容量(初始化用)
} Queue;

// 1.初始化
Queue *init(int maxSize) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->queue = (DataType *)malloc(sizeof(DataType) * maxSize);
    q->front = 0;
    q->rear = -1;  // 表示(下一次没有可以出队的元素[空队列])
    q->maxSize = maxSize;
    return q;
}
// 2.销毁
void destory(Queue *q) {
    free(q->queue);
    free(q);
}
// 3.入队
void push(Queue *q, DataType data) {
    assert(!(q->rear >= q->maxSize - 1) && "rear reach maxSize!");  // 可能存在伪溢出
    q->queue[++q->rear] = data;
}
// 4.出队
void pop(Queue *q) {
    assert(!(q->rear < q->front) && "queue is empty!");  // 空
    q->front++;
}
// 5.判空
bool empty(Queue *q) {
    return q->rear < q->front;
}
// 6.元素个数
int size(Queue *q) {
    return q->rear - q->front + 1;
}
// 7.获取队头元素
int peek(Queue *q) {
    assert(!(q->rear < q->front) && "queue is empty!");  // 空
    return q->queue[q->front];
}
// 8.遍历
void traverse(Queue *q) {
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d->", q->queue[i]);
    }
    puts("END");
}

// 展示伪溢出
void test(void) {
    Queue *q = init(3);
    push(q, 1);
    push(q, 2);
    push(q, 3);
    pop(q);        //  这里弹出了一个
    push(q, 300);  // 再插入应该不会报才对(但还是报错了)
    traverse(q);
    destory(q);
}

int main() {
    test();
    return 0;
}

这里还封装了函数, 真正去用时,连函数都不会封装; 定一个全局变量, 拿来就是用.

#include <stdbool.h>
#include <stdio.h>

#define N 100

int q[N];
int hh = 0, tt = -1;  // hh指向队头元素, tt指向队尾元素
// 1.push
void push(int x) {
    q[++tt] = x;
}
// 2.pop
void pop() {
    hh++;
}

// 3.取队头
int peek() {
    return q[hh];
}
// 4.判空
bool empty() {
    return tt < hh;  // 空的
}

第三章 相关应用

第一节 循环队列

解决假溢出的问题(充分利用空间)

• 实现的时候遇到的问题
  1. 关于size的计算: 一定是 (rear-front+N)%N 因为计算一段的长度一定是”末尾-头”,只是因为这里是循环的, 减为负的情况,+N%N就解决了
  2. 问题:如果N个空间全部利用的话 (rear-front+N)%N 初始时:rear和front都是0, 结果为0; 添加5个元素后rear绕一圈回来还是0,front不动,从而导致不知道是空还是满
  • 解决:牺牲一个空间使得 队空(front==rear) 和 队满((rear+1)%N==front) 状态有明确区分
    • 也就是, 如果((rear+1)%N==front)就不能push了==>满了
    • 如果front==rear就不能pop了==>空了
  3. 关于出队和入队: 因为是循环, 所以直接 + 1即可, 又因为越界,所以%N

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>

#define N 5

int q[N];
int front = 0, rear = 0;  // 注意front在队头元素的位置, rear在尾元素的下一个位置

// 入队
void push(int x) {
    assert(!((rear + 1) % N == front) && "circularQueue is full");
    q[rear] = x;
    rear = (rear + 1) % N;
}
// 出队
void pop() {
    assert(!(front == rear) && "circularQueue is empty");
    front = (front + 1) % N;
}
// 获取队头元素
int peek() {
    assert(!(front == rear) && "circularQueue is empty");
    return q[front];
}
// 判空
bool empty() {
    return front == rear;
}
// 获取元素个数
int size() {
    return (rear - front + N) % N;
}

// 遍历
void traverse() {
    for (int i = front; i != rear; i = (i + 1) % N) {
        printf("%d->", q[i]);
    }
    puts("END");
}

void test01(void) {
    push(1);
    push(2);
    traverse();
    pop();
    // push(3);
    push(4);
    push(5);
    push(6);
    traverse();
}

int main() {
    test01();
    return 0;
}

第四章 上手真题

第五章 比赛怎么用