Close
Close Window

Masters of Engineering Bridge Course

Chapter 8 Linked Lists, Bags, Stacks, and Efficiency

Show Source |    | About   «  8.4. Efficiency   ::   Contents   ::   8.6. Unit 8 Lab 1 Placeholder  »

8.5. Stacks

8.5.1. Objectives

Upon completion of this module, students will be able to:

  • Describe the Stack Abstract Data Type/Data Structure and the characteristics of a Stack

  • Implement Stacks in Java using an Array-Based or Linked-Chain approach

  • Develop and use Stack methods

  • Test the functionality of Stack

  • Evaluate a range of applications / use cases to determine if use of the Stack Data Structure is appropriate

8.5.1.1. Suggested Reading

Chapters 5 - 6 Bags from Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry

8.5.2. Introduction to Stacks [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

Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

Video Slides 8.5.2-StacksIntro

8.5.3. Checkpoint 1

8.5.4. StackIntroVideoMemory Example [6:25]

8.5.5. Checkpoint 2

8.5.6. Stacks Array-Based Design [4:57]

8.5.7. Checkpoint 3

8.5.8. Stacks Array Implementation

Follow Along and Engage

Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

Video Slides 8.5.8.1-StacksArrayImplementation.pdf

8.5.9. Stacks Linked Chain Implementation [12:50]

Follow Along and Engage

Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself!

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

8.5.10. Checkpoint 4

8.5.11. Programming Practice: LinkedStacks

   «  8.4. Efficiency   ::   Contents   ::   8.6. Unit 8 Lab 1 Placeholder  »

Close Window