Question

链栈中为什么需要头结点

Answer 1

链栈中需要头结点原因：因为栈是后进先出的数据结构，我们不可能直接就对栈底元素进行操作，要想操作栈底元素，必须得先依次让非栈底元素出栈。

即使设了头指针，也没有用处，对栈顶元素的操作，与头指针没关系。所以不必设头指针指向栈底元素。

1、头结点不存储数据，此时它只是个标记。链表从这里开始，意义在于头结点中的next。引出后面的链表数据。这就是平常写的头结点。

2、头结点存储数据，它此时就不只是个标记和引出后面的链表数据，还有它里面的data。意义在于data 和 next。

两个栈共享同一存储空间：

当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。

只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为└m/2┘和┌m/2┐的向量空间比较，前者发生上溢的概率比后者要小得多。