栈和队列

数据性质

栈:数据只从一端进行流入流出,即后进先出。 允许插入删除一端:栈顶。另一端:栈底。 本质还是顺序表,但是非栈顶数据不可开放和访问。 基本操作有:初始化、判空、判满、入栈 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 操作。

使用 Hugo 构建
主题 Stack 由 Jimmy 设计