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

Queue:

Stack:



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;
   
    /****CONSTRUCTORS****/
   
    /**
     * 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) {}
   
    /****ACCESSORS****/
   
    /**
     * 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;

    }
   
    /****MUTATORS****/
   
    /**
     * 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{}
   
    /****ADDITONAL OPERATIONS****/
   
    /**
     * 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!~