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

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 */ @Override public String toString() { String result = ""; result += "\n"; return result; } }
Wrap Up
- Answer the review questions on Canvas for today's lesson
|