数据结构详细笔记——栈与队列

---

栈的三要素

逻辑结构（定义）

栈是只允许在一端进行插入或删除操作的线性表

特点：后进先出（LIFO）

数据的运算（基本操作）

InitStack(&S)
初始化栈：构造一个空栈S，分配内存空间

DestroyStack(&S)
销毁栈：销毁并释放栈S所占用的内存空间

Push(&S,x)
进栈：若栈S未满，则将x加入使之成为新栈顶

Pop(&S,&x)
出栈：若栈非空，则弹出栈顶元素，并用x返回

GetTop(S,&x)
读栈顶元素：若栈S非空，则用x返回栈顶元素

StackEmpty(S)
判断一个栈S是否为空，若S为空，则返回true，否则返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

栈的常考题型
已知进栈顺序，问有哪些合法的出栈顺序？
出栈元素不同排列的个数为

存储结构（物理结构）

顺序栈（顺序存储）

顺序栈的定义

#define MaxSize 10
typedef struct{
	ELemType data[MaxSize];   // 静态数组存放栈中元素
	int top;                  // 栈顶指针
}SqStack;
1
2
3
4
5

初始化栈

void InitStack(SqStack &S){
	S.top = 0;
}
1
2
3

判空

bool StackEmpty(SqStack S){
	if(S.top == -1)
		return true;
	else
		return false;
]
1
2
3
4
5
6

进栈操作

bool Push(SqStack &S,ElemType x){
	if(S.top == MaxSize - 1)
		renturn false;
	S.top = S.top + 1;   // 指针先加1
	S.data[S.top] = x;   // 新元素入栈
	return true;
}
1
2
3
4
5
6
7

出栈操作

bool Pop(SqStack &S, ElemType &x){
	if(S.top == -1)
		return false;
	x = S.data[S.top];
	S.top = S.top - 1;
	return true;
}
1
2
3
4
5
6
7

读栈顶元素

bool GetTop(SqStack S, ElemType &x){
	if(S.top == -1)
		return false;
	x = S.data[S.top];
	return true;
|
1
2
3
4
5
6

共享栈

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int top0;      // 0号栈栈顶指针
	int top1;      // 1号栈栈顶指针
} ShStack;

// 初始化栈
void InitStack(ShStack &S){
	S.top0 = -1;
	S.top1 = MaxSize;
}
1
2
3
4
5
6
7
8
9
10
11
12

栈满的条件: top0 + 1 = top1

链栈（链式存储）

链栈的定义
其操作相当于头插法建立单链表（只从表头进行增加删除操作）

typedef struct LinkNode{
	ELemType data;   // 数据域
	struct LinkNode *next;     // 指针域
}*LinkStack;
1
2
3
4

队列的三要素

逻辑结构（定义）

队列是只允许在一端进行插入，在另一端删除的线性表

特点：先进先出（FIFO）

数据的运算（基本操作）

InitQueue(&Q)
初始化队列：构造一个空队列Q

DestroyQueue(&Q)
销毁队列：销毁并释队列Q所占用的内存空间

EnQueue(&Q,x)
入队：若队列Q未满，则将x加入使之成为新的队尾

DeQueue(&Q,&x)
出队：若队列非空，删除队头元素，并用x返回

GetHead(Q,&x)
读队头元素：若队列Q非空，则用x返回队头元素

QueueEmpty(Q)
判断一个队列Q是否为空，若Q为空，则返回true，否则返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

存储结构（物理结构）

顺序队列（顺序存储）

队列的顺序实现

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
} SqQueue;
1
2
3
4
5

初始化队列

void InitQueue(SqQueue &Q){
	Q.rear = Q.front = 0;
}
1
2
3

判断队列是否为空

bool QueueEmpty(SqQueue Q){
	if(Q.rear == Qfront)
		return true;
	else
		return false;
}
1
2
3
4
5
6

入队

bool EnQueue(SqQueue &Q,ElemType x){
	if((Q.rear + 1) % MaxSize == Q.front)
		return false;    //队满则报错
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;  //队尾指针加一取模
	return true;
} 
1
2
3
4
5
6
7

出队

bool DeQueue(SqQueue &Q,ElemType &x){
	if(Q.rear == Q.front)
		return false;   // 队空则报错
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	return true;
}
1
2
3
4
5
6
7

获取队头元素的值，用x返回

bool GetHead(SqQueue Q,ElemType &x){
	if(Q.rear == Q.front)
		return false;
	x = Q.data[Q.front];
	return true;
}
1
2
3
4
5
6

队列元素的个数：
（rear - front + MaxSzie）% MaxSize

链式队列（链式存储）

队列的链式实现

typedef struct LinkNode{    // 链式队列结点
	ElemType data;  
	struct LinkNode *next;
}LinkNode;

typedef struct{             // 链式队列
	LinkNode *front,*rear;  // 队列的队头和队尾指针
}LinkQueue;
1
2
3
4
5
6
7
8

初始化（带头结点）

void InitQueue(LinkQueue &Q){
	// 初始化 front、rear 都指向头结点
	Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}
1
2
3
4
5

队列是否为空

bool IsEmpty(LinkQueue Q){
	if(Q.rear == Qfront)
		return true;
	else
		return false;
}
1
2
3
4
5
6

新元素入队（带头结点）

void EnQueue(LinkNode &Q,ElemType x){
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = null;
	Q.rear->next = s;
	Q.rear = s;
}
1
2
3
4
5
6
7

入队（不带头结点）

void EnQueue(LinkQueue &Q,ElemType x){
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if(Q.front == NULL){   // 在空队列中插入第一个元素
		Q.front = s;       // 修改队头队尾的指针
		Q.rear = s;
	} else{
		Q.rear->next = s;
		Q.rear = s;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

出队（带头结点）

bool DeQueue(LinkQueue &Q,ElemType &x){
	if(Q.front == Q.rear)
		return false;    // 空队
	LinkNode *p = Q.front->next;
	x = p.data;
	Q.front->next = p->next;
	if(Q.rear == p)   // 此次是最后一个结点出队
		Q.rear = Q.front;
	free(p);          // 释放结点空间
	return true;
}
1
2
3
4
5
6
7
8
9
10
11

出队（不带头结点）

bool DeQueue(LinkQueue &Q,ElemType &x){
	if(Q.front == NULL)
		return false;
	LinkNode *p = Q.front;
	x = p->data;
	Q.front = p->next;
	if(Q.rear = p)[
		Q.front = NULL;
		Q.rear = NULL;
	}
	free(p);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

队列的变种

双端队列：允许从两端插入、两端删除的队列

输入受限的双端队列：允许从两端删除、从一端插入的队列

输出受限的双端队列：允许从两端插入、从一端删除的队列

考点：对输出序列的合法性的判断

栈在括号匹配中的应用

代码实现

#define MaxSize 10
typedef struct{
	char data[MaxSize];
	int top;
}SqStack;

// 初始化栈
void InitStack(SqStack &S)

// 判断栈是否为空
bool StackEmpty(SqStack S)

// 新元素入栈
bool Push(SqStack &S,char x)

// 栈顶元素出栈，用x返回
bool Pop(SqStack &S,char &x)

bool bracketCheck(char str[],int length){
	SqStack S;
	InitStack(S);  // 初始化
	for(int i = 0; i < length; i++){
		if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
			Push(S, str[i]);  // 扫描到左括号，入栈
		} else {
			if(StackEmpty(S))  // 扫描到右括号，并且当前栈空
				return false;  // 匹配失败
			char topElem;
			Pop(S, topElem);   // 栈顶元素出栈
			if(str[i] == ')' && topElem != '(')
				return false;
			if(str[i] == ']' && topElem != '[')
				return false;
			if(str[i] == '}' && topElem != '{')
				return false;
		}
	}
	return StackEmpty(S);   // 检索完全部括号后，栈空说明匹配成功
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

栈在表达式求值中的应用

三种算术表达式：
1、中缀表达式：运算符在两个操作数中间 —— a+b
2、后缀表达式（逆波兰表达式）：运算符在两个操作数后面 —— ab+
3、前缀表达式（波兰表达式）：运算符在两个操作数前面 —— +ab

中缀表达式 ------>后缀表达式

手算

1、确定中缀表达式中各个运算符的运算顺序
2、选择下一个运算符，按照【 左操作符 右操作符 运算符 】的方式组合成一个新的操作数
3、如果还有运算符没被处理，就继续2
注意：为了保证手算和机算结果相同，采用“左优先”原则：只有左边的运算符能先运算，就优先算左边（可保证运算顺序唯一）

机算

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符
从左到右处理各个元素，直到末尾，可能遇到三种情况：
1、遇到操作数：直接加入后缀表达式
2、遇到界限符：遇到 “ ( ” 直接入栈，遇到 “ ) ” 则依次弹出栈内运算符并加入后缀表达式，直到弹出 “ ( ” 为止。注意：“ ( ” 不加入后缀表达式
3、遇到运算符：依次弹出栈中优先级高于或者等于当前运算符的所有运算符，并加入后缀表达式，若碰到 “ ( ” 或栈空则停止。之后再把当前的运算符入栈
4、处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式

后缀表达式的计算

1、从左往右扫描下一个元素，直到处理完所有的元素
2、若扫描到操作数则压入栈，并回到1；否则执行3
3、若扫描到运算符，则弹出两个栈顶元素，执行相应运算（先出栈的是右操作数），运算结果压回栈顶，回到1
4、若表达式合法。则最后栈中只会留下一个元素，就是最终结果

中缀表达式 ------>前缀表达式

1、确定中缀表达式中各个运算符的运算顺序
2、选择下一个运算符，按照【 运算符 左操作符 右操作符 】的方式组合成一个新的操作数
3、如果还有运算符没被处理，就继续2
注意：为了保证手算和机算结果相同，采用“右优先”原则：只有右边的运算符能先运算，就优先算右边（可保证运算顺序唯一）

前缀表达式的计算

1、从右往左扫描下一个元素，直到处理完所有的元素
2、若扫描到操作数则压入栈，并回到1；否则执行3
3、若扫描到运算符，则弹出两个栈顶元素，执行相应运算（先出栈的是左操作数），运算结果压回栈顶，回到1
4、若表达式合法。则最后栈中只会留下一个元素，就是最终结果

用栈实现中缀表达式的计算

中缀表达式 ------>后缀表达式 与 后缀表达式的计算 的结合

*初始化两个栈：操作数栈 和 运算符栈
若扫描到操作数，压入操作数栈
若扫描到运算符或者界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈
每当弹出一个运算符时，就需要在弹出两个操作数栈的栈顶元素并执行相应的运算，运算结果再压回操作数栈中