30.2. Stacks and Queues¶
30.2.1. Container Class Design Issues¶
- Storing a record vs. Storing a reference to a record
- Homogeneity: Allow different record types? Check and block?
- Deletion: What happens to the record?
30.2.2. Stacks¶
LIFO: Last In, First Out.
Restricted form of list: Insert and remove only at front of list.
Notation:
- Insert: PUSH
- Remove: POP
- The accessible element is called TOP.
30.2.3. Stack ADT¶
public interface Stack { // Stack class ADT // Reinitialize the stack. public void clear(); // Push "it" onto the top of the stack public boolean push(Object it); // Remove and return the element at the top of the stack public Object pop(); // Return a copy of the top element public Object topValue(); // Return the number of elements in the stack public int length(); // Return true if the stack is empty public boolean isEmpty(); }interface Stack { // Stack class ADT // Reinitialize the stack. void clear(); // Push "it" onto the top of the stack boolean push(Object it); // Remove and return the element at the top of the stack Object pop(); // Return a copy of the top element Object topValue(); // Return the number of elements in the stack int length(); }public interface Stack<E> { // Stack class ADT // Reinitialize the stack. public void clear(); // Push "it" onto the top of the stack public boolean push(E it); // Remove and return the element at the top of the stack public E pop(); // Return a copy of the top element public E topValue(); // Return the number of elements in the stack public int length(); // Tell if the stack is empty or not public boolean isEmpty(); }
30.2.4. Array-Based Stack (1)¶
Issues:
- Which end is the top?
- Where does “top” point to?
- What are the costs of the operations?
30.2.5. Array-Based Stack (2)¶
class AStack implements Stack { private Object stackArray[]; // Array holding stack private static final int DEFAULT_SIZE = 10; private int maxSize; // Maximum size of stack private int top; // First free position at top // Constructors AStack(int size) { maxSize = size; top = 0; stackArray = new Object[size]; // Create stackArray } AStack() { this(DEFAULT_SIZE); }class AStack implements Stack { private Object stackArray[]; // Array holding stack private static final int DEFAULT_SIZE = 10; private int maxSize; // Maximum size of stack private int top; // First free position at top // Constructors AStack(int size) { maxSize = size; top = 0; stackArray = new Object[size]; // Create stackArray } AStack() { this(DEFAULT_SIZE); }class AStack<E> implements Stack<E> { private E stackArray[]; // Array holding stack private static final int DEFAULT_SIZE = 10; private int maxSize; // Maximum size of stack private int top; // First free position at top // Constructors @SuppressWarnings("unchecked") // Generic array allocation AStack(int size) { maxSize = size; top = 0; stackArray = (E[])new Object[size]; // Create stackArray } AStack() { this(DEFAULT_SIZE); }
30.2.6. Linked Stack¶
// Linked stack implementation class LStack implements Stack { private Link top; // Pointer to first element private int size; // Number of elements // Constructors LStack() { top = null; size = 0; } LStack(int size) { top = null; size = 0; }// Linked stack implementation class LStack implements Stack { private Link top; // Pointer to first element private int size; // Number of elements // Constructors LStack() { top = null; size = 0; } LStack(int size) { top = null; size = 0; }// Linked stack implementation class LStack<E> implements Stack<E> { private Link<E> top; // Pointer to first element private int size; // Number of elements // Constructors LStack() { top = null; size = 0; } LStack(int size) { top = null; size = 0; }What are the costs of the operations?
How do space requirements compare to the array-based stack implementation?
30.2.7. Queues¶
FIFO: First in, First Out
Restricted form of list: Insert at one end, remove from the other.
Notation:
- Insert: Enqueue
- Delete: Dequeue
- First element: Front
- Last element: Rear
