【数据结构与算法】栈 & 队列

栈相关概念

什么是栈

是限定仅在 表尾（栈顶） 进行插入和删除 操作的线性表

栈又称为 后进先出（Last In First Out） 的线性表，简称 LIFO 结构

栈顶（top）

我们把允许 插入和删除 的一端称为 栈顶

栈底（bottom）

另一端称为 栈底

空栈

不含任何任何 数据元素的栈称为 ==空栈==

栈的操作

入栈

入栈又称压栈，就是向栈中放数据，每次放入一个 top 指针就 +1

出栈

取出栈中数据的操作，每取出一个 top 指针 就-1

清空栈

清空栈，是把 top指针 直接 指向 bottom指针，原本物理空间上数据还存在

栈的实现

创建队列结构体

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

#define STACK_INIT_SIZE 20 // 栈大小
#define STACK_INCREMENT 10 // 申请空间大小

typedef char ElemType;

// 定义栈
typedef struct {
    ElemType *base; // 栈低
    ElemType *top;  // 栈顶
    int stackSize;  // 当前栈容纳的大小
} sqStack;

初始化队列

// 初始化栈
void initStack(sqStack *s){
    s->base = (ElemType *)malloc(STACK_INCREMENT * sizeof(ElemType));
    if (s->base == NULL) exit(-1); // 空间申请失败

    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;

    printf("s->top：%p\n",s->top);
    printf("s->base：%p\n",s->base);
}

入栈（压栈）

// 压栈
void push(sqStack *s,ElemType e){
    // 判断是否满栈，满栈 则扩容
    if (s->top - s->base >= s->stackSize){
        s->base = (ElemType *)realloc(s->base,(s->stackSize + STACK_INCREMENT) * sizeof(ElemType));
        if(!s->base)exit(-1);
    }

    *(s->top) = e; // 栈顶的值 赋值 e
    s->top++;      // 栈顶地址向前推进
}

出栈

// 出栈
void pop(sqStack *s,ElemType *e){
    // 判断下溢出
    if (s->top == s->base){
        return;
    }
    *e = *--s->top; // 减之后 赋值，* 为取值，不是指针
}

当前栈长度

// 当前栈长度
int sqStackLen(sqStack *s){
    return s->top - s->base;
}

主函数使用

用户输入值，进行压栈，# 号结束，输出 栈内数据

int main(){

    sqStack s; 
    initStack(&s); // 初始化栈

    ElemType c;
    printf("输入栈：");
    while((c = getchar()) != '#'){
        getchar();
        push(&s, c); // 压栈
    }
    getchar(); // 把 \n 从缓冲区去掉

    ElemType e;
    while(sqStackLen(&s)){
        pop(&s,&e);  // 出栈
        printf("%c",e);
    }

    return 0;
}

扩展（栈链）

就是把 栈 和 单链表 结合, 如下图一样 栈链内元素是指针相连，而栈是顺序的地址

队列概念

什么是队列

队列（queue）是只允许在一端进行插入的操作，而在另一端进行删除操作的线性表。

队列主要特征是先进先出（First In First Out）

队列操作

队列的结构体

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

#define ElemType char

// 队列元素结构体 （链表）
typedef struct QNode{
    ElemType data;     // 队列节点数据
    struct QNode *next;// 队列指针
} QNode, *QueuePrt;

// 队列头尾
typedef struct {
    QueuePrt front, rear; // 队头指针，队尾指针
} LinkQueue;

创建队列

/*
 创建结构体
 在内存中创建一个头结点，将队列的头尾指针指向头结点，此时 队列为空
 */
void initQueue(LinkQueue *q){
    q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));
    if (!q->front)exit(-1);

    q->front->next = NULL;
}

入队列

// 入队列（下面是在从尾部入）
void inertQueue(LinkQueue *q, ElemType e){
    QueuePrt node = (QueuePrt)malloc(sizeof(QNode));
    if (!node)exit(-1);

    node->data = e;
    node->next = q->rear->next;
    q->rear->next = node;
    q->rear = node;
}

出队操作 （取出队列的数据）

// 出队操作 （下面是从队列头部取值）
void getQueue(LinkQueue *q,ElemType *e){
    if (q->front == q->rear)return; // 队列为空

    QueuePrt node = q->front->next;
    *e = node->data;
    q->front->next = node->next;  // 队列头部向移动一位

    if (q->rear == node)
        q->rear = q->front; // 队列最后数据被取出是，初始化为空

    free(node);
};

销毁队列

// 销毁队列
void deleteQueue(LinkQueue *q){
    while(q->front){
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
}

主函数使用

int main(){
    LinkQueue q;
    initQueue(&q);

    ElemType e = 0;
    printf("输入队列数据：");
    scanf("%c",&e);
    while(e != '#'){
        inertQueue(&q,e);
        scanf("%c",&e);
    }
    printf("队列中的数据：\n");

    while(q.rear != q.front){
        getQueue(&q,&e);
        printf("%c",e);
    }
    return 0;
}