栈

栈是只允许在表的一端进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

主要操作为：push、pop、getTop、isEmpty、isFull。

顺序栈

顺序栈是用顺序表实现的栈，栈顶指针 top 指向栈顶元素的位置。

由于数组的下标从 $0$ 开始，所以栈顶指针 top 初始化为 $-1$，判断栈空时 top 为 $-1$，判断栈满时 top 为数组的最大下标即 maxSize - 1。

• push：先将元素入栈，再将栈顶指针 top 加一
• pop：将栈顶指针 top 减一即可
• isEmpty：判断栈空时 top 为 $-1$
• isFull：判断栈满时 top 为 maxSize - 1

双栈共享空间

一个以左端为栈底，另一个以右端为栈底，两个栈共享一个数组空间。

多栈共享空间

1. 初始平均分配空间
2. 若一个栈满，需要将后边的所有元素右移一位，空出空间

链式栈

链式栈是用链表实现的栈，栈顶指针 top 指向栈顶元素的位置，栈底元素的指针域为 NULL。（无头结点）

初始化时，栈顶指针 top 为 NULL，判断栈空时 top 为 NULL。

应用

• 数值转化
• 括号匹配
• 表达式求值
• 递归

队列

队列是只允许在表的一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为先进先出（First In First Out）的线性表，简称FIFO结构。

主要操作为：push、pop、getFront、isEmpty、isFull。

顺序队列

使用数组实现的队列，队头指针 front 和队尾指针 rear 分别指向队头元素和队尾（即下一个入队元素的位置）。 当 front == rear 时，队列为空 当 rear - front == maxSize 时，队列满

• push：先将元素入队，再将队尾指针 rear 加一
• pop：将队头指针 front 加一即可
• isEmpty：判断队列空时 front == rear
• isFull：判断队列满时 rear - front == maxSize

循环队列

在顺序队列的基础上，将队列的头尾相连，形成一个环形结构。

为了区别队列为空和队列满的情况，需要浪费一个存储单元。于是，队列的最大长度为 maxSize - 1。

• push：先将元素入队，rear = (rear + 1) % maxSize
• pop：front = (front + 1) % maxSize
• isEmpty：front == rear
• isFull：(rear + 1) % maxSize == front

链式队列

不含头结点以及尾指针的链表，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素。

• push：需要特判队列为空的情况，此时需要修改队头指针 front
• pop：需要特判队列出队后为空的情况，此时需要修改队尾指针 rear

应用

• 分层遍历（滚动数组）