栈与队列及其应用

栈的实现

1
2
3
4
5
6
7
8
9
10
11
const int N = 1e6 + 10;
class stack
{
public:
	int top = -1;
	int a[N];
	bool empty() { return top == -1; }
	void push(int x) { a[++top] = x; }
	int pop() { return a[top--]; }
	int peak() { return a[top]; }
};

常见应用

进制转换(10换16)

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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
class stack
{
public:
	int top = -1;
	char a[N];
	bool empty() { return top == -1; }
	void push(int x) { a[++top] = x; }
	char pop() { return a[top--]; }
	char peak() { return a[top]; }
};
int main()
{
	char digit[] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
	int n;
	cin >> n;
	stack S;
	while (n > 0)
	{
		S.push(digit[n % 16]);
		n /= 16;
	}
	while (!S.empty())
		cout << S.pop();
}

括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool jud(string a)
{
	stack S;
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] == '(' || a[i] == '[' || a[i] == '{')
			S.push(a[i]);
		if (a[i] == ')' || a[i] == ']' || a[i] == '}')
		{
			if (S.empty()) return false;//pop之前看是否为空
			char ch = S.pop();
			bool ismatch = (ch == '(' && a[i] == ')') || (ch == '[' && a[i] == ']') || (ch == '{' && a[i] == '}');
			if (!ismatch)
				return false;
		}
	}
	return S.empty();//最后若栈为空则正确
}

表达式求值

  • 后缀表达式求值

从左向右读，若是操作数则入栈，若是操作符则弹出两个操作数，计算后压栈

  • 中缀表达式转后置表达式

手工方法：

  1. 将表达式充分加括号，最终使没一对括号里仅有一个运算符
  2. 移动运算符使之放在与之对应的右括号后面
  3. 去掉所有括号
    A-B+C/DE
    (A-((B+(C/D))E))
    (A((B(CD)/)+E)    )-
    ABCD/+E    -

算法：设置一个栈存放运算符

  1. 操作数：直接放入后缀表达式
  2. 操作符：
    （1）栈空或栈顶为左括号，运算符压栈
    （2）运算符优先级大于栈顶运算符，压栈
    （3）<=，弹栈至优先级大于栈顶元素，再压栈
  3. 括号：左括号压栈，右括号弹栈至左括号
  4. 结束符：弹栈至栈空

  • 直接计算中缀表达式的值

结合两者，设立两个栈（操作数栈和运算符栈），当运算符弹栈后，从操作数栈也弹出两个元素直接计算结果压栈
important

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
#include <iostream>
using namespace std;
const int N = 1e4+10;
template <class T>
class Stack
{
public:
	bool empty() { return top == -1; }
	void push(T x) { a[++top] = x; }
	T pop() { return a[top--]; }
	T peak() { return a[top]; }
private:
	int top = -1;
	T a[N];
};

Stack<int> NUM;
Stack<char>OP;
int p[100] = { 0 };//运算符优先级

void operation(Stack<int>&NUM, Stack<char>&OP)//将计算操作抽离出来
{
	char t = OP.pop();
	int b = NUM.pop();//注意a,b顺序
	int a = NUM.pop();
	if (t == '+') NUM.push(a + b);
	else if (t == '-')NUM.push(a - b);
	else if (t == '*')NUM.push(a * b);
	else NUM.push(a / b);
}
int culculate(char* s)
{
	int len = strlen(s);
	p['+'] = p['-'] = 1; p['*'] = p['/'] = 2;//定义优先级！
	for (int i = 0; i < len; i++)
	{
		if (s[i] >= '0' && s[i] <= '9')//操作数
		{
			int tmp = 0;
			while (i < len && s[i] >= '0' && s[i] <= '9')
				tmp = 10 * tmp + s[i++] - '0';
			NUM.push(tmp);
			i--;//
		}
		else if (s[i] == '(') OP.push('(');//括号
		else if (s[i] == ')')
		{
			while (!OP.peak() == '(')
				operation(NUM, OP);
			OP.pop();
		}
		else//操作符
		{
			while (!OP.empty() && OP.peak() != '(' && !(p[s[i]] > p[OP.peak()]))//OP为空，遇到左括号,s[i]优先级大则不弹
			{
				operation(NUM, OP);
			}
			OP.push(s[i]);
		}
	}
	while (!OP.empty())
		operation(NUM, OP);
	return NUM.peak();
}
int main()
{
	char a[] = "20+8*3";
	cout<<culculate(a);
}

栈混洗

  • 栈混洗的甄别：判断是否为合法的出栈序列

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(int A[], int B[], int n)
{
	Stack s;
	int k = 0;//通过k扫描入栈序列
	for (int i = 0; i < n; i++)//通过i扫描出栈序列
	{
		while (s.empty() || s.peak() != B[i])
			if (k < n) s.push(A[k++]);
			else return false;
		s.pop();//只有s.peak()==B[i]才弹栈
	}
	return true;
}

  • 栈混洗的总数：有多少种可能的出栈序列

6个元素的栈混洗总数
入栈序列1，2…6可能的合法出栈序列数
6对括号的合法匹配序列数

队列的讨论及应用

实现

1
2
3
4
5
6
7
8
9
10
class queue
{
public:
    int p[N];
    int front=0;
    int rear=0;
    void enqueue(int x){p[rear++]=x; }
    int dequeue(){ return p[front++];}
    bool empty(){return front==rear;}
};

循环队列