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