编程概念：栈

栈是一种ADT，它可能涉及动态或静态实现。栈是后进先出 (LIFO) 或先进后出 (FILO) ADT。实现应包括两个操作，入栈和出栈，以及指向栈顶的指针。

现实生活中的例子是您可能放在桌子上的书堆

在这个例子中，我们不断地将（入栈）书籍添加到书堆中。如果我们要拿到最底部的关于汽车的书，我们必须首先移除（出栈）上面的所有书。因此，先进后出 (FILO)

让我们看看栈的计算机实现

• 入栈：将一个新的指定项添加到栈顶
• 出栈：从栈顶移除项。

状态 1	状态 2	状态 3	状态 4	状态 5
入栈 '大象'	入栈 '河马'	入栈 '斑马'	出栈	入栈 '火烈鸟'
内存位置 数据 栈顶 4 3 2 1 大象 <--	内存位置 数据 栈顶 4 3 2 河马 <-- 1 大象	内存位置 数据 栈顶 4 3 斑马 <-- 2 河马 1 大象	内存位置 数据 栈顶 4 3 斑马 2 河马 <-- 1 大象 请注意数据并没有被“删除” 栈顶指针移动 以表明它不再位于 栈中	内存位置 数据 栈顶 4 3 火烈鸟 <-- 2 河马 1 大象

栈有几种用途

• 反转队列（如上面用字母排序的名称所示）
• 执行逆波兰计算（参见……）
• 保存递归函数调用的返回地址和系统状态

练习：栈 在执行以下每个命令后绘制栈，从空栈开始。栈实现了什么 入栈 '安娜贝尔' 入栈 '克里斯' 入栈 '海明威' 入栈 '詹姆斯' 出栈 出栈 出栈 出栈 答案 命令 1 命令 2 命令 3 命令 4 内存位置 数据 栈顶 4 3 2 1 安娜贝尔 <-- 内存位置 数据 栈顶 4 3 2 克里斯 <-- 1 安娜贝尔 内存位置 数据 栈顶 4 3 海明威 <-- 2 克里斯 1 安娜贝尔 内存位置 数据 栈顶 4 詹姆斯 <-- 3 海明威 2 克里斯 1 安娜贝尔 命令 5 命令 6 命令 7 命令 8 内存位置 数据 栈顶 4 詹姆斯 3 海明威 <-- 2 克里斯 1 安娜贝尔 Output: James 内存位置 数据 栈顶 4 詹姆斯 3 海明威 2 克里斯 <-- 1 安娜贝尔 Output: Hemingway 内存位置 数据 栈顶 4 詹姆斯 3 海明威 2 克里斯 1 安娜贝尔 <-- Output: Chris 内存位置 数据 栈顶 4 詹姆斯 3 海明威 2 克里斯 1 安娜贝尔 Output: Annabelle 栈顶 = 0 栈为空 这组指令使用栈按顺序输入数据，然后以反序输出数据 给出从状态 1 到状态 2 所需的指令集，如下所示 状态 1 状态 2 内存位置 数据 栈顶 4 3 鲨鱼 <-- 2 粉笔 1 奶酪 内存位置 数据 栈顶 4 3 女巫 <-- 2 沙子 1 奶酪 答案 出栈 出栈 入栈 '沙子' 入栈 '女巫' 如果我们有一个空栈，我们将栈顶指针设置为多少？ 答案 0 或 null 描述栈数据类型 答案 栈是一种先进后出或后进先出的数据类型 给出栈在计算机中使用的两种情况 答案 反转队列（如上面用字母排序的名称所示） 执行逆波兰计算（参见……） 保存递归函数调用的返回地址

Dim myStack(10) as string
Dim ToS as integer = 0 'this is our pointer
Dim item as string

While item <> “#”
  Console.writeline(“please insert item ” & ToS & “ into the stack: ”)
  item = Console.readline()
  myStack(ToS) = item
  ToS = ToS + 1
End While

For x = ToS to 0 step -1
  Console.writeline(“Stack item: ” & x & “ = ”  & myStack(x) )
Next

console.readline()