程序员学数据结构

第4章　栈：后入先出的数据集

栈（Stack）是一种抽象化的数据结构，其中的对象遵循后入先出（Last-InFirst-Out, LIFO）的原则被增加和删除。相应地，能够清晰定义栈结构的两种操作分别为压栈和出栈，压栈是为这个数据集加入对象，出栈则将这个数据集中的对象删除。其他常见操作还有查看、清空、计数、判断栈是否为空、判断栈是否已满等，以上这些操作会在本章的高级话题中进行讨论。

栈可以基于数组或链表。与链表相似，栈有已排序栈和未排序栈之分。考虑到链表的结构，链表栈的排序操作效率会高于数组栈。

栈这种数据结构非常适合需要在表尾增加或删除对象的应用程序。对特定路径或一系列操作进行回溯追踪便是个好例子。如果应用程序允许在数据集的任意一个位置进行数据的增加和删除，则根据我们目前所学的这些数据结构知识，可以知道使用链表是最合适的。

本章将涵盖以下主要内容：

• 栈的定义；
• 栈的初始化；
• 案例学习——运动规划算法；
• 栈的实现；
• 栈的常用操作；
• 数组栈；
• 链表栈；
• 查找。

4.1　栈的初始化

对于栈这种数据结构，每种开发语言都提供了不同程度的支持。下面便是栈的初始化、向栈中加入对象以及从栈顶删除对象这些操作的示例。

C＃

C#通过Stack<T>泛型类提供了栈的一种具体实现。

Stack<MyObject> aStack = new Stack<MyObject>();
aStack.Push(anObject);
aStack.Pop();

Java

Java通过Stack<T>泛型类提供了栈的一种具体实现。

Stack<MyObject> aStack = new Stack<MyObject>();
aStack.push(anObject);
aStack.pop();

Objective-C ...