03. 栈和队列
栈
基础概念
| 定义 | 只能在表的一端进行插入和删除的线性表 |
|---|---|
| 逻辑结构 | 数据元素之间是一对一的关系 |
| 存储结构 | 顺序存储或链式存储 |
| 运算规则 | 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则 |
| 基本操作 | 建栈、判断栈满或栈空、入栈、出栈、取栈顶元素值 |
顺序栈
定义：利用一组地址连续的存储单元，依次存放从栈底到栈顶的数据元素。
注：顺序栈不仅需要判断下溢（栈空），还需要判断上溢（栈满）。
链式栈
定义：栈的链式存储结构，简称链栈；与单链表类似链表的尾部是栈底，链表的头部是栈顶。
栈的应用
运算符优先数法
问题：对算术表达式求值：1 + 2 * 4 - 9/3
解法
对每种运算符赋予一个优先数，如：
* / + - # 2 2 1 1 0 其中#是表达式结束符。
一般设两个栈：
- 运算符栈（OPTR）：存放运算符。
- 操作数栈（OPND）：存放操作数。
中缀表达式 a + b*c + (d * e + f) * g，其转换成后缀表达式则为 a b c * + d e * f + g * +。转换过程需要用到栈，具体过程如下：
1）如果遇到操作数，我们就直接将其输出。
2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
cpp
#include<iostream>
#include<stack>
#include<map>
using namespace std;
map<char, int> ranks = {{'#', 0},{'+', 2},{'-', 2},{'*', 3},{'/', 3},{'(', 1},{')', 1}};
void InfixToPostfix(char *infix, char *posfix){
char c;
stack<char> OPTR;//运算符栈
OPTR.push('#');//init_stack
for(int i = 0,j = 0; infix[i] != '\0'; i++){
c = infix[i];
if(c >= '0' && c <= '9'){
posfix[j++] = c;
}else{
int r = ranks[OPTR.top()];
while(ranks[c] <= r && ranks[c] != 1){//括号后面单独处理
if(r >= 2){//不加入其他字符
posfix[j++] = OPTR.top();
}
if(OPTR.empty()){
break;
}
OPTR.pop();
if(OPTR.empty()){
break;
}
r = ranks[OPTR.top()];
}
//如果是(,就直接加入，不用做任何处理
if(c == ')'){
char t = OPTR.top();
r = ranks[OPTR.top()];
while(t != '('){
if(r >= 2){//不加入其他字符
posfix[j++] = OPTR.top();
}
OPTR.pop();
t = OPTR.top();
r = ranks[OPTR.top()];
}
OPTR.pop();//弹出'('
}else{
OPTR.push(c);
}
}
}
}
void print_chars(char* chars){
cout << chars[0];
for(int i = 1; chars[i] != '\0'; i++){
cout << '!' << chars[i];
}
cout << endl;
}
int main(){
// char test1[10] = {'9','-','5','*','(','4','+','3',')','#'};
// char result1[50];
// InfixToPostfix(test1, result1);
// print_chars(result1);
/*output 9!5!4!3!+!*!- */
char test2[14] = {'2','*','(','3','+','4',')','/','(','1','+','1',')','#'};
char result2[50];
InfixToPostfix(test2, result2);
print_chars(result2);
/*output 2!3!4!+!*!1!1!+!/ */
return 0;
}地图四染色
栈的特性：
- 在某些问题的求解中常使用试探方法，当某一路径受阻时，需逆序退回，重新选择路径。
- 可利用栈记录曾到达的每一状态，栈顶状态即是回退的第一站。
问题：用不多于四种颜色对地图着色，使相邻地区不重色。
解法：
- 从 1 号地区开始逐一染色每一个地区逐次用色号 1、2、3、4 进行试探。
- 若当前所取的色号与周围已染色的地区不重色，则用栈记下该地区的色号，否则依次用下一色号进行试探。
- 若出现用 1~4 色均与相邻地区重色，则需退回，修改上一地区的色号：退栈回溯，修改当前栈顶的色号。
detail:
使用一个关系矩阵存储地区与地区之间是否相邻
伪代码：
python
for r in range(p): # p 为 1~7 的城市号
for ci in range(c): # c 为 1~4 的色号
for r in range(p): # 依次试探相邻城市是否染过颜色 ci
step:{是：回退；否：染色}
cpp
/**gb2312**/
#include<iostream>
#include<vector>
using namespace std;
//data
string name[34]={"广西","广东","云南","贵州","湖南","江西","福建",
"浙江","安徽","湖北","重庆","四川","西藏","青海",
"新疆","甘肃","陕西","宁夏","内蒙","北京","黑龙江",
"吉林","辽宁","天津","河北","山西","河南","江苏",
"山东","上海","海南","台湾","香港","澳门"};
int map[34][34]={省略} //二维关系矩阵
vector<int> find(int i){//找某一个城市与其他哪些城市有关系
vector<int> relationship;
for(int j = 0; j < i; j++){//这里 j<i 是因为只需要找前面涂过色的是否重复
if(map[i][j] == 1){
relationship.push_back(j);
}
}
return relationship;
}
void print_vec(vector<int> vec){
cout << "<";
for(int i = 0; i < vec.size(); i++){
cout << "{"<< name[i] << ": " << vec[i] << "}" << ", ";
}
cout << ">" << endl;
}
//非递归解法
void solution1(){
vector<int> color_stack;
vector<int> temp;
int i=0, c=0, k=0;//i 为所有城市，c 代表 4 种颜色
for(; i < 34; i++){//涂第 i 个城市
temp.clear();
temp = find(i);//temp 为与当前 i 有关系且已经涂过色的城市
for(;c < 4; c++){
int flag1 = 0;
if(!temp.empty()){
for(int m = 0; m < temp.size(); m++){
if(color_stack[temp[m]] == c){
flag1 = 1;//说明当前颜色不能用
}
}
}
if(flag1 == 0){//涂色
color_stack.push_back(c);
c = 0;
break;
}
}
while(c == 4){//没有颜色可用,向上判断一次
c = color_stack.back() + 1;
color_stack.pop_back();
temp.clear();
temp = find(color_stack.size());
while(c < 4){//遍历后面几种颜色进行涂色
int flag2 = 0;
if(!temp.empty()){
for(int m = 0; m < temp.size(); m++){
if(color_stack[temp[m]] == c){
flag2 = 1;//说明当前颜色不能用
}
}
}
if(flag2 == 0){//涂色
color_stack.push_back(c);
c = 0;
break;
}
c++;
}
}
}
print_vec(color_stack);
/*<{广西: 0}, {广东: 1}, {云南: 1}, {贵州: 2}, {湖南: 3},
{江西: 0}, {福建: 2}, {浙江: 1}, {安徽: 2}, {湖北: 1},
{重庆: 0}, {四川: 3}, {西藏: 0}, {青海: 1}, {新疆: 2},
{甘肃: 0}, {陕西: 2}, {宁夏: 1}, {内蒙: 3}, {北京: 0},
{黑龙江: 0}, {吉林: 1}, {辽宁: 0}, {天津: 1}, {河北: 2},
{山西: 0}, {河南: 3}, {江苏: 0}, {山东: 1}, {上海: 2},
{海南: 0}, {台湾: 0}, {香港: 0}, {澳门: 0}, >
*/
}
// 递归解法
int isOk(int metrix[34][34],int city[34],int current){
for(int j=0; j<current; j++)
if(metrix[current][j]==1&&city[j]==city[current])
//他们之间是相邻且涂的是同一种颜色
return 0;
return 1;
}
void color(int metrix[34][34],int city[34],int sum,int current)
{
if(current<=sum){
for(int i=0; i<4; i++) //colored current city
{
city[current]=i;
if(isOk(metrix,city,current))
{
color(metrix,city,sum,current+1); //colored next city
break;
}
}//注意这个循环和递归的结合，挺巧妙的。
}
}
int main (){
//solution1:
cout << "****************1***************" << endl;
solution1();
//solution2:
int city[34] = {};
color(map,city,34,0);
//print
cout << "****************2***************" << endl;
cout << "<";
for(int i = 0; i < 34; i++){
cout << "{"<< name[i] << ": " << city[i] << "}" << ", ";
}
cout << ">" << endl;
//结果一致
// for(int i = 0; i < 34; i++){
// cout << city[i] << ", ";
// }
//color = [0, 1, 1, 2, 3, 0, 2, 1, 2, 1, 0, 3, 0, 1, 2, 0, 2, 1, 3, 0, 0, 1, 0, 1, 2, 0, 3, 0, 1, 2, 0, 0, 0, 0]
return 0;
}
函数调用
- 栈是存储器的一个区域。
- 一般使用栈实现函数调用。
- 函数占用的区域被称作函数的栈帧。
- 函数调用时，为被调用的函数分配栈帧，存放函数创建的局部（临时）变量等信息。
- 函数嵌套调用时，堆栈中会同时存在多个函数的栈帧。
递归
定义：若一个过程直接地或间接地调用自己，则称这个过程是递归的。
分类：直接递归与间接递归。
条件：
解决问题时，可把一个问题转化为一个新的问题。
这个新问题的解法与原问题的解法相同，只是所处理的对象不同。
必须有结束递归的条件，否则递归将无休止地进行，导致耗尽系统资源。
数据结构是递归的，如二叉树。
问题的解法是递归的，如汉诺塔、地图四染色、走迷宫等。
大问题转换为几个小问题，小问题进一步分解为更小的小问题，直到递归出口为止。
递归模型由递归出口和递归体两部分组成，前者确定递归合适为止，后者确定递归的方式。
递归算法的非递归描述：考虑到**栈帧的模型（系统栈的调用）**就很好理解。
cpp
\********递归解法********\
int fac(int n){
if(n == 1)
return 1;
else
return n*fac(n-1);
}
int main(){
fac(4)
return 0;
}cpp
\*******非递归解法*******\
int fac(int n){
int s = 1;
while(n >= 1)
push(stack, p--);
while(!empty(stack))
s *= pop(stack);
return s;
}
int main(){
fac(4);
return 0;
}两种解法的时间复杂度与空间复杂度都是一样的。
队列
基础概念
| 队列定义 | 只能在表的一端进行插入，在表的另一端进行删除的线性表 |
|---|---|
| 逻辑结构 | 元素之间是一对一的关系 |
| 存储结构 | 顺序队列和链队列 |
| 运算规则 | 队尾入队、队头出队、遵循先进先出（FIFO）的原则 |
| 基本操作 | 入队、出队、建空队列、判队空或对满 |
顺序队列
队列的顺序存储，称为顺序队列。由存放元素的顺序表、队头指针、队尾指针三部分组成。
顺序存储的两个问题：
普通队列出现的假上溢的问题：使用循环队列解决：
把队列设想为环形（若 rear+1 == M, 则令 rear=0）
实现：利用模运算
入队：rear = (rear + 1)%M; sq[rear] = x;
出队： front = (front + 1)%M; x = sq[front];
队空与队满的判定条件相同：少用一个元素空间
- 队空：front == rear
- 队满：（rear + 1）%M == front
初始化：
cpp
cquenetp *initquene(){
cquenetp *q;
q = new cquenetp;
//将队列头尾指针置为 0
q->front = q->rear = 0;
return q;
}入队：
cpp
if((q->rear+1)%M == q->front){ //判队满
q->rear = (q->rear+1)%M; //入队
q->v[q->rear] = x;
return true;
}else{
return false;
}出队：
cpp
if(q->front == q->rear){ //判队空
q->front= (q->front + 1)%M; //出队
x = q->v[q->front];
return x
}else{
return false;
}链队列
- 头指针（front）指向队头结点。
- 尾指针（rear）指向队尾结点。
- 注意是删头加尾，因为删除链表的一个结点需要知道它的前趋结点。
- 链为空的条件是 front == rear, 原则上来说链队列是不需要判满的。
初始化：
cpp
linkquene *initquene(){
linkquene *q;//链队列指针，封装了队头队尾指针
QUENE *p;//p 为指向链队列结点的指针
q = new linkquene;
p = new QUENE;//生成头结点
p->next = NULL;//头节点指针域为空，空队列
q->front = q->rear = p;//队头队尾指针都指向头结点
return q;
}入队：
cpp
void enquene(linkquene *q, datatype x){
QUENE *p; //p 为指向链队列结点的指针
p = new QUENE;
p->data = x;
p->next = NULL;
q->rear->next = p;
q->rear= p;
}出队：
cpp
datatype dequene(linkquene *q){
QUENE *p; //p 为指向链队列结点的指针
datattype x;
if(q->front == q->rear){
return false;
}else{
p = q->front->next;//p 指向队列头
x = p->data;//将队头元素的值赋给 x
q->front->next = p->next;//出队
//若出队列后队列为空，则修改队尾指针
if(p->next == null)
q->rear = q->front;
delete(p);
return x;
}
}队列的应用（子集划分问题）
运动会设立了 n 个比赛项目，没饿过运动员可以参加 1~3 个项目。请问应该如何安排比赛日程？从而使同一运动员参加的项目不能在同一时间进行，并使总的竞赛日程最短。
解决方法概述：
将集合 A 中的所有元素放入一个队列中，然后依次取出队头元素 a_i 放入一个待分配的组 gm 中，若 a_i 与组 gm 中的其他元素无冲突，则加入组 gm，如产生冲突，则将重新入队；当遍历考察一轮队列中的所有元素后，产生一个无冲突的子集 gm，如此循环，直到所有元素都被分配完成。
细节：
- 同样使用关系矩阵存放冲突关系
- 使用**newrela[]**存放与当前子集的元素冲突的关系元素==>存一个元素到该子集就将该元素所有有冲突关系的元素在 newrela[]中标为 1，如此累积，直到这次循环结束，newrela[]清空。
- 是将 A 中元素的编号（1，2，3······，n）入队到 cq 中，reault[]，newrela[]清空，组号 group=1，pre=1。
- 出队一个元素->i，pre = i，result[i] = group,判断冲突。
- 如果 i<pre，则第一个分组完成，开始 group=2。
准备
cpp
#include<iostream>
#include<vector>
#include<stdexcept>
//关系矩阵，不过这里是人工手动建的，其中第一排与第一列不参与
int matrix[10][10] = {
{0,1,2,3,4,5,6,7,8,9},//0
{1,0,1,0,0,0,0,0,0,0},//1
{2,1,0,0,0,1,1,0,1,1},//2
{3,0,0,0,0,0,1,1,0,0},//3
{4,0,0,0,0,1,0,0,0,1},//4
{5,0,1,0,1,0,1,1,0,1},//5
{6,0,1,1,0,1,0,1,0,0},//6
{7,0,0,1,0,1,1,0,0,0},//7
{8,0,1,0,0,0,0,0,0,0},//8
{9,0,1,0,1,1,0,0,0,0},//9
};
int newrela[10] = {0,0,0,0,0,0,0,0,0,0,};
using namespace std;顺序存储实现队列
cpp
class my_quene{
int nums[10];
int front = 0;
int rear = 0;
public:
my_quene(){
}
~my_quene(){
}
void enquene(int x){
if((this->rear+1)%10 == this->front){
throw std::out_of_range( "duiman~" );
}
this->rear = (++this->rear)%10;
this->nums[this->rear] = x;
return;
}
int dequene(){
if(this->front == this->rear){
throw std::out_of_range( "duikong~" );
}
this->front = (++this->front)%10;
int x = this->nums[this->front];
return x;
}
int empty(){
if(this->front == this->rear){
return 1;
}
else{
return 0;
}
}
//为该题单独封装的一个方法
//判断一次是否遍历完了
int over(){
//这里后面还要出队入队才算结束
if(this->nums[(this->front + 1)%10] < this->nums[this->rear]){
return 1;
}
return 0;
}
};链式存储实现队列
cpp
struct qnode
{
int key;
qnode* next;
qnode(int x) :
key(x), next(NULL) {
}
};
class my_quene{
qnode* front = NULL;
//front 相当于头节点
qnode* rear = NULL;
public:
my_quene(){
front = new qnode(-1);
rear = front;
}
~my_quene(){
delete(front);
}
void enquene(int x){
qnode* temp = new qnode(x);
rear->next = temp;
rear = rear->next;
}
int dequene(){
if(this->empty()){
throw std::out_of_range("quene_empty!");
}
qnode* temp = front->next;
//这里最后一个节点删除的时候需要手动移动 rear 指针；
if(temp->next == NULL){
rear = front;
}
front->next = temp->next;
int x = temp->key;
delete(temp);
return x;
}
int empty(){
if(rear == front){
return 1;
}
return 0;
}
int over(){
if(this->empty()){
return 2;
}
if(front->next == NULL){
return 0;
}
if(front->next->key < rear->key){
return 1;
}
return 0;
}
};测试
cpp
void test_my_quene(){
my_quene test;
for(int i = 0; i < 4; i++){
test.enquene(i);
}
for(int i = 0; i < 4; i++){
int temp = test.dequene();
cout << temp << ", ";
}
cout << endl;
}添加冲突
cpp
int add_rela(int i){
//如果和当前组冲突，就返回 0
if(newrela[i] == 1){
return 0;
}
//不冲突就增加当前会冲突的，返回 1
for(int j = 1; j < 10; j++){
if(matrix[i][j] == 1){
newrela[j] = 1;
}
}
return 1;
}主函数
cpp
int main(){
//test_my_quene();
vector<vector<int>> groups;
vector<int> group;
//init_quene
my_quene match;
for(int i = 0; i < 9; i++){
match.enquene(i+1);
}
int temp = 0;
int flag = 1;
int flag_1 = 0;
while(!match.empty()){
while(1){
if(match.empty()){
break;
}
if(match.over()){//标志着一轮结束了，下一步就是这个
if(flag){//说明是开始就不跳出
flag = 0;//下一次是结束
}else if(flag_1){
flag = 1;//下一次是开始
flag_1 = 0;
break;
}
}
temp = match.dequene();
if(add_rela(temp)){
group.push_back(temp);
}else{
match.enquene(temp);
flag_1 = 1;
}
}
//清空关系
for(int i = 0; i < 10; i++){
newrela[i] = 0;
}
if(match.empty()){
break;
}
groups.push_back(group);
group.clear();
}
//展示
for(int i = 0; i < groups.size(); i++){
cout << "{";
for(int j = 0; j < groups[i].size(); j++){
cout << groups[i][j] << ", ";
}
cout << "}, ";
}
cout << endl;
return 0;
}