作者：解学武

对于逻辑关系为“一对一”的数据，除了用顺序表和链表存储外，还可以用栈结构存储。

栈是一种“特殊”的线性存储结构，它的特殊之处体现在以下两个地方：
1、元素进栈和出栈的操作只能从一端完成，另一端是封闭的，如下图所示：
 
通常，我们将元素进栈的过程简称为“入栈”、“进栈”或者“压栈”；将元素出栈的过程简称为“出栈”或者“弹栈”。

2、栈中无论存数据还是取数据，都必须遵循“先进后出”的原则，即最先入栈的元素最先出栈。以图 1 的栈为例，很容易可以看出是元素 1 最先入栈，然后依次是元素 2、3、4 入栈。在此基础上，如果想取出元素 1，根据“先进后出”的原则，必须先依次将元素 4、3、2 出栈，最后才能轮到元素 1 出栈。

我们习惯将栈的开口端称为栈顶，封口端称为栈底。例如在图 1 中，元素 4 一侧为栈顶，元素 1 一侧为栈底，如图 2 所示。

由此我们可以对栈存储结构下一个定义：栈一种“只能从一端存取元素，且存取过程必须遵循‘先进后出’原则”的线性存储结构。

栈的实际应用

对于刚刚接触栈存储结构的读者来说，可能很难理解为什么会设计出“栈”这种存储结构，它有什么用？栈是一种特殊的线性存储结构，借助它的“特殊性”，可以解决很多实际问题。

1) 实现浏览器的“回退”功能

所谓浏览器的“回退”功能，比如您用浏览器打开 A 页面，然后从 A 页面跳转到 B 页面，然后再从 B 页面跳转到 C 页面。这种情况下，如果想回到 A 页面，有两种方法：

• 重新搜索找到 A 页面；
• 借助浏览器的“回退”功能，先从 C 页面回退到 B 页面，再从 B 页面回退到 A 页面。

很多浏览器的“回退”功能就位于工具栏中，图标是一个类似←的箭头。

浏览器的“回退”功能底层就是用栈存储结构实现的，当从 A 页面跳转到 B 页面时，浏览器会执行入栈操作，A 页面信息会存入栈中；同样，从 B 页面跳转到 C 页面时，B 页面信息会存入栈中。当点击浏览器的“回退”按钮时，浏览器会执行“出栈”操作，根据“先进后出”的原则，B 页面先出栈，然后 A 页面出栈，这样就实现了“回退”的功能。

2) 实现 C 语言函数的相互调用

C语言程序中，函数间的相互调用过程也是用栈存储结构实现的。

举个简单的例子：

void func(){
    printf("Hello,World!");
}
int main(){
    func();
    return 0;
}

这段 C 语言程序中有两个函数，分别是 main() 函数和 func() 函数，其中 main() 函数内部调用了 func() 函数。

程序执行时，main() 函数会最先入栈，执行到第 5 行代码时，需要执行 func() 函数，此时会将 func() 函数入栈。等待 func() 函数执行完后，func() 函数会出栈，此时 main() 函数中的剩余代码会继续执行，直至 main() 函数执行完毕，做出栈操作，整个程序就执行结束了。

3) 解决一些实际问题

借助栈存储结构，可以快速解决类似“进制转换”、“括号匹配”等问题，具体的解决过程会在后续文章中做详细讲解。

栈的具体实现

和线性表类似，栈存储结构也有两种具体的实现方案：

• 顺序栈：用顺序表存储数据，数据存取的过程严格遵循栈结构的规定；
• 链栈：用链表存储数据，数据存储的过程严格遵循栈结构的规定。

显然，顺序栈和链栈两种实现方案，本质的区别仍然是顺序表和链表之间的区别，即顺序栈是将所有数据集中存储，而链栈是将数据分散存放，元素之间的逻辑关系靠指针维系。

关于顺序栈和链表的具体实现，会在后续章节做详细讲解。

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。