MengBridgeCourse 中文版

第 8 章 链表、包、栈与效率

| 关于   英文版   «  8.4. 效率   ::   目录   ::   8.6. 单元 8 实验 1 占位符  »

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

Follow Along and Engage

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

Video Slides 8.5.2-StacksIntro

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

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

Video Slides 8.5.8.1-StacksArrayImplementation.pdf

8.5.9. 栈链表实现 [12:50]

Follow Along and Engage

下载与视频对应的幻灯片。观看视频时,在它们上面做笔记,练习自己绘制图表!

Video Slides 8.5.9.1-StacksLinkedChainImplementation.pdf
Video Slides 8.5.9.1-TestingStacks.pdf

8.5.10. 检查点

8.5.11. 编程练习:LinkedStacks

   «  8.4. 效率   ::   目录   ::   8.6. 单元 8 实验 1 占位符  »

关闭窗口