17.23. Stacks and Queues¶
17.23.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?
17.23.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.
17.23.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(); }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(); }
17.23.4. Array-Based Stack (1)¶
Issues:
Which end is the top?
Where does “top” point to?
What are the costs of the operations?
17.23.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<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); }
17.23.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<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?
17.23.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
