栈
一、栈的顺序实现
使用连续的内存存储栈元素
1.SqStack.h
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
| #pragma once
#include "exception"
template <typename T>
class SqStack{
private:
T *data;
int top_;
int capacity;
public:
SqStack(int cap = 3)
{
data = new T[cap];
if(data != nullptr)
{
top_ = 0;
capacity = cap;
}
}
T& top();
bool push(T e);
bool pop();
bool empty();
void clear();
};
template <typename T>
T& SqStack<T>::top()
{
if(0 == top_)
{
throw "空栈";
}
return data[(top_-1)];
}
template <typename T>
bool SqStack<T>::push(T e)
{
if(capacity == top_)
{
T *p = new T[2*capacity];
if(p == nullptr)
return false;
for(int i = 0;i<capacity;i++)
{
p[i] = data[i];
}
delete[] data;
data = p;
capacity = 2 * capacity;
}
top_++;
data[top_-1] = e;
return true;
}
template <typename T>
bool SqStack<T>::pop()
{
if(top_ == 0)
{
return false;
}
top_--;
return true;
}
template <typename T>
bool SqStack<T>::empty()
{
return top_ == 0;
}
template <typename T>
void SqStack<T>::clear()
{
top_ = 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
| #include <iostream>
#include "SqStack.h"
using namespace std;
void testSqStack()
{
SqStack<char> stack;
stack.push('A');
stack.push('B');
stack.push('C');
stack.push('D');
while (!stack.empty())
{
char e = stack.top();
cout << e << " ";
stack.pop();
}
}
int main() {
testSqStack();
return 0;
}
|
编译结果
二、栈的链式实现
1.LKList.h
链式栈的压栈，在头节点的后面进行插入
链式栈的出栈，在头节点的后面进行删除
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
| #pragma once
#include "exception"
template <typename T>
class LkStack{
private:
struct LNode{
T data;
LNode *next;
};
LNode *head;
public:
LkStack()
{
head = new LNode();
head->next = nullptr;
}
virtual ~LkStack()
{
LNode *p = head->next;
while (p)
{
head->next = p->next;
delete p;
p = head->next;
}
delete p;
}
bool push(T e)
{
LNode *newNode = new LNode();
if(newNode == nullptr) return false;
newNode->data = e;
newNode->next = head->next;
head->next = newNode;
return true;
}
bool pop()
{
LNode *topNode = head->next;
if(topNode == nullptr) return false;
head->next = topNode->next;
delete topNode;
return true;
}
T &top()
{
LNode *topNode = head->next;
if(topNode == nullptr)
throw "空栈";
return topNode->data;
}
bool empty()
{
if(head->next == nullptr)
return true;
return false;
}
};
|
2.测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <iostream>
#include "SqStack.h"
#include "LkList.h"
using namespace std;
int main() {
LkStack<char> lStack;
lStack.push('A');
lStack.push('B');
lStack.push('C');
while (!lStack.empty())
{
char ch = lStack.top();
lStack.pop();
cout << ch << " ";
}
return 0;
}
|
三、栈的应用
1.数值进制转换
将10进制数转换为d进制
通过下图的计算过程，将先计算出的值压入栈中，全部计算完毕之后，进行出栈
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
| #include <iostream>
#include "SqStack.h"
using namespace std;
void BaseConversion()
{
int N,d;
int modNum;
cout << "输入十进制数: ";
cin >> N;
cout << "输入转换的d进制：";
cin>>d;
SqStack<int> stack;
while(N != 0)
{
modNum = N % d;
stack.push(modNum);
N = N/d;
}
while (!stack.empty())
{
int e = stack.top();
cout << e;
stack.pop();
}
}
int main() {
BaseConversion();
return 0;
}
|
运行结果：
1
2
3
| 输入十进制数: 1348
输入转换的d进制：8
2504
|
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
|
bool BracketMatching()
{
string s;
cout << "输入表达式：";
cin >> s;
char ch;
SqStack<char> stack;
for(int i = 0; i<s.size();i++)
{
switch (s[i])
{
case '{':
stack.push(s[i]);
break;
case '[':
stack.push(s[i]);
break;
case '(':
stack.push(s[i]);
break;
case '}':
if(stack.empty())
{
return false;
}
else
{
ch = stack.top();
stack.pop();
if(ch != '{')
return false;
}
break;
case ')':
if(stack.empty())
{
return false;
}
else
{
ch = stack.top();
stack.pop();
if(ch != '(')
return false;
}
break;
case ']':
if(stack.empty())
{
return false;
}
else
{
ch = stack.top();
stack.pop();
if(ch != '[')
return false;
}
break;
default:
break;
}
}
if(!stack.empty())
return false;
return true;
}
|
3.程序栈
程序栈，也称为调用栈或运行时栈，是程序在运行时管理函数调用的一个重要数据结构。它在计算机系统中负责追踪函数的调用与返回，并保存相关的局部变量、返回地址等信息
工作原理
程序栈是一种后进先出的数据结构，当程序执行时，它会保存每个函数调用的上下文信息，包括局部变量、参数、返回地址等。当函数结束时，这些信息会被从栈中弹出，并返回到调用该函数的地方继续执行
基本操作：
- 压栈：当一个函数被调用时，系统会将这个函数的调用信息（包括函数参数、局部变量、返回地址等）压入栈中，形成一个称为栈帧或活动记录
- 弹栈：当函数执行完毕，它的栈帧从栈中弹出，系统会恢复到调用该函数之前的状态
4.汉诺塔游戏
大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作
游戏规则：
每次只能移动一个圆盘
每个圆盘只能放在比它大的圆盘上，不能放在比它小的圆盘上
圆盘可以放在三个柱子中的任意一个上
递归思路：
假设有n个圆盘，三个柱子A、B、C，目标需要将所有圆盘移动到柱子C上
- 将前
n-1个圆盘从A移动到B，借助C（将前n-1个盘子，移动到辅助空间上）
- 将第
n个圆盘从A移动到C
- 再将
n-1个圆盘从B移动到C，借助A
如此理解：
- 将前
n-1从A移动到B，再将第n个盘子从A移动到C
- 此时
C已经到C，并且无论什么盘子移动到C中的第n个盘子上面都是遵守规则的，因为第n个盘子最大
- 问题就缩小规模了，变成了需要将前
n-1个盘子从B移动到C上
- 如此类推，问题规模在不断的缩减
- 出口：当只有一个盘子时，直接将其从起始的柱子，移动到目标的柱子
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
| #include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
void Solute(int N, char from, char to, char help)
{
if(N==1)
{
cout << "move " << N << " from " << from << " to " << to << endl;
return;
}
Solute(N-1, from, help, to);
cout << "move " << N << " from " << from << " to " << to << endl;
Solute(N-1, help, to, from);
}
int main() {
Solute(3, 'A', 'C', 'B');
return 0;
}
|
