8.5. 栈¶
8.5.1. 目标¶
完成本模块后,学生将能够:
描述栈抽象数据类型/数据结构及其特征
使用基于数组或链表的方法在 Java 中实现栈
开发并使用栈方法
测试栈的功能
评估一系列应用/用例以确定是否适合使用栈数据结构
8.5.1.1. 建议阅读¶
第 5-6 章(包,Bags),节选自 Frank M. Carrano 与 Timothy Henry 所著《Data Structures and Abstractions with Java》(第 4 版) 。
8.5.2. 栈的简介 [11:32]¶
The Stack Interface
StackInterface.java (right-click to download as .java file)
package stack;
/**
* An interface for the ADT stack.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @author maellis1
* @version May 2020
*/
public interface StackInterface<T> {
/**
* Adds a new entry to the top of this stack.
*
* @param newEntry
* An object to be added to the stack.
*/
public void push(T newEntry);
/**
* Removes and returns this stack's top entry.
*
* @return The object at the top of the stack.
* @throws stack.EmptyStackException
* if the stack is empty before the operation.
*/
public T pop();
/**
* Retrieves this stack's top entry.
*
* @return The object at the top of the stack.
* @throws stack.EmptyStackException
* if the stack is empty.
*/
public T peek();
/**
* Detects whether this stack is empty.
*
* @return True if the stack is empty.
*/
public boolean isEmpty();
/** Removes all entries from this stack. */
public void clear();
} // end StackInterface
8.5.3. 检查点 1¶
8.5.4. 堆栈介绍视频内存示例 [6:25]¶
8.5.5. 检查点 2¶
8.5.6. 基于数组的栈设计 [4:57]¶
8.5.7. 检查点 3¶
8.5.8. 栈数组实现¶
Follow Along and Engage
下载与视频对应的幻灯片。观看视频时,在幻灯片上做笔记,并亲自练习绘制图表!
8.5.9. 栈链表实现 [12:50]¶
Follow Along and Engage
下载与视频对应的幻灯片。观看视频时,在它们上面做笔记,练习自己绘制图表!
