Back to Stacks & Queues
Q1Question 1 of 1

What are stacks, queues, and deques in Java

Answer: A stack is a LIFO collection where the last element added is the first removed, a queue is a FIFO collection where the first element added is the first removed, and a deque supports both operations at both ends.

Key Concepts
  • A stack follows Last-In-First-Out (LIFO) order: the most recently added element is removed first.
  • A queue follows First-In-First-Out (FIFO) order: the earliest added element is removed first.
  • A deque (double-ended queue) supports insertion and removal at both ends in O(1) time.
  • In Java, use ArrayDeque as the default implementation for both stacks and queues instead of the legacy Stack class or LinkedList.
  • PriorityQueue orders elements by natural ordering or a Comparator, not by insertion order, giving O(log n) insertion and O(1) peek.
  • The legacy Stack class extends Vector and is synchronized, making it slower than ArrayDeque for single-threaded code.
  • For thread-safe queues in production, use ConcurrentLinkedQueue (non-blocking) or LinkedBlockingQueue (blocking).

Definition

A stack is a LIFO collection where the last element added is the first removed, a queue is a FIFO collection where the first element added is the first removed, and a deque supports both operations at both ends.
  • Stack is a LIFO (Last-In, First-Out) data structure with push (add to top) and pop (remove from top) operations, both in O(1) time.
  • Queue is a FIFO (First-In, First-Out) data structure with offer (add to tail) and poll (remove from head) operations, both in O(1) time.
  • Deque (double-ended queue) supports adding and removing elements at both the front and the back in O(1) time; ArrayDeque is the standard implementation.
  • PriorityQueue is a queue that orders elements by priority (natural order or Comparator) rather than insertion order, backed by a binary heap.
  • ArrayDeque is the recommended replacement for both java.util.Stack and LinkedList-as-queue; it uses a resizable circular array with no synchronization overhead.

At National Bank of India, think of a stack as a pile of cheque books in Rajesh's desk drawer: he always picks the one on top (LIFO). A queue is the customer line at the teller window: Priya, who arrived first, gets served first (FIFO). A deque is the express counter where VIP customers can join at the front while regular customers join at the back. A priority queue is the loan approval desk where applications are processed by loan amount (highest first), not by arrival time.

Understanding the Concepts

What is a stack and how does LIFO work?

A stack stores elements in Last-In-First-Out order. The three core operations are push (add to top), pop (remove from top), and peek (look at top without removing). All three are O(1).

In Java, use ArrayDeque as a stack. The legacy Stack class extends Vector and is synchronized, making it slower.

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.Deque;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();

        // Push transactions onto the undo stack
        undoStack.push("Deposit 50000 INR to SAV2001");
        undoStack.push("Transfer 20000 INR to CUR3001");
        undoStack.push("Withdraw 5000 INR from SAV2001");

        System.out.println("Undo stack (top first):");
        for (var txn : undoStack) {
            System.out.println("  " + txn);
        }

        // Pop: undo the most recent transaction
        String undone = undoStack.pop();
        System.out.println("\nUndone: " + undone);
        System.out.println("Peek (next to undo): " + undoStack.peek());
        System.out.println("Stack size: " + undoStack.size());
    }
}
TEXT
Expected output:
Undo stack (top first):
  Withdraw 5000 INR from SAV2001
  Transfer 20000 INR to CUR3001
  Deposit 50000 INR to SAV2001

Undone: Withdraw 5000 INR from SAV2001
Peek (next to undo): Transfer 20000 INR to CUR3001
Stack size: 2

What is a queue and how does FIFO work?

A queue stores elements in First-In-First-Out order. The three core operations are offer (add to tail), poll (remove from head), and peek (look at head without removing). All three are O(1).

In Java, use ArrayDeque or LinkedList as a Queue. For production, use ConcurrentLinkedQueue for thread safety.

JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> customerQueue = new ArrayDeque<>();

        // Customers arrive (FIFO)
        customerQueue.offer("Priya (SAV2001) - balance inquiry");
        customerQueue.offer("Rajesh (CUR3001) - loan application");
        customerQueue.offer("Pankaj (SAV2002) - cheque deposit");

        System.out.println("Customer service queue:");
        System.out.println("  Queue size: " + customerQueue.size());
        System.out.println("  Next: " + customerQueue.peek());

        // Serve customers in order
        System.out.println("\nServing customers:");
        while (!customerQueue.isEmpty()) {
            System.out.println("  Serving: " + customerQueue.poll());
        }
        System.out.println("Queue empty: " + customerQueue.isEmpty());
    }
}
TEXT
Expected output:
Customer service queue:
  Queue size: 3
  Next: Priya (SAV2001) - balance inquiry

Serving customers:
  Serving: Priya (SAV2001) - balance inquiry
  Serving: Rajesh (CUR3001) - loan application
  Serving: Pankaj (SAV2002) - cheque deposit
Queue empty: true

What is a deque and how do double-ended operations work?

A deque (double-ended queue) supports insertion and removal at both the front and the back. ArrayDeque uses a circular array internally, giving O(1) amortized time for all operations at both ends.

Deque methods: addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast.

JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Add at both ends
        deque.addLast("Regular: Rajesh - deposit");
        deque.addLast("Regular: Priya - withdrawal");
        deque.addFirst("VIP: Pankaj - loan approval"); // VIP jumps to front

        System.out.println("Bank service deque:");
        for (var item : deque) {
            System.out.println("  " + item);
        }

        // Remove from both ends
        System.out.println("\nServe from front: " + deque.removeFirst());
        System.out.println("Cancel from back:  " + deque.removeLast());
        System.out.println("Remaining: " + deque.peekFirst());
        System.out.println("Size: " + deque.size());
    }
}
TEXT
Expected output:
Bank service deque:
  VIP: Pankaj - loan approval
  Regular: Rajesh - deposit
  Regular: Priya - withdrawal

Serve from front: VIP: Pankaj - loan approval
Cancel from back:  Regular: Priya - withdrawal
Remaining: Regular: Rajesh - deposit
Size: 1

How are Stack, Queue, and Deque different?

FeatureStack (LIFO)Queue (FIFO)Deque
Addpush (top)offer (tail)addFirst / addLast
Removepop (top)poll (head)removeFirst / removeLast
Peekpeek (top)peek (head)peekFirst / peekLast
OrderLast in, first outFirst in, first outBoth ends
Java classArrayDequeArrayDeque or LinkedListArrayDeque
Use caseUndo history, expression parsingTask queues, BFSSliding window, work stealing
Legacy classjava.util.Stack (avoid)NoneNone
Thread-safeN/A (use ConcurrentLinkedDeque)ConcurrentLinkedQueueConcurrentLinkedDeque
JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class StackVsQueueVsDeque {
    public static void main(String[] args) {
        // Same data, different retrieval order
        String[] transactions = {"T1: 10000", "T2: 25000", "T3: 5000"};

        // Stack (LIFO)
        Deque<String> stack = new ArrayDeque<>();
        for (var t : transactions) stack.push(t);
        System.out.println("Stack (LIFO): " + stack.pop() + ", " + stack.pop() + ", " + stack.pop());

        // Queue (FIFO)
        Queue<String> queue = new ArrayDeque<>();
        for (var t : transactions) queue.offer(t);
        System.out.println("Queue (FIFO): " + queue.poll() + ", " + queue.poll() + ", " + queue.poll());

        // Deque (both ends)
        Deque<String> deque = new ArrayDeque<>();
        for (var t : transactions) deque.addLast(t);
        System.out.println("Deque front:  " + deque.removeFirst());
        System.out.println("Deque back:   " + deque.removeLast());
    }
}
TEXT
Expected output:
Stack (LIFO): T3: 5000, T2: 25000, T1: 10000
Queue (FIFO): T1: 10000, T2: 25000, T3: 5000
Deque front:  T1: 10000
Deque back:   T3: 5000

What is a complete banking project using stacks, queues, and priority queues?

This project implements an undo transaction stack, a customer service queue, and a VIP priority queue for National Bank of India.

Project structure

DIAGRAM
bank-queue-service/
├── src/
│   └── main/
│       └── java/
│           └── com/
│               └── bank/
│                   └── core/
│                       ├── Customer.java
│                       ├── UndoTransactionStack.java
│                       ├── CustomerServiceQueue.java
│                       ├── VipPriorityQueue.java
│                       └── BankQueueApp.java
└── run.sh

Customer.java

JAVA
package com.bank.core;

import java.math.BigDecimal;

public record Customer(String name, String accountId, BigDecimal balance, boolean isVip) implements Comparable<Customer> {

    @Override
    public int compareTo(Customer other) {
        // VIP first, then by balance descending
        if (this.isVip != other.isVip) return this.isVip ? -1 : 1;
        return other.balance.compareTo(this.balance);
    }

    @Override
    public String toString() {
        return name + " (" + accountId + ") " + balance + " INR" + (isVip ? " [VIP]" : "");
    }
}

UndoTransactionStack.java

JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.Deque;

public class UndoTransactionStack {
    private final Deque<String> stack = new ArrayDeque<>();

    public void execute(String transaction) {
        stack.push(transaction);
        System.out.println("  Executed: " + transaction);
    }

    public String undo() {
        if (stack.isEmpty()) return "Nothing to undo";
        return "Undone: " + stack.pop();
    }

    public int size() { return stack.size(); }
}

CustomerServiceQueue.java

JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.Queue;

public class CustomerServiceQueue {
    private final Queue<String> queue = new ArrayDeque<>();

    public void arrive(String customer) {
        queue.offer(customer);
    }

    public String serve() {
        return queue.poll();
    }

    public int waiting() { return queue.size(); }
}

VipPriorityQueue.java

JAVA
package com.bank.core;

import java.util.PriorityQueue;

public class VipPriorityQueue {
    private final PriorityQueue<Customer> pq = new PriorityQueue<>();

    public void add(Customer customer) {
        pq.offer(customer);
    }

    public Customer serveNext() {
        return pq.poll();
    }

    public int waiting() { return pq.size(); }
}

BankQueueApp.java

JAVA
package com.bank.core;

import java.math.BigDecimal;

public class BankQueueApp {
    public static void main(String[] args) {
        System.out.println("=== National Bank of India: Queue Services ===");

        // 1. Undo stack
        System.out.println("\n--- Undo Transaction Stack ---");
        var undoStack = new UndoTransactionStack();
        undoStack.execute("Deposit 50000 INR to SAV2001");
        undoStack.execute("Transfer 20000 INR to CUR3001");
        undoStack.execute("Withdraw 5000 INR from SAV2001");
        System.out.println("  " + undoStack.undo());
        System.out.println("  " + undoStack.undo());
        System.out.println("  Remaining in stack: " + undoStack.size());

        // 2. Customer service queue
        System.out.println("\n--- Customer Service Queue (FIFO) ---");
        var serviceQueue = new CustomerServiceQueue();
        serviceQueue.arrive("Priya (SAV2001)");
        serviceQueue.arrive("Rajesh (CUR3001)");
        serviceQueue.arrive("Pankaj (SAV2002)");
        System.out.println("  Serving: " + serviceQueue.serve());
        System.out.println("  Serving: " + serviceQueue.serve());
        System.out.println("  Waiting: " + serviceQueue.waiting());

        // 3. VIP priority queue
        System.out.println("\n--- VIP Priority Queue ---");
        var vipQueue = new VipPriorityQueue();
        vipQueue.add(new Customer("Priya", "SAV2001", new BigDecimal("150000"), false));
        vipQueue.add(new Customer("Rajesh", "CUR3001", new BigDecimal("500000"), false));
        vipQueue.add(new Customer("Pankaj", "SAV2002", new BigDecimal("75000"), true));
        System.out.println("  Serve: " + vipQueue.serveNext());
        System.out.println("  Serve: " + vipQueue.serveNext());
        System.out.println("  Serve: " + vipQueue.serveNext());
    }
}

How to compile and run

BASH
javac -d out src/main/java/com/bank/core/*.java
java -cp out com.bank.core.BankQueueApp
TEXT
Expected output:
=== National Bank of India: Queue Services ===

--- Undo Transaction Stack ---
  Executed: Deposit 50000 INR to SAV2001
  Executed: Transfer 20000 INR to CUR3001
  Executed: Withdraw 5000 INR from SAV2001
  Undone: Withdraw 5000 INR from SAV2001
  Undone: Transfer 20000 INR to CUR3001
  Remaining in stack: 1

--- Customer Service Queue (FIFO) ---
  Serving: Priya (SAV2001)
  Serving: Rajesh (CUR3001)
  Waiting: 1

--- VIP Priority Queue ---
  Serve: Pankaj (SAV2002) 75000 INR [VIP]
  Serve: Rajesh (CUR3001) 500000 INR
  Serve: Priya (SAV2001) 150000 INR

What are common mistakes with stacks and queues?

The most common mistake is using the legacy Stack class instead of ArrayDeque. Another mistake is calling pop() or poll() without checking if the collection is empty.

Wrong: using legacy Stack class

JAVA
package com.bank.core;

import java.util.Stack;

public class WrongLegacyStack {
    public static void main(String[] args) {
        // BAD: Stack extends Vector, every method is synchronized
        Stack<String> stack = new Stack<>();
        stack.push("Deposit 10000 INR");
        stack.push("Withdraw 5000 INR");

        System.out.println("Legacy Stack (WRONG):");
        System.out.println("  Class: " + stack.getClass().getName());
        System.out.println("  Problem: extends Vector, synchronized, allows random access");
        System.out.println("  stack.get(0): " + stack.get(0) + " (breaks LIFO contract)");
    }
}
TEXT
Expected output:
Legacy Stack (WRONG):
  Class: java.util.Stack
  Problem: extends Vector, synchronized, allows random access
  stack.get(0): Deposit 10000 INR (breaks LIFO contract)

Correct: use ArrayDeque as a stack

JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.Deque;

public class CorrectArrayDequeStack {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Deposit 10000 INR");
        stack.push("Withdraw 5000 INR");

        System.out.println("ArrayDeque as Stack (CORRECT):");
        System.out.println("  Class: " + stack.getClass().getName());
        System.out.println("  No synchronization overhead");
        System.out.println("  No random access (enforces LIFO contract)");
        System.out.println("  Pop: " + stack.pop());
        System.out.println("  Pop: " + stack.pop());
    }
}
TEXT
Expected output:
ArrayDeque as Stack (CORRECT):
  Class: java.util.ArrayDeque
  No synchronization overhead
  No random access (enforces LIFO contract)
  Pop: Withdraw 5000 INR
  Pop: Deposit 10000 INR

What about PriorityQueue?

PriorityQueue orders elements by their natural ordering (Comparable) or a custom Comparator, not by insertion order. Internally it uses a binary min-heap. Insertion is O(log n). Peek is O(1). Poll (remove min) is O(log n).

In banking, PriorityQueue is useful for processing high-value transactions first, serving VIP customers before regular ones, or scheduling loan approvals by urgency.

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueDemo {

    record LoanApplication(String accountId, String name, BigDecimal amount) {}

    public static void main(String[] args) {
        // Process highest loan amount first
        var pq = new PriorityQueue<LoanApplication>(
            Comparator.comparing(LoanApplication::amount).reversed());

        pq.offer(new LoanApplication("SAV2001", "Rajesh", new BigDecimal("500000")));
        pq.offer(new LoanApplication("CUR3001", "Priya", new BigDecimal("2000000")));
        pq.offer(new LoanApplication("SAV2002", "Pankaj", new BigDecimal("100000")));

        System.out.println("Loan applications (highest amount first):");
        while (!pq.isEmpty()) {
            var app = pq.poll();
            System.out.println("  " + app.name() + " (" + app.accountId() + "): " + app.amount() + " INR");
        }
    }
}
TEXT
Expected output:
Loan applications (highest amount first):
  Priya (CUR3001): 2000000 INR
  Rajesh (SAV2001): 500000 INR
  Pankaj (SAV2002): 100000 INR

What about thread safety?

ArrayDeque, ArrayList, and PriorityQueue are not thread-safe. For concurrent access, Java provides thread-safe queue implementations:

  • ConcurrentLinkedQueue: non-blocking, lock-free FIFO queue.
  • LinkedBlockingQueue: blocking queue used in producer-consumer patterns.
  • ConcurrentLinkedDeque: non-blocking deque.
  • ArrayBlockingQueue: bounded blocking queue.
JAVA
package com.bank.core;

import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;

public class ConcurrentQueueDemo {
    public static void main(String[] args) throws InterruptedException {
        var queue = new ConcurrentLinkedQueue<String>();
        var latch = new CountDownLatch(2);

        // Producer thread
        Thread.ofVirtual().start(() -> {
            for (int i = 1; i <= 5; i++) {
                queue.offer("TXN-" + i + " from SAV2001");
            }
            latch.countDown();
        });

        // Another producer
        Thread.ofVirtual().start(() -> {
            for (int i = 6; i <= 10; i++) {
                queue.offer("TXN-" + i + " from CUR3001");
            }
            latch.countDown();
        });

        latch.await();
        System.out.println("ConcurrentLinkedQueue results:");
        System.out.println("  Total enqueued: " + queue.size());
        System.out.println("  First: " + queue.poll());
        System.out.println("  No data corruption, no locks needed");
    }
}
TEXT
Expected output:
ConcurrentLinkedQueue results:
  Total enqueued: 10
  First: TXN-1 from SAV2001
  No data corruption, no locks needed

What should a senior or principal engineer know?

At the senior level, you should choose the right queue implementation for your use case and understand the performance characteristics.

At the principal level, consider:

  • Bounded vs unbounded: ArrayBlockingQueue is bounded (prevents memory overflow). ConcurrentLinkedQueue is unbounded (can grow until OOM).
  • Backpressure: in producer-consumer systems, use a bounded BlockingQueue so producers block when the queue is full.
  • Work-stealing deques: ForkJoinPool uses work-stealing deques internally. Each thread has a local deque; idle threads steal from the tail of other threads' deques.
  • Monotonic stacks: used in interview problems for finding next-greater-element, stock span, and histogram problems.
  • Queue-based BFS: breadth-first search uses a FIFO queue. Level-order tree traversal also uses a queue.
JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.Deque;

public class SeniorQueueKnowledge {

    // Monotonic stack: find next greater transaction amount
    public static int[] nextGreaterAmount(int[] amounts) {
        int n = amounts.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>(); // stores indices

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && amounts[stack.peek()] <= amounts[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : amounts[stack.peek()];
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] amounts = {50000, 30000, 80000, 20000, 90000};

        System.out.println("Senior/Principal queue checklist:");
        System.out.println("  1. Use ArrayDeque (not Stack) for LIFO");
        System.out.println("  2. Use ArrayBlockingQueue for bounded producer-consumer");
        System.out.println("  3. ForkJoinPool uses work-stealing deques internally");
        System.out.println("  4. Monotonic stacks for next-greater-element problems");
        System.out.println("  5. BFS always uses a FIFO queue");

        System.out.println("\nNext greater transaction amount:");
        int[] nextGreater = nextGreaterAmount(amounts);
        for (int i = 0; i < amounts.length; i++) {
            System.out.println("  " + amounts[i] + " INR -> next greater: " + (nextGreater[i] == -1 ? "none" : nextGreater[i] + " INR"));
        }
    }
}
TEXT
Expected output:
Senior/Principal queue checklist:
  1. Use ArrayDeque (not Stack) for LIFO
  2. Use ArrayBlockingQueue for bounded producer-consumer
  3. ForkJoinPool uses work-stealing deques internally
  4. Monotonic stacks for next-greater-element problems
  5. BFS always uses a FIFO queue

Next greater transaction amount:
  50000 INR -> next greater: 80000 INR
  30000 INR -> next greater: 80000 INR
  80000 INR -> next greater: 90000 INR
  20000 INR -> next greater: 90000 INR
  90000 INR -> next greater: none

What are common interview follow-up questions?

  • How do you implement a stack using two queues? (Push: enqueue to queue2, then move all from queue1 to queue2, swap names. Pop: dequeue from queue1.)
  • How do you implement a queue using two stacks? (Enqueue: push to stack1. Dequeue: if stack2 is empty, pop all from stack1 to stack2, then pop from stack2.)
  • What is the difference between offer/poll and add/remove? (offer/poll return null or false on failure. add/remove throw exceptions on failure.)
  • When should you use PriorityQueue over a sorted TreeSet? (PriorityQueue gives O(1) peek for the min element and O(log n) insertion. TreeSet gives O(log n) for everything but supports range queries and sorted iteration.)
  • What is a circular buffer and how does ArrayDeque implement it? (ArrayDeque uses a circular array with head and tail indices that wrap around. When the array is full, it doubles in size.)
  • How does BFS use a queue? (Start at the source, add to queue. While queue is not empty, poll, process, and offer all unvisited neighbors.)

Visual Overview

DIAGRAM
 Stack (LIFO)                  Queue (FIFO)
 ============                  ============

     push ──> ┌───┐            offer ──> ┌───┐┌───┐┌───┐ ──> poll
              │ C │  <── top              │ A ││ B ││ C │
              ├───┤                       └───┘└───┘└───┘
              │ B │              head ──────^              ^── tail
              ├───┤
              │ A │
              └───┘

     pop  <── top               poll <── head
     (C out first)              (A out first)


 Deque (Double-Ended Queue)
 ===========================

  addFirst ──> ┌───┐┌───┐┌───┐ <── addLast
               │ C ││ A ││ B │
               └───┘└───┘└───┘
  removeFirst ──^              ^── removeLast


 PriorityQueue (Min-Heap)
 =========================

  offer(50000)  offer(20000)  offer(80000)

  Internal binary heap:
            20000
           /     \
       50000    80000

  poll() returns 20000 (smallest)

            50000
           /
       80000

Key Takeaway

Stacks, queues, and deques are fundamental data structures that control the order in which elements are added and removed. A stack uses LIFO order (last in, first out), a queue uses FIFO order (first in, first out), and a deque supports operations at both ends.

In Java, ArrayDeque is the recommended implementation for both stacks and queues. It uses a circular resizable array, has no synchronization overhead, and outperforms both the legacy Stack class (which extends Vector) and LinkedList (which has pointer-chasing overhead). The legacy Stack class should never be used in new code.

PriorityQueue is a special queue that orders elements by priority rather than insertion order. It uses a binary min-heap internally, giving O(1) peek and O(log n) insert/remove. In our National Bank of India project, we used PriorityQueue to serve VIP customers and high-value loan applications before regular ones.

For production systems with concurrent access, use ConcurrentLinkedQueue (non-blocking FIFO), LinkedBlockingQueue (blocking producer-consumer), or ConcurrentLinkedDeque. A bounded BlockingQueue provides backpressure so producers block when the queue is full, preventing out-of-memory errors.

At the senior level, understand monotonic stacks (used in next-greater-element and histogram problems), work-stealing deques (used internally by ForkJoinPool), and the difference between bounded and unbounded queues. In coding interviews, be ready to implement a queue with two stacks or a stack with two queues.

Remember one sentence: use ArrayDeque for both stacks and queues, PriorityQueue when order is by priority not arrival, and ConcurrentLinkedQueue or BlockingQueue when multiple threads share the queue.

---

Share