第三章 C语言：栈和队列

一、栈

特性：先进后出，顺序存储

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

#define CAPACITY 3  //默认初识容量
typedef int SData;

typedef struct Stack {
    SData* data;
    size_t size;
    size_t capacity;
}Stack;

void Init(Stack* s) {
    assert(s);
    s->data = (SData*)malloc(sizeof(SData) * CAPACITY);
    if (s == NULL) {
        perror("init::malloc");
        exit(1);
    }
    s->size = 0;
    s->capacity = CAPACITY;
}

bool Empty(Stack* s) {
    assert(s);
    return s->size == 0;
}

void CheckCapacity(Stack* s) {
    assert(s);
    if (s->size == s->capacity) {
        SData* tmp = (SData*)realloc(s->data, sizeof(SData) * (s->size + CAPACITY));
        if (tmp == NULL) {
            perror("realloc");
            exit(1);
        }
        s->data = tmp;
        s->capacity += CAPACITY;
    }
}

void Push(Stack* s, SData x) {
    assert(s);
    CheckCapacity(s);
    s->data[s->size] = x;
    ++s->size;
}

void Pop(Stack* s) {
    assert(s);
    if (!Empty(s)) {
        --s->size;
    }
}

size_t Size(Stack* s) {
    assert(s);
    printf("the stack size is %d\n", s->size);
    return s->size;
}

void PrintStack(Stack* s) {
    assert(s);
    if (!Empty(s)) {
        int i = 0;
        while (i < s->size) {
            printf("%d ", s->data[i]);
            ++i;
        }
        printf("\n");
    }

}

int main() {
    Stack s;
    Init(&s);
    Push(&s, 1);
    Push(&s, 3);
    Push(&s, 2);
    Push(&s, 4);
    Size(&s);
    PrintStack(&s);
    Pop(&s);
    Pop(&s);
    Pop(&s);
    Pop(&s);
    Pop(&s);
    Size(&s);
    PrintStack(&s);
    return 0;
}

二、队列

特性：先进先出，链式存储

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

typedef int QData;

typedef struct Queue {
    QData data;
    struct Queue* next;
}Queue;

void Init(Queue* q) {
    assert(q);
    q->next = (Queue*)malloc(sizeof(Queue));
    q->next->next = NULL;
}

bool Empty(Queue* q) {
    assert(q);
    return q->next->next == NULL;
}

void Push(Queue* q, QData x) {
    assert(q);
    Queue* node = (Queue*)malloc(sizeof(Queue));
    node->data = x;
    node->next = q->next->next;
    q->next->next = node;
}

void Pop(Queue* q) {
    assert(q);
    if (!Empty(q)) {
        Queue* cur = q->next->next;
        q->next->next = cur->next;
        free(cur);
        cur = NULL;
    }
}

size_t Size(Queue* q) {
    assert(q);
    size_t size = 0;
    if (!Empty(q)) {
        Queue* cur = q->next->next;
        while (cur) {
            ++size;
            cur = cur->next;
        }
    }
    printf("the list size is %d\n", size);
    return size;
}

void PrintQueue(Queue* q) {
    assert(q);
    if (!Empty(q)) {
        Queue* cur = q->next->next;
        printf("%d ", cur->data);
        while (cur->next) {
            printf("-> %d ", cur->next->data);
            cur = cur->next;
        }
        printf("\n");
    }
}

int main() {
    Queue q;
    Init(&q);
    Push(&q, 1);
    Push(&q, 3);
    Push(&q, 4);
    Push(&q, 2);
    Size(&q);
    PrintQueue(&q);
    Pop(&q);
    Pop(&q);
    Pop(&q);
    Pop(&q);
    Pop(&q);
    Size(&q);
    PrintQueue(&q);
    return 0;
}

三、循环队列

特性：先进先出，顺序存储，空间有限并循环利用，留一个空位区分空和满

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

#define CAPACITY 5     //总容量为5，数据容量为4
typedef int CQData;

typedef struct CirQue {
    CQData* data;
    int head;
    int tail;
    int size;
}CirQue;

void Init(CirQue* cq) {
    assert(cq);
    cq->data = (CQData*)malloc(sizeof(CQData) * CAPACITY); //多开辟一个空间
    cq->head = cq->tail = cq->size = 0;
}

bool Empty(CirQue* cq) {
    assert(cq);
    return cq->head == cq->tail;
}

bool Full(CirQue* cq) {
    assert(cq);
    return (cq->tail + 1) % CAPACITY == cq->head;
}

int Size(CirQue* cq) {
    assert(cq);
    return (cq->tail + CAPACITY - cq->head) % CAPACITY;
}

void Push(CirQue* cq, CQData x) {
    assert(cq);
    if (!Full(cq)) {
        cq->data[cq->tail] = x;
        cq->tail = (cq->tail + 1) % CAPACITY;
    }
}

void Pop(CirQue* cq) {
    assert(cq);
    if (!Empty(cq)) {
        cq->head = (cq->head + 1) % CAPACITY;
    }
}

void PrintCirQue(CirQue* cq) {
    assert(cq);
    if (!Empty(cq)) {
        int pos = cq->head;
        int size = Size(cq);
        while (size--) {
            printf("%d ", cq->data[pos]);
            pos = (pos + 1) % CAPACITY;
        }
        printf("\n");
    }
}

int main () {
    CirQue cq;
    Init(&cq);
    Push(&cq, 1);
    Push(&cq, 3);
    Push(&cq, 5);
    printf("the CirQue size is %d\n", Size(&cq));
    PrintCirQue(&cq);//1 3 5
    Push(&cq, 2);
    Push(&cq, 4);
    Push(&cq, 6);
    printf("the CirQue size is %d\n", Size(&cq));
    PrintCirQue(&cq);//1 3 5 2
    Pop(&cq);
    Pop(&cq);
    Pop(&cq);
    printf("the CirQue size is %d\n", Size(&cq));
    PrintCirQue(&cq);//2
    Push(&cq, 10);
    Push(&cq, 20);
    Push(&cq, 30);
    Push(&cq, 40);
    printf("the CirQue size is %d\n", Size(&cq));
    PrintCirQue(&cq);//2 10 20 30
    Pop(&cq);
    Pop(&cq);
    Pop(&cq);
    Pop(&cq);
    Pop(&cq);
    Pop(&cq);
    printf("the CirQue size is %d\n", Size(&cq));
    PrintCirQue(&cq);
    return 0;
}