数据性质
栈:数据只从一端进行流入流出,即后进先出。
允许插入删除一端:栈顶。另一端:栈底。
本质还是顺序表,但是非栈顶数据不可开放和访问。
基本操作有:初始化、判空、判满、入栈 Push、出栈 Pop、读栈顶 GetTop。入栈时栈已经满,叫上溢。出栈或读栈顶时空栈,叫下溢。
队列:数据从一端流入,一端流出。
栈的写法和语法
顺序栈
基本要素:一个连续数组,top 变量为栈顶元素下标并在新元素进出栈过程中不断更新,初始化为 -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
| template <class T>
class SeqStack {
T* data; // 动态数组,构造函数为其申请长度为 n 的连续空间
int top;
int cap;
public:
explicit SeqStack(int n = 50)
: data(new T[n]), top(-1), cap(n) {}
~SeqStack() { delete[] data; }
bool empty() const { return top == -1; }
bool full() const { return top == cap - 1; }
bool push(const T& x) {
if (full()) return false;
data[++top] = x;
return true;
}
bool pop(T& x) {
if (empty()) return false;
x = data[top--];
return true;
}
bool getTop(const T& x) const = delete;
bool getTop(T& x) const {
if (empty()) return false;
x = data[top];
return true;
}
};
|
补充 explicit 知识点:
explicit 作用为防止单参数(或多参数但其余都有默认值)构造函数发生隐式转换。以上面的代码为例:
1
2
| SeqStack<int> s1; // 调用默认参数 n = 50
SeqStack<int> s2(100); // 显式传入参数 n = 100
|
如果写成:
1
| SeqStack<int> s3 = 100;
|
编译器会尝试把 100 隐式转换为 SeqStack<int>,进而调用 SeqStack<int>(100),这通常不是想要的意思。explicit 会阻止这种转换:
1
2
| void func(SeqStack<int> s);
func(100); // 编译报错,不能隐式转换参数
|
链栈
即数据存储用单链表,然后用一个头指针维护栈顶,若空栈则 top = nullptr 即可。
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
| template <class T>
struct Node {
T data;
Node* next;
};
template <class T>
class LinkedStack {
Node<T>* top;
public:
LinkedStack() : top(nullptr) {}
~LinkedStack() {
T x;
while (pop(x)) {}
}
bool empty() const { return top == nullptr; }
void push(const T& x) {
Node<T>* p = new Node<T>;
p->data = x;
p->next = top; // 先连到原来的栈顶
top = p; // 再让 top 指向新结点
}
bool pop(T& x) {
if (top == nullptr) return false;
Node<T>* p = top;
x = p->data;
top = p->next;
delete p;
return true;
}
};
|
队列
先进先出,分为两端,一端只负责进,一端只允许出。
顺序队列
假溢出问题
本质原因是当头位置出队列的时候,头部指针向后更新,但是尾端指针无法更新;只要进来了 5 个元素,rear 尾指针就会指向第五个元素,会输出已满。
解决方案:顺序队列用数组实现,解决假溢出需要把数组看成首尾相连的循环。
比如五个位置,下标为 0–4:
1
| rear = (rear + 1) mod totalSize
|
比如进来 5 个,出去 2 个,这时候 rear 指向下标 0 的位置;若已有出队列则可以利用。
循环队列的判满和判空
有上边解决假溢出,自然就可以用尾指针位置是否有元素来判断,即:
1
| (rear + 1) mod totalSize == front
|
但是这样,如果一个容量为 5 的数组真正存放 5 个数时,不能判断它是满还是空,因为这两种情况都会得到 front == rear,与空队列一致。
故约定:队列牺牲一个数组位置,来区分满和空。
栈和队列的应用:递归
递归定义:函数在执行过程中调用它本身,给出递归推导和终止条件。
示例:
1
2
3
4
5
| int Length(Qnode* p) {
if (p == nullptr)
return 0;
return 1 + Length(p->next); // 递推关系,一层一层嵌套,故使用栈来实现
}
|
示例 2:计算组合数与输出组合。从 n 个数中选择 r 个,按最大数降序输出所有组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void combinations(int n, int r, vector<int>& chosen) {
if (r == 0) {
for (int x : chosen)
cout << x << ' ';
cout << '\n';
return;
}
if (n < r)
return; // 剩下的数不够选
chosen.push_back(n); // 选择 n
combinations(n - 1, r - 1, chosen);
chosen.pop_back(); // 撤销选择,恢复之前的状态
combinations(n - 1, r, chosen); // 不选择 n
}
|
单向递归和尾递归
广义表
广义表的元素可以是原子,也可以是子表。原子就是不再作为表继续拆分的元素(即表的多层嵌套)。
- 广义表长度:只数最外层元素的个数。
- 深度:最大深度元素的深度 + 1。空表深度为 1,原子深度为 0(实际就是嵌套层数)。
表头 head 取第一个元素;表尾 tail 取删除第一个元素后剩下的表,指向的是一个表。若只有一个元素,则表尾取空表。
取表中某个元素,则需要一层一层解开表,这里还要注意,(B)到 B,还要做一次 head 操作。