Java Stack and Queue — LIFO and FIFO Structures

Stacks (LIFO) and queues (FIFO) are fundamental data structures. Java provides them through the Queue and Deque interfaces, with ArrayDeque as the go-to implementation for both.

---

Queue Interface (FIFO)

A queue is like a line at a store — first in, first out.

offer("A") → [A]
offer("B") → [A, B]
offer("C") → [A, B, C]
poll()     → "A"  →  [B, C]
poll()     → "B"  →  [C]

Two Sets of Methods

Operation	Throws Exception	Returns Special Value
Insert	add(e) → IllegalStateException	offer(e) → false
Remove	remove() → NoSuchElementException	poll() → null
Examine	element() → NoSuchElementException	peek() → null

Prefer offer(), poll(), peek() — they return null/false instead of throwing.

Queue Example

Queue<String> queue = new LinkedList<>();
queue.offer("Task 1");
queue.offer("Task 2");
queue.offer("Task 3");

while (!queue.isEmpty()) {
    String task = queue.poll();
    System.out.println("Processing: " + task);
}
// Processing: Task 1
// Processing: Task 2
// Processing: Task 3

---

The Legacy Stack Class

Stack<String> stack = new Stack<>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.pop();   // "C"
stack.peek();  // "B"

Don’t use Stack. It extends Vector (synchronized, slow), and exposes List methods like get(0) that break the stack abstraction. Use Deque instead.

---

Deque as Stack and Queue

Deque (double-ended queue) supports operations at both ends — making it usable as both a stack and a queue:

     ┌───────────────────────────────┐
     │   offerFirst()  ←  → offerLast()   │
     │   pollFirst()   ←  → pollLast()    │
     │   peekFirst()   ←  → peekLast()    │
     │ ┌───┬───┬───┬───┬───┐             │
     │ │ A │ B │ C │ D │ E │             │
     │ └───┴───┴───┴───┴───┘             │
     │  head                  tail        │
     └───────────────────────────────┘

Deque as Stack (LIFO)

Deque<String> stack = new ArrayDeque<>();
stack.push("Bottom");   // pushes to head
stack.push("Middle");
stack.push("Top");

stack.pop();    // "Top"
stack.peek();   // "Middle"

Stack Operation	Deque Method
Push	push(e) / offerFirst(e)
Pop	pop() / pollFirst()
Peek	peek() / peekFirst()

Deque as Queue (FIFO)

Deque<String> queue = new ArrayDeque<>();
queue.offer("First");    // adds to tail
queue.offer("Second");
queue.offer("Third");

queue.poll();   // "First" — removes from head
queue.peek();   // "Second"

Queue Operation	Deque Method
Enqueue	offer(e) / offerLast(e)
Dequeue	poll() / pollFirst()
Peek	peek() / peekFirst()

---

ArrayDeque — The Recommended Implementation

ArrayDeque is backed by a circular resizable array:

Circular array (capacity 8):
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
  │   │   │ A │ B │ C │ D │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
            ↑               ↑
           head            tail

offerFirst("Z"):
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
  │   │ Z │ A │ B │ C │ D │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘
        ↑                   ↑
       head                tail

Why ArrayDeque Over LinkedList?

Factor	ArrayDeque	LinkedList
Memory	Compact array	Node objects (~5×)
Cache locality	Excellent	Poor
Throughput	Faster	Slower
Null elements	❌ Not allowed	✅ Allowed
As List	❌ Not a List	✅ Also a List

Use ArrayDeque for all stack and queue needs. Use LinkedList only if you need null elements or List interface.

---

Real-World Use Cases

1. Task Queue (Job Processing)

Queue<Runnable> taskQueue = new ArrayDeque<>();
taskQueue.offer(() -> sendEmail("alice@example.com"));
taskQueue.offer(() -> generateReport("Q4"));
taskQueue.offer(() -> cleanupTempFiles());

while (!taskQueue.isEmpty()) {
    Runnable task = taskQueue.poll();
    task.run();
}

2. Undo Functionality (Stack)

Deque<String> undoStack = new ArrayDeque<>();

public void performAction(String action) {
    undoStack.push(action);
    execute(action);
}

public void undo() {
    if (!undoStack.isEmpty()) {
        String lastAction = undoStack.pop();
        reverse(lastAction);
    }
}

3. BFS — Breadth-First Search

public List<String> bfs(TreeNode root) {
    List<String> result = new ArrayList<>();
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        result.add(node.value);

        if (node.left != null)  queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return result;
}

4. Bracket Matching (Stack)

public boolean isBalanced(String expression) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

    for (char c : expression.toCharArray()) {
        if ("([{".indexOf(c) >= 0) {
            stack.push(c);
        } else if (pairs.containsKey(c)) {
            if (stack.isEmpty() || !stack.pop().equals(pairs.get(c))) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

---

Big-O Summary

Operation	ArrayDeque	LinkedList (as Deque)
offerFirst / offerLast	O(1) amortized	O(1)
pollFirst / pollLast	O(1)	O(1)
peekFirst / peekLast	O(1)	O(1)
contains	O(n)	O(n)
Memory per element	~8 bytes	~40 bytes

---

Choosing the Right Structure

Need FIFO (first-in, first-out)?
└── Use Queue → ArrayDeque

Need LIFO (last-in, first-out)?
└── Use Deque as stack → ArrayDeque

Need priority ordering?
└── Use PriorityQueue

Need thread-safe queue?
└── Use ConcurrentLinkedQueue or BlockingQueue

Need the legacy Stack class?
└── No. Use ArrayDeque.

---

Key Takeaways

1. Queue = FIFO; use offer(), poll(), peek().
2. Deque = double-ended; works as both stack and queue.
3. ArrayDeque is the best implementation for both — fast, memory-efficient.
4. Never use Stack — it’s legacy and extends Vector.
5. Use push()/pop() for stack behaviour, offer()/poll() for queue behaviour.

---

What’s Next?

Next: Set Interface — collections with no duplicates, backed by HashSet, LinkedHashSet, and TreeSet.