3.1 栈、顺序栈、链栈、共享栈
3.1.1 栈的定义及基本操作
栈（Stack）是只允许在一端进行插入或删除操作的线性表。
线性表的基本操作
InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素
StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。
3.1.2 顺序栈
栈是逻辑结构，栈有两种存储方式，一种是顺序栈。利用一组地址连续的存储单元存放自栈底到栈顶的数据元素（数组），以及一个指向栈顶元素的指针（top指针）。
#define ElemType int
#define MaxSize 10
#include <iostream>
using namespace std;
typedef struct {
ElemType data[MaxSize];
int top;
} SqStack;
//初始化栈
void InitStack(SqStack &stack) {
stack.top = -1; //初始化栈顶指针，-1表示栈空
}
//判断一个栈是否为空
bool StackEmpty(SqStack stack) {
return stack.top == -1; //栈顶指针为-1时表示栈空
}
//进栈，将数据x存入到栈中
bool Push(SqStack &stack, ElemType x) {
if (stack.top == MaxSize - 1) {
return false; //栈已满
}
//先将top指针向上移动一位，然后将数据存入栈中
stack.data[++stack.top] = x;
return true;
}
//出栈，将出栈元素存入x中
bool Pop(SqStack &stack, ElemType &x) {
if (StackEmpty(stack)) {
return false; //栈空
}
//先出栈，再将栈顶指针top向下移动一位
x = stack.data[stack.top--];
return true;
}
//获取栈顶元素,将栈顶元素赋值给x
bool GetTop(SqStack &stack, ElemType &x) {
if (StackEmpty(stack)) {
return false; //栈空
}
//将栈顶元素的值赋值给x
x = stack.data[stack.top];
return true;
}
顺序栈的缺点是栈的大小不可变，当栈内元素过少时就会浪费很多空间。共享栈可以提高空间的利用率，两个栈共享同一片空间，两个栈从两边往中间增长。
3.1.3 链栈
栈的另一种存储方式就是采用链式存储的链栈，通常采用单链表实现。
栈的插入和删除操作都是在表头进行操作，入栈就相当于采用头插法插入新的节点，出栈就是删除表头节点。采用带头结点和不带头结点的方式存在些许区别。
#include <iostream>
using namespace std;
#define ElemType int
typedef struct StackNode {
ElemType data;
struct StackNode *next;
} *LinkStack;
void InitStack(LinkStack &linkStack) {
linkStack = new StackNode;
linkStack->next = nullptr;
StackNode *h = linkStack; //指向头结点的指针
StackNode *s; //临时节点
ElemType e;
cin >> e;
while (e != 9999) {
s = new StackNode;
s->data = e;
s->next = h->next;
h->next = s;
cin >> e;
}
}
//判断一个栈是否为空
bool StackEmpty(LinkStack linkStack) {
return linkStack->next == nullptr; //栈顶指针为-1时表示栈空
}
//出栈，删除头节点的下一个节点
bool Pop(LinkStack &linkStack, ElemType &e) {
if (StackEmpty(linkStack)) {
return false;
}
e = linkStack->next->data;
auto *k = linkStack->next;
linkStack->next = linkStack->next->next;
free(k);
return true;
}
//进栈，将元素e压入栈中
bool Push(LinkStack &linkStack, ElemType e) {
auto *node = new StackNode;
if (node == nullptr) {
return false; //内存分配不足
}
node->data = e;
node->next = linkStack->next;
linkStack->next = node;
return true;
}
#include <iostream>
using namespace std;
#define ElemType int
typedef struct StackNode {
ElemType data;
struct StackNode *next;
} *LinkStack;
//判断一个栈是否为空
bool StackEmpty(LinkStack linkStack) {
return linkStack == nullptr; //栈顶指针为-1时表示栈空
}
//出栈，删除第一个节点
bool Pop(LinkStack &linkStack, ElemType &e) {
if (StackEmpty(linkStack)) {
return false;
}
auto *h = linkStack;
e = linkStack->data;
linkStack = linkStack->next;
free(h);
return true;
}
//进栈，将元素e压入栈中
bool Push(LinkStack &linkStack, ElemType e) {
auto *node = new StackNode;
if (node == nullptr) {
return false; //内存分配不足
}
node->data = e;
node->next = linkStack;
linkStack = node;
return true;
}
3.2 队列
3.2.1 队列的定义和基本操作
队列（Queue）是只允许在一端进行插入，在另一端删除的线性表。
队列的基本操作
InitQueue(&Q)：初始化队列，构造一个空队列Q。
DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。
EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
3.2.2 队列的顺序存储
队列有两种存储结构，第一种是顺序存储，指分配一块连续的存储单元存放独立中的元素（数组），并附设两个指针，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置。
#define ElemType int
#define MaxSize 10
#include <iostream>
using namespace std;
typedef struct {
ElemType data[MaxSize];
int front, rear;
} SqQueue;
//初始化队列
void InitQueue(SqQueue &queue) {
queue.front = 0;
queue.rear = 0;
}
//判断队列是否为空
bool QueueEmpty(SqQueue queue) {
return queue.front == queue.rear;
}
//入队
bool EnQueue(SqQueue &queue, ElemType x) {
if ((queue.rear + 1) % MaxSize == queue.front) {
return false; //队满
}
queue.data[queue.rear] = x;
queue.rear = (queue.rear + 1) % MaxSize; //队尾指针后移一位
return true;
}
//出队
bool DeQueue(SqQueue &queue, ElemType &x) {
if (QueueEmpty(queue)) {
return false; //队空
}
x = queue.data[queue.front];
queue.front = (queue.front + 1) % MaxSize; //队头指针后移一位
return true;
}
//获取队头元素
bool GetHead(SqQueue &queue, ElemType &x) {
if (QueueEmpty(queue)) {
return false; //队空
}
x = queue.data[queue.front];
return true;
}
采用上述方式时，队空或队满都是Q.rear==Q.front，为了能够判断出队满的情况，需要牺牲一个队内的存储单元。还可以使用以下两种不需要牺牲队列存储单元的方式判断队满。
typedef struct {
ElemType data[MaxSize];
int front, rear;
int size; //队内元素的个数
} SqQueue;
当size==MaxSize时，表示队满；当size==0时，表示队空。
tag为0表示删除，1表示插入。当Q.rear==Q.front且tag为0时则是由删除数据引起的，那么肯定是队空。当Q.rear==Q.front且tag为1时则是由插入数据引起的，那么肯定是队满。
3.2.3 队列的链式存储
#define ElemType int
#define MaxSize 10
#include <iostream>
using namespace std;
typedef struct LinkNode { //链式队列节点
ElemType data;
struct LinkNode *next;
} LinkNode;
typedef struct { //链式队列
LinkNode *front, *rear;
} LinkQueue;
//初始化队列
void InitQueue(LinkQueue &queue) {
//创建一个头节点，两个指针都指向头节点
queue.front = queue.rear = new LinkNode;
queue.front->next = nullptr;
}
//判断队列是否为空
bool IsEmpty(LinkQueue queue) {
//当对头指针与队尾指针都指向头结点时表示队空
return queue.front == queue.rear;
}
//入队
void EnQueue(LinkQueue &queue, ElemType x) {
auto *s = new LinkNode;
s->data = x;
s->next = nullptr;
queue.rear->next = s; //新节点插入到rear之后
queue.rear = s; //队尾指针修改为s
}
//出队
bool DeQueue(LinkQueue &queue, ElemType &x) {
if (IsEmpty(queue)) {
return false; //队空
}
LinkNode *p = queue.front->next; //待出队节点
x = p->data;
queue.front->next = p->next; //修改头结点的指向
if (queue.rear == p) { //如果删除的节点是最后一个节点
queue.rear = queue.front;
}
free(p);
return true;
}
#define ElemType int
#define MaxSize 10
#include <iostream>
using namespace std;
typedef struct LinkNode { //链式队列节点
ElemType data;
struct LinkNode *next;
} LinkNode;
typedef struct { //链式队列
LinkNode *front, *rear;
} LinkQueue;
//初始化队列
void InitQueue(LinkQueue &queue) {
//创建一个头节点，两个指针都指向头节点
queue.front = nullptr;
queue.rear = nullptr;
}
//判断队列是否为空
bool IsEmpty(LinkQueue queue) {
//对头或者队尾指针为null时表示队空
return queue.front == nullptr;
//或者 return queue.rear == nullptr;
}
//入队
void EnQueue(LinkQueue &queue, ElemType x) {
auto *s = new LinkNode;
s->data = x;
s->next = nullptr;
if (IsEmpty(queue)) { //队列为空时
queue.front = queue.rear = s;
} else {
queue.rear->next = s; //将新节点插入到rear之后
queue.rear = s; //修改rear为s
}
}
//出队
bool DeQueue(LinkQueue &queue, ElemType &x) {
if (IsEmpty(queue)) {
return false; //队空
}
LinkNode *p = queue.front; //待出队节点
x = p->data;
queue.front = p->next; //修改头结点的指向
if (queue.rear == p) { //如果删除的节点是最后一个节点
queue.front = nullptr; //这句不加也可以，因为执行queue.front = p->next;时front已经指向null了
queue.rear = nullptr;
}
free(p);
return true;
}
3.2.4 双端队列
双端队列是队列一个变种，指允许两端都可以进行入队和出队操作的队列。
通过限制某一端的插入和删除操作，又可以分为输出受限的的双端队列（允许在一端进行插入和删除，另一端只允许插入）和输入受限的双端队列（允许在一端进行插入和删除，另一端只允许删除）。
3.3 栈和队列的应用
3.3.1 栈在括号匹配中的应用
依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。当遇到左括号单身、右括号单身、左右括号不匹配三种情况时则匹配失败。
#define ElemType char
#define MaxSize 10
#include <iostream>
using namespace std;
typedef struct {
ElemType data[MaxSize];
int top;
} SqStack;
//初始化栈
void InitStack(SqStack &stack) {
stack.top = -1; //初始化栈顶指针，-1表示栈空
}
//判断一个栈是否为空
bool StackEmpty(SqStack stack) {
return stack.top == -1; //栈顶指针为-1时表示栈空
}
//进栈，将数据x存入到栈中
bool Push(SqStack &stack, ElemType x) {
if (stack.top == MaxSize - 1) {
return false; //栈已满
}
//先将top指针向上移动一位，然后将数据存入栈中
stack.data[++stack.top] = x;
return true;
}
//出栈，将出栈元素存入x中
bool Pop(SqStack &stack, ElemType &x) {
if (StackEmpty(stack)) {
return false; //栈空
}
//先出栈，再将栈顶指针top向下移动一位
x = stack.data[stack.top--];
return true;
}
bool bracketCheck(string str) {
SqStack stack;
InitStack(stack);
for (char c : str) {
if (c == '(' || c == '{' || c == '[') { //左括号进栈
Push(stack, c);
} else { //右括号
if (StackEmpty(stack)) { //栈空说明没有与右括号匹配的左括号，失败
return false;
} else {
char topEle;
Pop(stack, topEle);
//栈顶元素与当前扫描到的字符比较
if (c == ')' && topEle != '(') { //右括号与左括号不匹配，失败
return false;
} else if (c == ']' && topEle != '[') {
return false;
} else if (c == '}' && topEle != '{') {
return false;
}
}
}
}
return StackEmpty(stack);
}
3.3.2 栈在表达式求值中的应用
计算一个中缀表达式分为两步：
1. 中缀表达式转后缀表达式
//运算符优先级
private static final Map<Character, Integer> priority = new HashMap<>();
{
priority.put('+', 1);
priority.put('-', 1);
priority.put('*', 2);
priority.put('/', 2);
priority.put('(', 3);
priority.put(')', 3);
}
//中缀表达式转后缀表达式
private String infixToPostfix(String infix) {
StringBuilder postfix = new StringBuilder(); //后缀表达式
Stack<Character> operatorStack = new Stack<>(); //操作符栈
for (int i = 0; i < infix.length(); i++) {
char op = infix.charAt(i);
if (priority.get(op) == null) {
postfix.append(op); // map中没有，说明是操作数，加入后缀表达式
} else if (op == '(') { // 遇到左括号直接入栈
operatorStack.push(op);
} else if (op == ')') { //遇到 ) 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ( 为止
char top = operatorStack.pop();
while (top != '(') {
postfix.append(top);
top = operatorStack.pop();
}
} else { //遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(” 或栈空则停止
while (!operatorStack.empty() && operatorStack.peek() != '(') {
if (priority.get(operatorStack.peek()) >= priority.get(op)) {
postfix.append(operatorStack.pop());
} else { //栈顶操作符优先级低于当前运算符
break;
}
}
operatorStack.push(op);
}
}
//将栈中剩余运算符依次弹出，并加入后缀表达式
while (!operatorStack.empty()) {
postfix.append(operatorStack.pop());
}
return postfix.toString();
}
2.后缀表达式的计算
//计算后缀表达式
private int computerPostfix(String postfix) {
Stack<Integer> operandStack = new Stack<>();
for (int i = 0; i < postfix.length(); i++) {
char op = postfix.charAt(i);
if (priority.get(op) == null) { //遇到的是操作数，压入栈
operandStack.push(Integer.parseInt(String.valueOf(op)));
} else {
computer(operandStack, op);
}
}
return operandStack.pop();
}
//将操作数栈顶两个元素进行计算，并压入栈中
private void computer(Stack<Integer> operandStack, char op) {
int a = operandStack.pop();
int b = operandStack.pop();
int c = 0;
if (op == '+') {
c = b + a;
} else if (op == '-') {
c = b - a;
} else if (op == '*') {
c = b * a;
} else if (op == '/') {
c = b / a;
}
operandStack.push(c);
}
中缀表达式的计算代码实现
中缀表达式的计算就是中缀表达式转后缀表达式和后缀表达式的计算这二者的结合，下面是代码实现：
//运算符优先级
private static final Map<Character, Integer> priority = new HashMap<>();
{
priority.put('+', 1);
priority.put('-', 1);
priority.put('*', 2);
priority.put('/', 2);
}
//计算中缀表达式
private int computerInfix(String infix) {
Stack<Integer> operandStack = new Stack<>(); //操作符栈
Stack<Character> operatorStack = new Stack<>(); //操作数栈
for (int i = 0; i < infix.length(); i++) {
char op = infix.charAt(i);
if (priority.get(op) == null) { //map中没有，说明是操作数，压入栈中
operandStack.push(Integer.parseInt(String.valueOf(op)));
} else if (op == '(') { //左括号直接入栈
operatorStack.push(op);
} else if (op == ')') { //遇到 ) 则依次弹出栈内运算符并计算，直到弹出 ( 为止
char top = operatorStack.pop(); //栈顶运算符
while (top != '(') {
computer(operandStack, top);
top = operatorStack.pop();
}
} else { //遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并计算，若碰到“(” 或栈空则停止
while (!operatorStack.empty() && operatorStack.peek() != '(') {
if (priority.get(operatorStack.peek()) >= priority.get(op)) {
char top = operatorStack.pop();
computer(operandStack, top);
} else { //栈顶操作符优先级低于当前运算符
break;
}
}
operatorStack.push(op);
}
}
//取出剩余操作符进行计算
while (!operatorStack.empty()) {
char top = operatorStack.pop();
computer(operandStack, top);
}
return operandStack.pop();
}
//将操作数栈顶两个元素进行计算，并压入栈中
private void computer(Stack<Integer> operandStack, char op) {
int a = operandStack.pop();
int b = operandStack.pop();
int c = 0;
if (op == '+') {
c = b + a;
} else if (op == '-') {
c = b - a;
} else if (op == '*') {
c = b * a;
} else if (op == '/') {
c = b / a;
}
operandStack.push(c);
}