0%
Requirements
Define Core Objects
Analyze Relationships
Establish Hierarchy
Collection Interface
Node Class
Design Patterns
Iterator Pattern: Safe Traversal
Template Method: Common Collection Operations
Producer-Consumer with Blocking Queue
Define Class Members / Write Code
Stack with Thread Safety
Queue with Thread Safety
Run and Test
Adhere to SOLID Guidelines
Consider Scalability and Flexibility
Lock-Based Thread Safety
Lock-Free Alternatives
Bounded Queue for Back-Pressure
Create/Explain Your Diagrams
Future Improvements
Stack and Queue seem like textbook data structures with trivial implementations. But designing them as production-quality, thread-safe, generic collections surfaces real engineering decisions: linked list vs. array backing, O(1) guarantees vs. cache locality, lock-based vs. lock-free concurrency, and how to expose traversal without leaking internal structure. The design challenge is building two structures that share a common interface while having fundamentally different access patterns.
Interview Dialogue
Functional Requirements
push(item) to add to the top, pop() to remove and return the top element, and peek() to view the top without removal. Follow Last-In-First-Out ordering. Throw an exception on pop/peek when empty.enqueue(item) to add to the back, dequeue() to remove and return the front element, and peek() to view the front without removal. Follow First-In-First-Out ordering. Throw an exception on dequeue/peek when empty.size() and isEmpty() run in O(1) time.Stack<T> and Queue<T> use generics for compile-time type safety without casting.Non-Functional Requirements
Start by scanning the requirements for nouns. "Stack with push and pop" gives us Stack. "Queue with enqueue and dequeue" becomes Queue. "Linked list elements with data and next pointer" maps to Node. "Common operations like size and isEmpty" give us the shared Collection interface. Not every noun becomes a class. "capacity" is a numeric field or constraint, not its own entity, but nouns give you the starting lineup.
Imagine a print queue: users send documents to the printer. The first document submitted prints first (FIFO). Now imagine a browser's back button: the most recently visited page is the first one you return to (LIFO). These two everyday scenarios produce Queue and Stack.
Both Stack and Queue are built on a linked list. Each element in the linked list is a Node: a container holding the data and a pointer to the next node. Node is an internal implementation detail, not exposed to callers.
Why is Node a separate class? Node encapsulates the pointer logic (data + next reference). Without it, Stack and Queue would manage raw pointer manipulation directly, mixing data storage with structural concerns.
The Stack maintains a top pointer to the head of the linked list. Push creates a new Node, points it to the current top, and updates top. Pop reads the top node's data, advances top to top.next, and returns the data. Both operations are O(1).
The Queue maintains both a head and a tail pointer. Enqueue creates a new Node and appends it at the tail. Dequeue reads from the head. Having both pointers ensures both operations are O(1). Without a tail pointer, enqueue would require traversing the entire list to find the end: O(n).
A Collection interface defines the shared contract: size(), isEmpty(), and iterator(). Both Stack and Queue implement this interface, enabling polymorphic usage. Code that only needs to check size or iterate can accept any Collection without knowing the concrete type.
Do not expose a shared base API so generic that Stack and Queue lose their semantics. A single insert/remove pair may look elegant, but it hides the difference between LIFO and FIFO, which is the entire reason both structures exist separately.
Why a separate Node class instead of combining its responsibilities into Stack? Each class should have one reason to change. If Stack handled both its own logic and Node logic, a change to either concern would risk breaking the other.
Composition: Stack owns Nodes, Queue owns Nodes
Nodes are created on push/enqueue and garbage-collected on pop/dequeue. They exist only within the data structure. A Node has no identity or purpose outside its Stack or Queue. This is composition: the parent manages the child's entire lifecycle.
Shared Interface: Stack and Queue implement Collection
Both data structures implement the same Collection interface. The relationship is interface implementation (dashed arrow in UML). Code that depends on Collection can work with either structure without knowing the concrete type.
Why not have Stack extend Queue or vice versa? Because their access semantics are fundamentally different. Stack returns the newest element (LIFO); Queue returns the oldest (FIFO). If Stack extended Queue, calling dequeue() would either return the wrong element or require O(n) traversal to reach the bottom. Liskov Substitution forbids both outcomes.
No Inheritance Between Stack and Queue
Stack and Queue do not extend each other. A Stack is not a special kind of Queue, and a Queue is not a special kind of Stack. They share an interface but have fundamentally different access patterns (LIFO vs. FIFO). Forcing inheritance would violate Liskov Substitution: a Stack cannot correctly behave as a Queue because popping returns the most recent item, not the oldest.
Iterator Creates Snapshot Traversal
The iterator() method returns an Iterator that traverses from the structure's access point (top for Stack, head for Queue). The Iterator holds a current-node pointer and advances it on each next() call. The Iterator does not modify the structure.
Three methods. No implementation is forced to implement unrelated operations. Stack never sees enqueue. Queue never sees pop. The shared interface contains only universally applicable methods.
Node's data field is final (immutable after construction), but next is mutable because the linked list structure changes as elements are added and removed. This is intentional: the data is fixed, but the node's position in the chain changes.
Why is Node generic? Without generics, Node would hold Object. Every getData() call would require casting. With Node<T>, the compiler enforces type safety. Stack<String> creates Node<String> objects, and getData() returns String directly.
Why not expose Node objects to callers instead of hiding them behind push/pop/enqueue/dequeue? Because exposing Node lets callers call node.setNext(null), severing the linked list and silently losing all elements after that node. It also lets callers create cycles (node.setNext(node)), causing infinite loops. Encapsulation ensures all structural changes go through controlled methods.
Both Stack and Queue provide an iterator that traverses without modifying the structure. The iterator holds a current-node pointer, initialized to top (Stack) or head (Queue), and advances on each next() call.
Without the Iterator pattern, callers would need direct access to Node objects to traverse. This would expose internal structure, allowing callers to break the linked list by modifying next pointers.
The Collection interface acts as a template for shared behavior. If you add utility methods like contains(T item) or toArray(), they can be implemented as default methods in the interface using only size(), isEmpty(), and iterator(). Concrete classes inherit these methods without any modification.
The Queue naturally extends to a bounded, blocking producer-consumer pattern. enqueue() blocks when full (producer waits). dequeue() blocks when empty (consumer waits). This is the foundation of java.util.concurrent.BlockingQueue and is one of the most important concurrency patterns in practice.
The Iterator pattern is essential for Stack and Queue because it provides traversal without exposing Node objects. Without it, callers would need direct linked-list access, which would bypass thread safety and size tracking.
Code Stack first, then Queue. Stack proves the one-pointer linked-list mechanics cleanly. Queue then adds the real edge case: keeping head and tail consistent when the last element is removed and the structure transitions back to empty.
Stack maintains a single pointer (top) and wraps every mutating operation in a ReentrantLock. push() creates a new Node, links it to the current top, and updates top. pop() reads top data, advances top, and returns the data. Both are O(1) and atomic.
Queue maintains two pointers (head and tail) for O(1) operations at both ends. enqueue() appends at tail. dequeue() removes from head. The two-pointer design is what makes Queue fundamentally different from Stack in structure, even though both use a linked list internally.
Notice that Queue.dequeue() sets tail to null when the last element is removed. Without this, tail would point to a removed node, creating a dangling reference and preventing garbage collection.
Browse the complete solution code and run it. Try modifying the code to experiment with the design.
Single Responsibility Principle
Open/Closed Principle
Liskov Substitution Principle
Interface Segregation Principle
Dependency Inversion Principle
In interviews, emphasize ISP by saying: 'Stack has push/pop/peek. Queue has enqueue/dequeue/peek. Neither exposes the other's operations. The shared Collection interface has only size(), isEmpty(), and iterator() - three methods that apply to every collection.'
Both Stack and Queue use a ReentrantLock to make every mutating operation atomic. The lock ensures that size checks, pointer updates, and element access happen as one indivisible operation. Here is a concrete double-pop race condition without locking:
For performance-critical paths, lock-free structures avoid the overhead of lock acquisition. The Treiber Stack uses AtomicReference and Compare-And-Swap (CAS):
If another thread modified top between the read and the CAS, compareAndSet fails and the loop retries. No lock is ever held, so no thread is ever blocked.
The Michael-Scott Queue uses CAS on both head and tail for a lock-free FIFO queue. These are foundational concurrent data structures used in java.util.concurrent.
A bounded Queue with a maximum capacity implements back-pressure. enqueue() blocks when full (producer slows down). dequeue() blocks when empty (consumer waits). This naturally throttles fast producers and prevents memory exhaustion. The BlockingQueue interface in Java's standard library is built on this pattern.
Junior: implement thread-safe Stack and Queue with ReentrantLock.
Mid-level: explain the Treiber Stack CAS loop and why it avoids ABA problems with immutable nodes.
Senior: compare lock-based, CAS-based, and LMAX Disruptor approaches and explain when each is appropriate.
Why fine-grained locking instead of a single global lock? A global lock serializes all operations - only one thread can do anything at a time. Per-resource locks let operations on different resources proceed in parallel, scaling throughput linearly with the number of independent resources.
Below is the class diagram for the Stack and Queue system.
Key points to highlight in an interview:
Priority Queue with Heap
Extend the Collection interface with a PriorityQueue backed by a binary heap. Elements are dequeued in priority order rather than insertion order. Useful for task scheduling (highest-priority task first) and event processing (earliest event first).
Double-Ended Queue (Deque)
Support insertion and removal at both ends. Deque can act as both a Stack (push/pop on one end) and a Queue (push on one end, pop on the other). The work-stealing algorithm in thread pools uses Deque: each thread has its own Deque and steals from other threads' Deques when idle.
Persistent (Immutable) Structures
Immutable Stack and Queue where push/enqueue returns a new instance sharing structure with the old one. The old version is still accessible. This enables safe sharing across threads without locks, undo via reference to the previous version, and functional programming patterns.
Array-Backed Implementations
Add ArrayStack and ArrayQueue using circular buffers for better cache locality. The circular buffer wraps indices modulo the array length, reusing space from dequeued elements. When full, the array doubles in size (amortized O(1)). These provide better performance for CPU-cache-sensitive workloads.
Monitoring and Metrics
Add size monitoring to detect unbounded growth. Alert when queue depth exceeds a threshold (indicates consumer lag). Track push/pop throughput for capacity planning. Expose metrics through JMX or Prometheus for production monitoring.
Reading a solution is not the same as producing one under interview pressure. Design it on the whiteboard and get scored feedback.
0%
Requirements
Define Core Objects
Analyze Relationships
Establish Hierarchy
Collection Interface
Node Class
Design Patterns
Iterator Pattern: Safe Traversal
Template Method: Common Collection Operations
Producer-Consumer with Blocking Queue
Define Class Members / Write Code
Stack with Thread Safety
Queue with Thread Safety
Run and Test
Adhere to SOLID Guidelines
Consider Scalability and Flexibility
Lock-Based Thread Safety
Lock-Free Alternatives
Bounded Queue for Back-Pressure
Create/Explain Your Diagrams
Future Improvements