数据结构碎碎念（二）

碎碎念

在中，提到了栈，这在计算机领域中可以说是非常重要的一个概念，我们可以在高级语言中找到其使用（如stack<int>），我们还可以在汇编语言中找到（助记符push，及相关的栈的概念），甚至于可以在硬件中看到栈的实现（如x86特有的浮点寄存器结构）。

我们在说栈的时候，通常指如下两种情况：

1. 编程中使用的栈（stack<int>）及其相关的操作。

2. 栈指针（不是stack<int>中的top变量，而是程序运行时栈溢出这类内存分配的问题）

栈

在数据结构中对栈的定义十分简单： 一个 只能对栈顶进行操作的线性表。

这个定义中明确的规定了栈必须是一个线性表，同时隐式的限制了栈顶的数量。

可能会有人说，这个栈顶不是应该就只有一个吗？怎么就要讨论栈顶的数量？

如果栈顶是一个绝对概念（顶部就是上面，上面就是顶部），那么栈顶的确可以说只有一个。

但栈顶的定义其实是相对于栈底来说的，栈顶在上面，那么栈底就在下面，反之亦然。

栈顶的数量

1. 栈顶数量为0，可以吗？

答案是否定的，如果不规定栈顶（没有栈顶），那就没有了操作的入口，那这个栈就没有存在的意义。

1. 栈顶数量为1，标准栈

这种类型的栈我们首先就会想到自下而上增长的栈：

其实现如下：

const int MAXSIZE = 10;
// 1. 声明一个栈
int stack[MAXSIZE];
int top = -1;

// 2. 栈空
top == -1;

// 3. 栈满
top == MAXSIZE;

// 4. 压栈push(x)
stack[top++] = x;

// 5. 弹栈pop()
int x = stack[top--];

// 6. 读取栈顶元素
int x = stack[top];

这个实现方法可以说是通用的，只要是支持数组的语言，基本上都可以用该方法实现一个简单的固定大小的栈。

在这个实现中，我们默认将栈底设置在了-1索引位置处，栈的增长方向是 -1->10 ，反过来设置也是可以的，因为栈底和栈顶的位置是相对的。

1. 栈顶数量为2，可以吗？

当然可以，共享栈就是两个栈顶，分别对应位置-1和MAXSIZE，两边同时向中间增长。

top1 = -1;
top2 = MAXSIZE;

// top1压栈做自增操作，弹栈做自减操作
// top2压栈做自减操作，弹栈做自增操作
// 栈满是top1+1 == top2;

1. 栈顶的数量大于2，存在吗？

目前为止，我们所讨论内容的都是一维的，再怎么开脑洞也找不到栈顶大于2的情况。

等等，如果强行对共享栈进行扩展，咱还真能找到栈顶数量大于2的情况，但这时候，我们应该就会发现本文的一个逻辑漏洞，这个漏洞对于本节的讨论是致命的。

致命的漏洞

本文在讨论栈的时候是以栈顶的数量为标准进行划分的，但看到这里，我们应该能发现一个逻辑漏洞，即当栈顶数量大于等于2的时候，他就是多个栈，而不是一个栈了。

所以，栈顶数量是不能作为栈类型的划分依据的，那本文在讨论什么？栈的复合吗？有点像诶。但是对于我们来说，好像下面这种使用才像是复合：

template <class T>
class MinStack<T> {
private:
  stack<T> st;
  stack<T> min;
}

// 最小栈的算法，还是挺经典的，可以自己查一查。

最小栈

总结

本文的内容，上一节算是总结，关于栈，还能聊两句基本的概念。

根据物理结构的不同，栈被划分成两个大类：

1. 顺序栈

采用顺序存储的栈称为顺序栈：就是在内存中申请一组 连续的 存储单元存放栈中的元素，可以认为就是数组实现。

1. 链式栈

采用链式存储的栈称为链式栈：栈中的元素在内存中 不连续 ，同时每个存储单元中预留一小块位置存放下一个元素的地址，可以认为就是单链表实现。