Welcome to Lesson 6!

Learning Objectives
By the end of this class, you should know...

  • The difference between the Stack and Queue ADTs
  • Applications of Stacks
  • The most important Stack operations
  • How to implement a Stack data structure

1. Stacks

  • Last class we talked briefly about Stacks.
  • We learned that Stacks are organized by the principle of Last In, First Out or LIFO, just like a stack of dishes.
  • The last dish placed on the stack of dishes is the first one to be removed.

A Stack

Stack of Dishes 2

Like this stack of dishes, Stacks are organized according to the principle of LIFO: last in, first out. Image Source

  • Therefore, many of the Stack operations are concentrated at the very front of the stack.
  • What does this mean for our Stack implementation?

1.1. Stack Applications
  • Method call stacks (we will discuss more when we get to recursion).
  • Undo sequence of a text editor.
  • Page visited history in a web browser.
  • Matching tags in HTML and XML
  • Can you think of any others?

1.2. Stack Operations

  • Two important Stack operations are known as Push and Pop.
  • Pushing an item onto the Stack means inserting a new item at the top of the Stack.
  • Popping an item off the Stack means removing the item at the top of the Stack.

Two important Stack operations: Push and Pop. Image Source.

  • Note that unlike the Queue, the Stack only allows access to its top item.

1.3. Diagrams Comparing Stack and Queue



2. Writing Our Own Stack Class

  • Inside of your Lab3 Java project, add a new class called Stack.java
  • Copy and paste the following code into Stack.java.
  • Test it - and your Queue.java methods - in Lab3Test.java
  • What looks different from the Queue? What looks the same?

 * Stack.java
 * @author
 * @author

import java.util.NoSuchElementException;

public class Stack<T> {
    private class Node {
        private T data;
        private Node next;
        public Node(T data) {
            this.data = data;
            this.next = null;
    private int length;
    private Node top;
     * Default constructor for the Stack class
     * @postcondition a new Stack object with all fields
     * assigned default values
    public Stack() {}
     * Copy constructor for the Stack class
     * @param original the Stack to copy
     * @postcondition a new Stack object which is
     * an identical, but distinct, copy of original
    public Stack(Stack<T> original) {}
     * Returns the value stored at the top
     * of the Stack
     * @return the value at the top of the Stack
     * @precondition !isEmpty()
     * @throws NoSuchElementException when the
     * precondition is violated
    public T peek() throws NoSuchElementException {

       return null;

     * Returns the length of the Stack
     * @return the length from 0 to n
    public int getLength() {
        return -1;
     * Determines whether a Stack is empty
     * @return whether the Stack is emtpy
    public boolean isEmpty() {
        return false;
     * Determines whether two Stacks contain
     * the same values in the same order
     * @param Q the Stack to compare to this
     * @return whether Q and this are equal
    @Override public boolean equals(Object o) {

        return false;

     * Inserts a new value at the top of
     * the Stack
     * @param data the new data to insert
     * @postcondition a new node at the end
     * of the Stack
    public void push(T data) {}
     * Removes the top element of the Stack
     * @precondition !isEmpty()
     * @throws NoSuchElementException when
     * the precondition is violated
     * @postcondition the top element has
     * been removed
    public void pop() throws NoSuchElementException{}
     * Returns the values stored in the Stack
     * as a String, separated by a blank space
     * with a new line character at the end
     * @return a String of Stack values
    public String toString() {
        String result = "";
        result += "\n";
        return result;

Wrap Up
  • Answer the review questions on Canvas for today's lesson

~Have a Great Weekend!~