Master linear data structures with LIFO and FIFO ordering. Learn implementations, classic applications, and interview-winning patterns with complete C# solutions.
A stack is a Last-In-First-Out (LIFO) data structure where elements are added and removed from the same end, called the top. The last element pushed is the first one to be popped.
Imagine a stack of plates in a restaurant: you place plates on top of the stack, and when you need a plate, you take from the top. The plate added last is the one you grab first. This fundamental principle makes stacks invaluable for problems involving backtracking, undo operations, and expression evaluation.
Inserts a new element at the top of the stack. This operation simply adds the element and updates the top pointer.
Removes the element at the top of the stack and returns it. If the stack is empty, this operation may throw an exception or return a sentinel value.
Inspects the top element of the stack without modifying it. Useful for checking the next element to be processed.
Returns a boolean indicating whether the stack is empty. Essential for loop termination conditions.
Here's how a stack evolves with push and pop operations:
Stacks can be implemented using arrays (fixed or dynamic) or linked lists. Each approach has trade-offs in terms of memory and access patterns.
Using a dynamic array (List in C#) provides cache-friendly access and is the most common implementation.
public class ArrayStack<T> { private List<T> items = new List<T>(); // Push: Add element to the top public void Push(T item) { items.Add(item); } // Pop: Remove and return top element public T Pop() { if (items.Count == 0) throw new InvalidOperationException("Stack is empty"); T item = items[items.Count - 1]; items.RemoveAt(items.Count - 1); return item; } // Peek: Return top element without removing public T Peek() { if (items.Count == 0) throw new InvalidOperationException("Stack is empty"); return items[items.Count - 1]; } // IsEmpty: Check if stack is empty public bool IsEmpty() => items.Count == 0; // Size: Get number of elements public int Size() => items.Count; }
Using a linked list avoids array resizing but trades cache locality for dynamic memory.
public class Node<T> { public T Data { get; set; } public Node<T> Next { get; set; } public Node(T data) { Data = data; Next = null; } } public class LinkedListStack<T> { private Node<T> top = null; private int size = 0; public void Push(T item) { Node<T> newNode = new Node<T>(item); newNode.Next = top; top = newNode; size++; } public T Pop() { if (top == null) throw new InvalidOperationException("Stack is empty"); T data = top.Data; top = top.Next; size--; return data; } public T Peek() { if (top == null) throw new InvalidOperationException("Stack is empty"); return top.Data; } public bool IsEmpty() => top == null; public int Size() => size; }
A queue is a First-In-First-Out (FIFO) data structure where elements are added at the rear and removed from the front. The first element enqueued is the first one to be dequeued.
Imagine waiting in line at a coffee shop: the first person in line is the first to be served, and new customers join at the back of the line. This ordering makes queues perfect for task scheduling, breadth-first search, and buffering operations where fairness is important.
Inserts a new element at the rear (back) of the queue. This operation updates the rear pointer.
Removes the element at the front of the queue and returns it. Essential for processing queued items.
Inspects the front element of the queue without modifying it.
Returns a boolean indicating whether the queue is empty.
Here's how a queue evolves with enqueue and dequeue operations:
Queues are typically implemented using circular arrays (most efficient) or linked lists. The circular array approach avoids the O(n) cost of shifting elements.
A circular buffer reuses array space by treating the array as circular, eliminating the need to shift elements on dequeue.
public class CircularQueue<T> { private T[] items; private int front = 0; private int rear = -1; private int size = 0; private int capacity; public CircularQueue(int capacity) { this.capacity = capacity; items = new T[capacity]; } // Enqueue: Add element at rear public void Enqueue(T item) { if (size == capacity) Resize(); rear = (rear + 1) % capacity; items[rear] = item; size++; } // Dequeue: Remove element from front public T Dequeue() { if (size == 0) throw new InvalidOperationException("Queue is empty"); T item = items[front]; front = (front + 1) % capacity; size--; return item; } // Peek: Return front element public T Peek() { if (size == 0) throw new InvalidOperationException("Queue is empty"); return items[front]; } public bool IsEmpty() => size == 0; private void Resize() { T[] newItems = new T[capacity * 2]; for (int i = 0; i < size; i++) { newItems[i] = items[(front + i) % capacity]; } items = newItems; front = 0; rear = size - 1; capacity *= 2; } }
Using a linked list with front and rear pointers provides clean semantics without circular logic.
public class LinkedListQueue<T> { private Node<T> front = null; private Node<T> rear = null; private int size = 0; public void Enqueue(T item) { Node<T> newNode = new Node<T>(item); if (rear == null) { front = rear = newNode; } else { rear.Next = newNode; rear = newNode; } size++; } public T Dequeue() { if (front == null) throw new InvalidOperationException("Queue is empty"); T data = front.Data; front = front.Next; if (front == null) rear = null; size--; return data; } public T Peek() { if (front == null) throw new InvalidOperationException("Queue is empty"); return front.Data; } public bool IsEmpty() => front == null; public int Size() => size; }
A deque allows insertion and removal from both ends, combining the flexibility of stacks and queues. It's useful for sliding window problems and implementing both stack and queue semantics.
A deque supports eight operations: push/pop from the front, push/pop from the rear, peek at both ends, and check if empty.
public class Deque<T> { private LinkedList<T> items = new LinkedList<T>(); // Front operations public void PushFront(T item) => items.AddFirst(item); public T PopFront() { if (items.Count == 0) throw new InvalidOperationException(); T val = items.First.Value; items.RemoveFirst(); return val; } public T PeekFront() { if (items.Count == 0) throw new InvalidOperationException(); return items.First.Value; } // Rear operations public void PushRear(T item) => items.AddLast(item); public T PopRear() { if (items.Count == 0) throw new InvalidOperationException(); T val = items.Last.Value; items.RemoveLast(); return val; } public T PeekRear() { if (items.Count == 0) throw new InvalidOperationException(); return items.Last.Value; } public bool IsEmpty() => items.Count == 0; public int Size() => items.Count; }
Deque<T> class doesn't exist in the standard library, but LinkedList<T> provides all deque operations efficiently via AddFirst, AddLast, RemoveFirst, RemoveLast.
A priority queue is an abstract data type where each element has an associated priority. Elements with higher priority are dequeued before those with lower priority, regardless of insertion order.
C# 10+ provides a built-in PriorityQueue<TElement, TPriority> class (not a heap, but a priority queue implementation).
// Using C# 10+ PriorityQueue PriorityQueue<string, int> pq = new(); // Lower priority value = higher priority (dequeued first) pq.Enqueue("High", 1); pq.Enqueue("Low", 10); pq.Enqueue("Medium", 5); while (pq.Count > 0) { var (item, priority) = pq.DequeueWithPriority(); Console.WriteLine($"{item}: {priority}"); // Output: High: 1, Medium: 5, Low: 10 } // For max-heap (higher value = higher priority), negate PriorityQueue<int, int> maxHeap = new(); maxHeap.Enqueue(5, -5); // Negate for max-heap maxHeap.Enqueue(10, -10); maxHeap.Dequeue(); // Returns 10
A monotonic data structure maintains elements in a specific order (increasing or decreasing). These patterns solve problems involving next greater/smaller elements and sliding window extrema in linear time.
A monotonic stack maintains elements in increasing or decreasing order. When a new element violates the order, we pop elements until the order is restored, processing each popped element.
// Template: Monotonic Increasing Stack // Process array and maintain indices in increasing order by value public int[] NextGreaterElement(int[] nums) { var result = new int[nums.Length]; var stack = new Stack<int>(); // Store indices // Process array from right to left for "next greater" for (int i = nums.Length - 1; i >= 0; i--) { // Pop elements smaller than current (maintain decreasing order) while (stack.Count > 0 && nums[stack.Peek()] < nums[i]) { stack.Pop(); } // Stack top is next greater (or -1 if none) result[i] = stack.Count == 0 ? -1 : nums[stack.Peek()]; // Push current index stack.Push(i); } return result; }
A monotonic deque efficiently finds the maximum (or minimum) in every sliding window of size k in O(n) time.
// Template: Sliding Window Maximum using Monotonic Deque public int[] MaxSlidingWindow(int[] nums, int k) { if (nums.Length == 0) return new int[0]; var result = new int[nums.Length - k + 1]; var dq = new Deque<int>(); // Store indices in decreasing order for (int i = 0; i < nums.Length; i++) { // Remove elements outside window if (dq.Count > 0 && dq.PeekFront() < i - k + 1) dq.PopFront(); // Remove smaller elements from back (maintain decreasing) while (dq.Count > 0 && nums[dq.PeekRear()] < nums[i]) dq.PopRear(); dq.PushRear(i); // Once we have k elements, add max to result if (i >= k - 1) { result[i - k + 1] = nums[dq.PeekFront()]; } } return result; }
Understanding when and how to use stacks and queues is crucial for solving many algorithmic problems and real-world systems.
These problems represent the most common patterns in interviews and real-world applications. Master these to handle 80% of stack and queue questions.
Given a string with brackets, determine if they are balanced and properly nested.
public bool IsValid(string s) { var stack = new Stack<char>(); var pairs = new Dictionary<char, char> { { ')', '(' }, { ']', '[' }, { '}', '{' } }; foreach (char c in s) { if (pairs.ContainsKey(c)) { if (stack.Count == 0 || stack.Pop() != pairs[c]) return false; } else { stack.Push(c); } } return stack.Count == 0; } // Time: O(n), Space: O(n)
Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time.
public class MinStack { private Stack<int> stack; private Stack<int> minStack; public MinStack() { stack = new Stack<int>(); minStack = new Stack<int>(); } public void Push(int val) { stack.Push(val); if (minStack.Count == 0 || val <= minStack.Peek()) minStack.Push(val); } public void Pop() { if (stack.Pop() == minStack.Peek()) minStack.Pop(); } public int Top() => stack.Peek(); public int GetMin() => minStack.Peek(); } // Time: O(1) all ops, Space: O(n)
Evaluate an expression in Reverse Polish Notation (postfix notation) where operators follow operands.
public int EvalRPN(string[] tokens) { var stack = new Stack<int>(); var ops = new HashSet<string> { "+", "-", "*", "/" }; foreach (string token in tokens) { if (ops.Contains(token)) { int b = stack.Pop(); int a = stack.Pop(); int result = token switch { "+" => a + b, "-" => a - b, "*" => a * b, "/" => a / b, }; stack.Push(result); } else { stack.Push(int.Parse(token)); } } return stack.Pop(); } // Time: O(n), Space: O(n)
For each day, find the number of days until a warmer temperature. Use a monotonic decreasing stack.
public int[] DailyTemperatures(int[] temps) { var result = new int[temps.Length]; var stack = new Stack<int>(); // Store indices for (int i = 0; i < temps.Length; i++) { // Pop smaller temperatures and set their result while (stack.Count > 0 && temps[stack.Peek()] < temps[i]) { int idx = stack.Pop(); result[idx] = i - idx; } stack.Push(i); } return result; } // Time: O(n), Space: O(n)
Find the largest rectangular area in a histogram using a monotonic stack.
public int LargestRectangleArea(int[] heights) { var stack = new Stack<int>(); int maxArea = 0; for (int i = 0; i <= heights.Length; i++) { int h = (i == heights.Length) ? 0 : heights[i]; // Pop and calculate area for all taller bars while (stack.Count > 0 && heights[stack.Peek()] > h) { int idx = stack.Pop(); int width = (stack.Count == 0) ? i : i - stack.Peek() - 1; int area = heights[idx] * width; maxArea = Math.Max(maxArea, area); } if (i < heights.Length) stack.Push(i); } return maxArea; } // Time: O(n), Space: O(n)
Implement a queue using two stacks, one for input and one for output.
public class QueueUsingStacks { private Stack<int> input = new(); private Stack<int> output = new(); public void Push(int x) => input.Push(x); public int Pop() { Peek(); // Ensures output stack is filled return output.Pop(); } public int Peek() { // Lazy transfer: only move when output is empty if (output.Count == 0) { while (input.Count > 0) output.Push(input.Pop()); } return output.Peek(); } public bool Empty() => input.Count == 0 && output.Count == 0; } // Push: O(1), Pop/Peek: O(1) amortized
Implement a stack using two queues. More complex: either make push O(n) or pop O(n).
public class StackUsingQueues { private Queue<int> q1 = new(); private Queue<int> q2 = new(); // Push: O(n) - move all elements from q1 to q2 public void Push(int x) { q2.Enqueue(x); // Move all from q1 to q2 while (q1.Count > 0) q2.Enqueue(q1.Dequeue()); // Swap: q1 is now the main queue (q1, q2) = (q2, q1); } // Pop: O(1) - front of q1 is the top public int Pop() => q1.Dequeue(); public int Top() => q1.Peek(); public bool Empty() => q1.Count == 0; }
The .NET framework provides optimized generic implementations. Always prefer these over custom implementations unless you need specialized behavior.
// Stack<T> var stack = new Stack<int>(); stack.Push(1); stack.Push(2); int top = stack.Pop(); // 2 bool empty = stack.Count == 0; // Queue<T> var queue = new Queue<int>(); queue.Enqueue(1); queue.Enqueue(2); int front = queue.Dequeue(); // 1 int next = queue.Peek(); // 2 bool isEmpty = queue.Count == 0; // Common methods // .Count: number of elements // .Contains(item): O(n) search // .TryPeek(out T): safe peek without exception // .TryDequeue(out T): safe dequeue without exception
using System.Collections.Generic; // PriorityQueue with custom comparison PriorityQueue<Task, int> pq = new(); // Lower priority = dequeues first (min-heap) pq.Enqueue(new Task("Print"), 1); // High priority pq.Enqueue(new Task("Backup"), 10); // Low priority while (pq.Count > 0) { Task task = pq.Dequeue(); Console.WriteLine(task.Name); // Print, Backup } // Custom comparer for descending (max-heap) PriorityQueue<int, int> maxHeap = new(Comparer<int>.Create( (a, b) => b.CompareTo(a))); maxHeap.Enqueue(5, 5); maxHeap.Enqueue(10, 10); maxHeap.Dequeue(); // 10
Quick reference for time and space complexity of all stack and queue variants.
| Operation | Array Stack | Linked Stack | Array Queue | Circular Queue | Linked Queue | Priority Queue |
|---|---|---|---|---|---|---|
| Push/Enqueue | O(1) amortized | O(1) | O(n)* | O(1) amortized | O(1) | O(log n) |
| Pop/Dequeue | O(1) | O(1) | O(1) | O(1) | O(1) | O(log n) |
| Peek | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
| Space per element | 1 word | 1 word + ptr | 1 word | 1 word | 1 word + ptr | 1 word (heap) |
| Best for | General stacks | Educational | Small fixed | Production queues | Educational | Dijkstra, scheduling |
Strategic insights to recognize when a stack or queue is the right tool and how to approach interview questions.