2.2. Stacks and Queues¶
2.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?
2.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.
2.2.3. Stack ADT¶
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(); }
2.2.4. Array-Based Stack (1)¶
Issues:
Which end is the top?
Where does “top” point to?
What are the costs of the operations?
2.2.5. Array-Based Stack (2)¶
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); }
2.2.6. Linked Stack¶
// 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?
2.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
