软件设计与数据结构

Chapter 5 Efficiency, Stacks

| 关于   «  1. 效率   ::   目录   ::   3. 实验 5 冰淇淋蛋筒  »

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

跟随并参与(Follow Along and Engage)

下载与视频对应的幻灯片。观看视频时在幻灯片上做笔记,并自己动手练习绘制示意图!

StacksIntro.pdf

2.3. 检查点 1

2.4. 交互式:栈内存示例

2.5. 检查点 2

2.6. 基于数组的栈设计

2.7. 检查点 3

2.8. 栈的数组实现

跟随并参与(Follow Along and Engage)

下载与视频对应的幻灯片。观看视频时在幻灯片上做笔记,并自己动手练习绘制示意图!

StacksArrayImplementation.pdf

2.9. 栈的链式链实现

跟随并参与(Follow Along and Engage)

下载与视频对应的幻灯片。观看视频时在幻灯片上做笔记,并自己动手练习绘制示意图!

StacksLinkedChainImplementation.pdf
TestingStacks.pdf

2.10. 检查点 4

2.11. 编程练习:LinkedStacks

   «  1. 效率   ::   目录   ::   3. 实验 5 冰淇淋蛋筒  »

关闭窗口