Definition
- 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.
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());
}
}
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.
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());
}
}
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.
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());
}
}
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?
| Feature | Stack (LIFO) | Queue (FIFO) | Deque |
|---|---|---|---|
| Add | push (top) | offer (tail) | addFirst / addLast |
| Remove | pop (top) | poll (head) | removeFirst / removeLast |
| Peek | peek (top) | peek (head) | peekFirst / peekLast |
| Order | Last in, first out | First in, first out | Both ends |
| Java class | ArrayDeque | ArrayDeque or LinkedList | ArrayDeque |
| Use case | Undo history, expression parsing | Task queues, BFS | Sliding window, work stealing |
| Legacy class | java.util.Stack (avoid) | None | None |
| Thread-safe | N/A (use ConcurrentLinkedDeque) | ConcurrentLinkedQueue | ConcurrentLinkedDeque |
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());
}
}
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
bank-queue-service/ ├── src/ │ └── main/ │ └── java/ │ └── com/ │ └── bank/ │ └── core/ │ ├── Customer.java │ ├── UndoTransactionStack.java │ ├── CustomerServiceQueue.java │ ├── VipPriorityQueue.java │ └── BankQueueApp.java └── run.sh
Customer.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
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
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
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
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
javac -d out src/main/java/com/bank/core/*.java
java -cp out com.bank.core.BankQueueApp
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
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)");
}
}
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
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());
}
}
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.
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");
}
}
}
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.
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");
}
}
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:
ArrayBlockingQueueis bounded (prevents memory overflow).ConcurrentLinkedQueueis 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:
ForkJoinPooluses 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.
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"));
}
}
}
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
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.
---