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
2.2.8. Queue Implementation (1)¶
2.2.9. Queue Implementation (2)¶
1 / 9 Settings<<<>>>A more efficient implementation can be obtained by relaxing the requirement that all elements of the queue must be in the first $n$ positions of the array. We still require that the queue be stored be in contiguous array positions, but the contents of the queue will be permitted to drift within the array.
