数据结构之栈与队列

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 11k 阅读时长 ≈ 10 分钟

第三章栈与队列

第三节堆栈和队列的应用

1.表达式求值

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<iostream>
#define OK 1
#define ERROR 0
using namespace std;
typedef char SElemType;
typedef int Status;
//链栈存储结构
typedef struct Node {
    SElemType data;
    struct Node* next;
}Node, * LinkStack;

//链栈初始化
Status InitStack(LinkStack &S) {   //构造空栈，栈顶指针置空
    S = NULL;
    return OK;
}

//链栈入栈
Status Push(LinkStack &S, SElemType e) {//栈顶插入元素e
    LinkStack p = new Node;    //生成新节点
    p->data = e;   //新节点数据域置为e
    p->next = S;   //将新节点插入栈顶
    S = p; //修改栈顶指针为p
    return OK;
}

//链栈的出栈
Status Pop(LinkStack &S, SElemType &e) {
    if (S == NULL) //栈为空
        return ERROR;
    LinkStack p;   //定义临时链栈
    e = S->data;   //将栈顶元素赋值给e
    p = S; //临时存储栈顶空间，以备释放
    S = S->next;   //修改栈顶指针
    delete p;  //删除栈顶指针
    return OK;
}

//取栈顶元素
SElemType GetTop(LinkStack S) {
    if (S != NULL) //栈非空
        return S->data;
}

//判断读入的字符ch是否为运算符
Status In(SElemType ch) {
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')'||ch=='#')
        return OK;
    else
        return ERROR;
}

//判断运算符栈顶元素与读入运算符ch的优先级
SElemType Precede(SElemType a, SElemType b) {
    if (a == '+' || a == '-') {
        if (b == '+' || b == '-' || b == '#' || b == ')')
            return '>';
        else
            return '<';
    }
    if (a == '*' || a == '/') {
        if (b == '(')
            return '<';
        else
            return '>';
    }
    if (a == '(') {
        if (b == ')')
            return '=';
        else
            return '<';
    }
    if (a == '#') {
        if (b == '#')
            return '=';
        else
            return '<';
    }
    if (a == ')')
        return '>';
}

//运算函数
SElemType Operate(SElemType a, SElemType t, SElemType b) {//进行运算的函数
    switch (t) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
    }
}

//算法表达式求值的优先算法，设OPTR和OPND分别为运算符栈和操作数栈
void EvaluateExpression() {
    LinkStack OPND, OPTR;  //定义栈
    SElemType ch, t,t1,t2;
    InitStack(OPND);   //初始化操作数栈
    InitStack(OPTR);   //初始化运算符栈
    Push(OPTR,'#');    //入栈
    cin >> ch;
    while (ch != '#' || GetTop(OPTR) != '#') {//表达式没有扫描完毕或者OPTR栈顶不为‘#’时执行
        if (!In(ch)) { //ch不是运算符
            Push(OPND, ch-'0');    //进入OPND栈
            cin >> ch; //读取下一个字符
        }
        else
            switch (Precede(GetTop(OPTR), ch)) {   //比较OPTR栈顶元素和ch的优先级
                case '<':
                    Push(OPTR, ch);    //将ch压入OPTR栈
                    cin >> ch; //读取下一个字符
                    break;
                case '>':
                    Pop(OPTR, t);  //弹出OPTR栈顶运算符，赋值给t
                    Pop(OPND, t2); //后进先出
                    Pop(OPND, t1); //弹出OPND栈顶两个运算数
                    Push(OPND, Operate(t1, t, t2));    //将运算结果压入OPND栈
                    break;
                case '=':  //OPTR栈顶元素是'('且ch是')'
                    Pop(OPTR, t);  //弹出栈顶'('
                    cin >> ch; //读取下一个字符
                    break;
            }
    }
    cout<<(int)GetTop(OPND)<<endl; //将char转换为int
}

int main() {
    EvaluateExpression();
    return 0;
}

2.括号匹配问题

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<string.h>
using namespace std;

//定义栈
#define max_size 200//栈的最大容量
typedef char datatype;
typedef struct{
    datatype zhan[max_size];
    int top;//栈顶
}stack;

//栈的初始化
void initial(stack &st)
{
    st.top = 0;
}

//类型为datatype的x入栈
void push(stack &st, datatype x)
{
    //当栈顶和max_size相等时，栈满
    if(st.top == max_size){
        // cout<<"This stack has already full!";
        cout<<"no";
        exit(0);
    }else{
        st.zhan[st.top] = x;
        st.top++;
    }
}

//出栈
char pop(stack &st){
    if(st.top == 0){
        // cout<<"This stack is empty!";
        cout<<"no";
        exit(0);
    }else{
        st.top--;
        return st.zhan[st.top];
    }
}

int main(){
    stack s;
    initial(s);
    /*输入字符串，并将字符串放到字符数组中，
    实现能够逐个扫描字符串中的字符，并且不跳过空格符*/
    string str;
    getline(cin, str);
    char ch[200]={'\0'};
    strcpy(ch,str.c_str());
    //flag标志状态 1为括号匹配，0为不匹配
    int flag=1;
    int i;
    for(i=0; ch[i]!='\0'; i++){
        //元素若为{，(，[则入栈
        if((ch[i] == '{' )|| (ch[i] =='[') || (ch[i] =='(')){
            push(s, ch[i]);
        }//元素若为}，)，]则出栈 赋值给a
        else if((ch[i] == '}') || (ch[i] ==']') || (ch[i] ==')')){
            char a;
            a = pop(s);
            //若a与ch[i]匹配，进行下一个字符扫描
            if((a == '{' && ch[i] == '}') || (a == '(' && ch[i] == ')') || (a == '[' && ch[i] == ']')){
                continue;
            }else flag = 0;
        }
    }

    if(s.top != 0){    //当左括号多出没有与右括号匹配的时候（如：" {() "）
        flag = 0;
    }

    if(flag == 0){
        cout<<"no";
    }
    else 
        cout<<"yes";
    return 0;
}

3.迷宫问题（栈，深度检索）

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;


#define ROW  6//行
#define COL  6//列

//地图
typedef struct _Maze
{
    int map[ROW][COL];
}Maze;

#define MAX_SIZE 128

typedef struct _Postion//地图中点的坐标,这个栈中存的元素就是点的坐标
{
    int _x;
    int _y;
}Postion;

typedef Postion DataType;

//栈的结构体
typedef struct _Stack
{
    DataType* top;
    DataType* base;
}Stack;

//栈的初始化
bool initStack(Stack& S)
{
    S.base = new DataType[MAX_SIZE];
    if (!S.base)
        return false;
    S.top = S.base;
    return true;
}

//入栈
bool pushStack(Stack& S, DataType data)
{
    if (!S.base)
        return false;
    if (S.top - S.base == MAX_SIZE)
        return false;
    *(S.top) = data;
    S.top++;
    return true;
}

//出栈
bool popStack(Stack& S,DataType& e)
{
    if (S.top == S.base)
        return false;
    e = *(--S.top);
    return true;
}

//返回栈顶元素
DataType* getTop(Stack& S)
{
    if (S.top - S.base == 0)
        return NULL;
    //注意何时自增何时不自增
    return S.top-1;//返回栈顶元素的指针
}

//返回栈中元素个数
int getSize(Stack& S)
{
    return S.top - S.base;
}

//判断栈是否为空
bool isEmpty(Stack& S)
{
    if (S.top == S.base)
        return true;
    else
        return false;

}

//销毁栈
void destoryStack(Stack& S)
{
    if (S.base)
    {
        delete[] S.base;
        S.top = S.base = NULL;
    }
}
//根据给出给出的地图数据初始化结构体地图
void initMaze(Maze& m, int map[ROW][COL])
{
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            m.map[i][j] = map[i][j];
}

//打印迷宫(地图)
void printMaze(Maze& m)
{
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            cout << m.map[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

//判断是否是有效的入口
bool isValidEnter(Maze* m,Postion enter)
{
    assert(m);//断言-里面的表达式为0直接终止程序,注意里面的内容是什么
    //只要入口在四个边界上就是合法的,并且是1(道路)
    if (((enter._x == 0 || enter._x == ROW - 1) || (enter._y == 0 || enter._y == COL - 1)))
        return true;
    return false;
}

//判断当前位置是否是出口
bool isVaildExit(Maze* m, Postion cur, Postion enter)
{
    assert(m);
    //该结点不能是入口点，除了入口点，在边界上就是合法出口

    if ((cur._x != enter._x || cur._y != enter._y) && ((cur._x == 0 || cur._x == ROW - 1) || (cur._y == 0 || cur._y == COL - 1)))
        return true;
    else
        return false;
}

//判断当前结点的下一个结点是否能走通-是不是可以走的点
bool isNextPass(Maze* m, Postion cur, Postion next)
{
    assert(m);
    //判断next是不是cur的下一个结点
    //同一行相邻或者同一列相邻
    if (((next._x == cur._x) && ((next._y == cur._y + 1) || (next._y == cur._y - 1)))
        || ((next._y == cur._y) && ((next._x = cur._x + 1) || (next._x = cur._x - 1))))
        //确实是cur的下一个结点(相邻的 )
        //判断这个点是不是在迷宫里
        //合法坐标并且那个位置的值是1
        if (((next._x >= 0 && next._x < ROW) && (next._y >= 0 && next._y < COL))
            && (m->map[next._x][next._y] == 1))
            //最后的参数==1，不仅仅是看是否是可以走的位置(道路是1)，
            //同时有了这个我们就不用倒着往往前走了(不走重复的路)，不是有效的结点不只是墙(0)
            //走过的也不是有效结点，直接pop出栈，通过出栈来往前回退
            return true;
    return false;
}

//寻找迷宫通路
bool PassMaze(Maze* m, Postion enter, Stack& s)
{
    assert(m && isValidEnter(m, enter));

    Postion cur = enter;//cur存储当前结点
    Postion next;//下一个结点，从入口开始出发向四周移动

    //先将入口压入栈中
    pushStack(s, cur);
    m->map[cur._x][cur._y] = 2;//将入口值改为2

    //循环求解-当栈中还有路径时
    while (!isEmpty(s))
    {
        cur = *getTop(s);//取到栈顶元素
        //判断当前位置是否是出口
        if (isVaildExit(m, cur, enter))//注意参数传递顺序
            return true;//是出口直接返回

        //不是出口继续在周围判断
        //把cur当前刚才那个位置拿过来向四周判断

        //先向左判断
        next = cur;
        next._y = cur._y - 1;
        if (isNextPass(m,cur,next))//如果下一个结点走得通
        {
            //走得通就走到那个位置-压进栈
            pushStack(s, next);
            //走过的位置-标记
            m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;

            //之后
            continue;
        }
        //走不通向另一个方向判断
        //向右走一步
        next = cur;
        next._y = cur._y + 1;
        if (isNextPass(m, cur, next))
        {
            pushStack(s, next);
            m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
            continue;
        }

        //向下走一步
        next = cur;
        next._x = cur._x + 1;
        if (isNextPass(m, cur, next))
        {
            pushStack(s, next);
            m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
            continue;
        }

        //向上走一步
        next = cur;
        next._x = cur._x - 1;
        if (isNextPass(m, cur, next))
        {
            pushStack(s, next);
            m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1;
            continue;
        }

        //走到这里说明此结点的四个方向都走不通
        //进行回溯
        Postion tmp;//没用 临时接收
        popStack(s, tmp);//出栈

    }
    return false;
}

int main(void)
{
    //0-墙 1-路
    int map[ROW][COL] = {
            0,0,1,0,0,0,
            0,0,1,1,1,0,
            0,0,1,0,0,0,
            1,1,1,1,1,0,
            0,0,1,0,1,0,
            0,0,0,0,0,0
    };


    Maze m;//创建一个迷宫(地图)
    initMaze(m, map);//初始化迷宫
    printMaze(m);//打印迷宫

    cout << "_______" << endl;

    //迷宫入口
    Postion enter;
    enter._x = 0;
    enter._y = 2;

    //定义栈
    Stack s;//用于保存走过的轨迹，便于回溯
    initStack(s);//初始化栈

    int ret = PassMaze(&m, enter, s);
    if (ret)
        cout << "有解" << endl;
    else
        cout << "无解" << endl;
    printMaze(m);
    return 0;
}

4.调度问题

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<stdio.h>
const int INF=1000;
const int max_task=10;            	//最大任务数
int n;                           	//任务数
int a[max_task][2];             	//存储每个作业分别在机器1与机器2上的时间消耗
int result[max_task];          		//存储排列树中的一条路径
int best_result[max_task];    		//存储最优路径
int min=INF;                 		//安排任务最小完成时间
int rop[max_task+1];        		//每个深度对应遍历进度
int finish[max_task+1];    			//每一层消耗时间和
void swap(int result[max_task],int best_result[max_task])   //复制数组
{
    for(int i=0;i<n;i++)
        best_result[i]=result[i];
}
void allot_task(int depth)
{
    static bool visited[max_task];    	//标记已安排任务
    for(int i=rop[depth];i<n;i++)
    {
        if(!visited[i])                 //寻找该层未访问节点
        {
            int f1=0;                 	//在机器一上的完成时间
            int f2=0;                  	//在机器二上的完成时间
            rop[depth]=i+1;           	//更新该层访问进度
            visited[i]=true;         	//标记作业
            result[depth-1]=i;        	//加入结果序列
            for(int j=0;j<n;j++)
            {
                if(visited[j])
                {
                    f1+=a[j][0];
                }
            }
            f2=f1+a[i][1];            	//该作业完成时间
            if(f2<finish[depth-1])    	//该序列执行到此作业消耗时间
                f2=finish[depth-1];
            finish[depth]=f2;
            if(depth==n)             	//最后一个作业
            {
                if(f2<min)
                {
                    min=f2;
                    swap(result,best_result);      //保存最优序列
                }
                visited[i]=false;
                rop[depth]=0;
                return;
            }
            else if(depth<n)
            {
                if(f2>min)
                {
                    visited[i]=false;
                    allot_task(depth-1);     //回溯
                }
                else
                {
                    allot_task(depth+1);      //继续添加作业
                }

            }
        }
        visited[rop[depth]-1]=false;         //跟换当前层次作业需要把之前作业解标记
    }
    visited[rop[depth]-1]=false;
    rop[depth]=0;
    return;
}
int main()
{
    printf("请输入任务数：");
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        printf("作业%d分别在机器1与机器2上运行时间：",i+1);
        scanf("%d %d",&a[i][0],&a[i][1]);
    }
    allot_task(1);
    printf("最优调度序列为：");
    for(int i=0;i<n;i++)
    {
        printf("%d ",best_result[i]+1);
    }
    printf("\n消耗时间为：%d\n",min);
}