2. 栈¶
2.1. 目标¶
完成本模块后,学生将能够:
描述栈的抽象数据类型/数据结构以及栈的特征
使用基于数组或链式链的方法在 Java 中实现栈
开发并使用栈方法
测试栈的功能
评估一系列应用/用例,以判断使用栈数据结构是否合适
2.1.1. 建议阅读¶
第 5 - 6 章(Bags),来自 Data Structures and Abstractions with Java(第 4 版),Frank M. Carrano 和 Timothy Henry 著
2.2. 交互式:栈简介¶
栈接口(The Stack Interface)
StackInterface.java (right click-> save link as...)
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
2.3. 检查点 1¶
2.4. 交互式:栈内存示例¶
2.5. 检查点 2¶
2.6. 基于数组的栈设计¶
2.7. 检查点 3¶
2.8. 栈的数组实现¶
跟随并参与(Follow Along and Engage)
下载与视频对应的幻灯片。观看视频时在幻灯片上做笔记,并自己动手练习绘制示意图!
2.9. 栈的链式链实现¶
跟随并参与(Follow Along and Engage)
下载与视频对应的幻灯片。观看视频时在幻灯片上做笔记,并自己动手练习绘制示意图!
