栈和队列

栈

定义

栈 是一种遵循 后进先出（LIFO） 原则的线性表。新添加和待删除的数据都保存在栈的同一端栈顶，另一端就是栈底。新元素靠近栈顶，旧元素靠近栈底

  • 栈的操作只能在这个线性表的表尾进行。

顺序栈 （常用）

  • 不可扩展

    • 使用数组实现

    • typedef struct SeqStack{
    ElemType datas [MAXSIZE];
    int top;    // 栈顶指针
}*Stack;
<!--code0-->

    • 这里定义了一个顺序存储的栈,它包含了三个元素:base, top, stackSize。其中base 是指向栈底的指针变量,top 是指向栈顶的指针变量, stackSize 指示栈的当前可使用的最大容量。

    • // 初始化栈
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10

typedef char ElementType;
void initStack(sqStack *s) {
    s->base = (ElementType *) malloc(STACK_INIT_SIZE * sizeof(ElementType));
    if (!s->base) {
        exit(0);
    }
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
};
<!--code1-->

  • 将队头指针指向链队列的头结点,而队尾指针指向终端结点。( 注:头结点不是必要的,但为了方便操作,我们加上了)

    • image-20211120193628931

  • 空队列时, front和rear都指向头结点。

    • image-20211120193740884

顺序存储结构

循环队列

  • 入队算法：rear = (rear +1)%数组长度 (rear+1)%QueueSize

  • 入队算法：rear = (rear +1)%数组长度 (front+1)%QueueSize

  • typedef struct {
    // 用于存放内存分配基地址
    // 这里也可以使用数组存放
    ElemType *base;

    int front;
    int rear;
};

双端队列

  • 普通双端队列

  • 循环队列改进

    • 从队尾删除：rear=(rear-1+QueueSize)%QueueSize

    • 从队头插入：front=(front-1+QueueSize)%QueueSize