[C++知识库]手撕链式栈+循环队列（动态分配长度）

链式栈

空栈示意图：

栈中有元素示意图：

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

//链式栈
typedef struct Node{
    int data;
    struct Node * next;
}NODE, * PNODE;

typedef struct Stack{
    PNODE pTop;   //栈顶
    PNODE pBottom;//栈底
}STACK, * PSTACK;

void init(PSTACK pS){//链栈的初始化
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (pHead == NULL)
    {
        printf("内存分配失败！\n");
    }
    pS->pBottom = pHead;  //初始栈顶栈底都指向头节点
    pS->pTop = pHead;
    pS->pTop->next = NULL;

}

void push(PSTACK pS, int val){ //原则：先入栈后变动栈顶指针
    PNODE pnew = (PNODE)malloc(sizeof(NODE));
    pnew->data = val;
    pnew->next = pS->pTop; //将新节点接在原栈顶上方
    pS->pTop = pnew;  //栈顶指针变动至最新位置
    return;
}

void traverse(PSTACK pS){
    PNODE p = pS->pTop;  //遍历指针获取到栈顶
    while(p != pS->pBottom){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return;
}

//出栈一次，并将元素输出在val中
bool pop(PSTACK pS, int * p){
    if(pS->pBottom == pS->pTop){  //栈空报错
        return false;
    }
    *p = pS->pTop->data;  //保存删去的值
    PNODE q = pS->pTop;
    pS->pTop = q->next;  //移动栈顶指针
    free(q);
    return true;
}

void clear(PSTACK pS){  //清空表中数据
    if(pS->pBottom == pS->pTop){  //栈空直接返回
        return ;
    }
    PNODE p = pS->pTop;
    while(p != pS->pBottom){
        PNODE q = p;
        p = p->next;
        free(q);
    }
    pS->pTop = pS->pBottom;
    return ;
}

int main(){
    STACK S;  //STACK等价于 struct Stack
    int val;  //保存出栈的元素
    init(&S);
    push(&S, 1);
    push(&S, 2);
    push(&S, 3);
    push(&S, 4);
    push(&S, 5);
    traverse(&S);
    if(pop(&S, &val)){
        printf("出栈元素为:%d\n", val);
    }else{
        printf("出栈失败");
    }
    traverse(&S);
    clear(&S);
    printf("将栈清空！\n");
    if(pop(&S, &val)){
        printf("出栈元素为:%d\n", val);
    }else{
        printf("出栈失败");
    }
    return 0;
}

循环队列

空队示意图：

队满判断方法：
牺牲一个元素空间，来区别队空或队满。入队前，先判Q.rear+1是否等于Q.front，若是则为队满。

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

#define MAX_SIZE 6   //宏定义  数组长度为6，最多能保存5个元素

typedef struct Queue
{
    int * pBase;  //数组的首地址
    int front;
    int rear;
}QUEUE;

void init(QUEUE * pQ){ //初始化一个长度为6的队列
    pQ->pBase = (int *)malloc(sizeof(int) * MAX_SIZE);
    pQ->front = 0;
    pQ->rear = 0;
}

//判断队列是否为空（引入一个空单元作为牺牲）
bool is_full(QUEUE * pQ){
    if((pQ->rear + 1) % MAX_SIZE == pQ->front){
        printf("该循环队列已满！\n");
        return true;
    }
    return false;
}

bool en_queue(QUEUE * pQ, int val){  //入队：入队一个元素，队尾向后移动一下
    if(is_full(pQ)){
        printf("队列已满，无法添加元素！\n");
        return false;
    }else{
        pQ->pBase[pQ->rear] = val;
        pQ->rear = (pQ->rear + 1) % MAX_SIZE;
        return true;
    }
}

bool de_queue(QUEUE * pQ, int * val){
    if(pQ->front == pQ->rear){
        printf("该队列为空，无法出队！\n");
        return false;
    }else{
        *val = pQ->pBase[pQ->front];
        pQ->front = (pQ->front + 1) % MAX_SIZE;
        return true;
    }
}

void traverse_queue(QUEUE * pQ){
    int i = pQ->front;  //找到队首
    if (pQ->front == pQ->rear)
    {
        printf("该循环队列为空！\n");
        return;
    }
    while((pQ->rear + MAX_SIZE - i) % MAX_SIZE > 0){
        printf("%d ", pQ->pBase[i]);
        i++;
    }
    printf("\n");
}

int main(){
    QUEUE Q;  //实例化一个队列
    int val; //保存出队元素
    init(&Q);
    en_queue(&Q, 1);
    en_queue(&Q, 2);
    en_queue(&Q, 3);
    if(de_queue(&Q, &val)){
        printf("出队伍成功！出队元素为:%d", val);
        printf("\n");
    }
    en_queue(&Q, 4);
    en_queue(&Q, 5);
    if(de_queue(&Q, &val)){
        printf("出队伍成功！出队元素为:%d", val);
        printf("\n");
    }
    en_queue(&Q, 6);
    traverse_queue(&Q);
    return 0;
}