6.4 - Stacks and Queues
Stacks and queues are fundamental data structures that follow specific patterns for adding and removing elements. They are used in various applications, from algorithm implementation to system design. This section explores stacks and queues in detail, including their implementations, operations, and applications in C#.
6.4.1 - Stack Operations and Applications
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed.
6.4.1.1 - Stack Operations
The primary operations of a stack are:
- Push: Add an element to the top of the stack.
- Pop: Remove and return the top element from the stack.
- Peek: Return the top element without removing it.
- IsEmpty: Check if the stack is empty.
6.4.1.2 - Stack Implementation in C#
C# provides a built-in generic Stack<T> class in the System.Collections.Generic namespace:
using System.Collections.Generic;
// Creating a stack
Stack<int> stack = new Stack<int>();
// Pushing elements
stack.Push(1);
stack.Push(2);
stack.Push(3);
// Peeking at the top element
int topElement = stack.Peek(); // 3
// Popping elements
int poppedElement = stack.Pop(); // 3
poppedElement = stack.Pop(); // 2
// Checking if the stack is empty
bool isEmpty = stack.Count == 0;
// Getting the number of elements
int count = stack.Count;
// Clearing the stack
stack.Clear();
6.4.1.3 - Custom Stack Implementation
You can also implement a stack using an array or a linked list:
Array-based Stack
public class ArrayStack<T>
{
private T[] elements;
private int top;
private const int DefaultCapacity = 10;
public ArrayStack()
{
elements = new T[DefaultCapacity];
top = -1;
}
public int Count => top + 1;
public bool IsEmpty => Count == 0;
public void Push(T item)
{
if (top == elements.Length - 1)
Resize();
elements[++top] = item;
}
public T Pop()
{
if (IsEmpty)
throw new InvalidOperationException("Stack is empty");
return elements[top--];
}
public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException("Stack is empty");
return elements[top];
}
private void Resize()
{
T[] newArray = new T[elements.Length * 2];
Array.Copy(elements, newArray, elements.Length);
elements = newArray;
}
}
Linked List-based Stack
public class LinkedListStack<T>
{
private class Node
{
public T Value { get; set; }
public Node Next { get; set; }
public Node(T value)
{
Value = value;
Next = null;
}
}
private Node top;
private int count;
public int Count => count;
public bool IsEmpty => Count == 0;
public void Push(T item)
{
Node newNode = new Node(item);
newNode.Next = top;
top = newNode;
count++;
}
public T Pop()
{
if (IsEmpty)
throw new InvalidOperationException("Stack is empty");
T value = top.Value;
top = top.Next;
count--;
return value;
}
public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException("Stack is empty");
return top.Value;
}
}
6.4.1.4 - Stack Applications
Stacks are used in various applications:
- Function Call Management: The call stack keeps track of function calls and their local variables.
- Expression Evaluation: Stacks are used to evaluate arithmetic expressions, especially in postfix (Reverse Polish) notation.
- Undo Mechanism: Stacks can be used to implement undo functionality in applications.
- Backtracking Algorithms: Stacks are used in backtracking algorithms, such as depth-first search.
- Parsing: Stacks are used in parsing expressions, such as checking for balanced parentheses.
6.4.1.5 - Example: Balanced Parentheses
Here's an example of using a stack to check if a string has balanced parentheses:
public static bool AreParenthesesBalanced(string expression)
{
Stack<char> stack = new Stack<char>();
foreach (char c in expression)
{
if (c == '(' || c == '[' || c == '{')
{
stack.Push(c);
}
else if (c == ')' || c == ']' || c == '}')
{
if (stack.Count == 0)
return false;
char top = stack.Pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{'))
{
return false;
}
}
}
return stack.Count == 0;
}
6.4.1.6 - Example: Infix to Postfix Conversion
Here's an example of using a stack to convert an infix expression to postfix notation:
public static string InfixToPostfix(string infix)
{
Dictionary<char, int> precedence = new Dictionary<char, int>
{
{ '+', 1 }, { '-', 1 },
{ '*', 2 }, { '/', 2 },
{ '^', 3 }
};
Stack<char> operators = new Stack<char>();
StringBuilder postfix = new StringBuilder();
foreach (char c in infix)
{
if (char.IsLetterOrDigit(c))
{
postfix.Append(c);
}
else if (c == '(')
{
operators.Push(c);
}
else if (c == ')')
{
while (operators.Count > 0 && operators.Peek() != '(')
{
postfix.Append(operators.Pop());
}
if (operators.Count > 0 && operators.Peek() == '(')
operators.Pop();
}
else // Operator
{
while (operators.Count > 0 && operators.Peek() != '(' &&
precedence.ContainsKey(operators.Peek()) &&
precedence[operators.Peek()] >= precedence[c])
{
postfix.Append(operators.Pop());
}
operators.Push(c);
}
}
while (operators.Count > 0)
{
postfix.Append(operators.Pop());
}
return postfix.ToString();
}
6.4.2 - Queue Operations and Applications
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed.
6.4.2.1 - Queue Operations
The primary operations of a queue are:
- Enqueue: Add an element to the end of the queue.
- Dequeue: Remove and return the element from the front of the queue.
- Peek: Return the front element without removing it.
- IsEmpty: Check if the queue is empty.
6.4.2.2 - Queue Implementation in C#
C# provides a built-in generic Queue<T> class in the System.Collections.Generic namespace:
using System.Collections.Generic;
// Creating a queue
Queue<int> queue = new Queue<int>();
// Enqueuing elements
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
// Peeking at the front element
int frontElement = queue.Peek(); // 1
// Dequeuing elements
int dequeuedElement = queue.Dequeue(); // 1
dequeuedElement = queue.Dequeue(); // 2
// Checking if the queue is empty
bool isEmpty = queue.Count == 0;
// Getting the number of elements
int count = queue.Count;
// Clearing the queue
queue.Clear();
6.4.2.3 - Custom Queue Implementation
You can also implement a queue using an array or a linked list:
Array-based Queue
public class ArrayQueue<T>
{
private T[] elements;
private int front;
private int rear;
private int count;
private const int DefaultCapacity = 10;
public ArrayQueue()
{
elements = new T[DefaultCapacity];
front = 0;
rear = -1;
count = 0;
}
public int Count => count;
public bool IsEmpty => Count == 0;
public void Enqueue(T item)
{
if (count == elements.Length)
Resize();
rear = (rear + 1) % elements.Length;
elements[rear] = item;
count++;
}
public T Dequeue()
{
if (IsEmpty)
throw new InvalidOperationException("Queue is empty");
T value = elements[front];
front = (front + 1) % elements.Length;
count--;
return value;
}
public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException("Queue is empty");
return elements[front];
}
private void Resize()
{
T[] newArray = new T[elements.Length * 2];
for (int i = 0; i < count; i++)
{
newArray[i] = elements[(front + i) % elements.Length];
}
elements = newArray;
front = 0;
rear = count - 1;
}
}
Linked List-based Queue
public class LinkedListQueue<T>
{
private class Node
{
public T Value { get; set; }
public Node Next { get; set; }
public Node(T value)
{
Value = value;
Next = null;
}
}
private Node front;
private Node rear;
private int count;
public int Count => count;
public bool IsEmpty => Count == 0;
public void Enqueue(T item)
{
Node newNode = new Node(item);
if (IsEmpty)
{
front = newNode;
rear = newNode;
}
else
{
rear.Next = newNode;
rear = newNode;
}
count++;
}
public T Dequeue()
{
if (IsEmpty)
throw new InvalidOperationException("Queue is empty");
T value = front.Value;
front = front.Next;
count--;
if (front == null)
rear = null;
return value;
}
public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException("Queue is empty");
return front.Value;
}
}
6.4.2.4 - Queue Applications
Queues are used in various applications:
- Task Scheduling: Operating systems use queues to manage processes and tasks.
- Breadth-First Search: Queues are used in breadth-first search algorithms.
- Buffering: Queues are used to buffer data in various applications, such as printers and media players.
- Message Queues: Queues are used in message-passing systems for asynchronous communication.
- Event Handling: Queues are used to handle events in event-driven programming.
6.4.2.5 - Example: Level Order Traversal of a Binary Tree
Here's an example of using a queue to perform a level order traversal of a binary tree:
public class TreeNode
{
public int Value { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
public TreeNode(int value)
{
Value = value;
Left = null;
Right = null;
}
}
public static List<int> LevelOrderTraversal(TreeNode root)
{
List<int> result = new List<int>();
if (root == null)
return result;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
TreeNode node = queue.Dequeue();
result.Add(node.Value);
if (node.Left != null)
queue.Enqueue(node.Left);
if (node.Right != null)
queue.Enqueue(node.Right);
}
return result;
}
6.4.3 - Implementations Using Stack<T> and Queue<T>
C# provides several specialized queue types for specific use cases:
6.4.4 - Priority Queues (C# 11+)
A priority queue is a queue where elements are dequeued based on their priority rather than their order of entry. In .NET 6 and later, C# provides a built-in PriorityQueue<TElement, TPriority> class:
// Creating a priority queue
PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
// Enqueuing elements with priorities
priorityQueue.Enqueue("Task 1", 3); // Lower priority
priorityQueue.Enqueue("Task 2", 1); // Highest priority
priorityQueue.Enqueue("Task 3", 2); // Medium priority
// Dequeuing elements (in order of priority)
string task = priorityQueue.Dequeue(); // "Task 2" (priority 1)
task = priorityQueue.Dequeue(); // "Task 3" (priority 2)
task = priorityQueue.Dequeue(); // "Task 1" (priority 3)
6.4.3.2 - ConcurrentQueue<T>
ConcurrentQueue<T> is a thread-safe queue that can be used in multi-threaded applications:
using System.Collections.Concurrent;
// Creating a concurrent queue
ConcurrentQueue<int> concurrentQueue = new ConcurrentQueue<int>();
// Enqueuing elements
concurrentQueue.Enqueue(1);
concurrentQueue.Enqueue(2);
concurrentQueue.Enqueue(3);
// Trying to dequeue an element
if (concurrentQueue.TryDequeue(out int result))
{
Console.WriteLine($"Dequeued: {result}");
}
// Trying to peek at the front element
if (concurrentQueue.TryPeek(out int frontElement))
{
Console.WriteLine($"Front element: {frontElement}");
}
6.4.3.3 - CircularBuffer<T>
A circular buffer (or ring buffer) is a fixed-size buffer that wraps around when it reaches the end. While not built into C#, you can implement it:
public class CircularBuffer<T>
{
private T[] buffer;
private int head;
private int tail;
private int count;
public CircularBuffer(int capacity)
{
buffer = new T[capacity];
head = 0;
tail = 0;
count = 0;
}
public int Count => count;
public int Capacity => buffer.Length;
public bool IsEmpty => Count == 0;
public bool IsFull => Count == Capacity;
public void Enqueue(T item)
{
if (IsFull)
throw new InvalidOperationException("Buffer is full");
buffer[tail] = item;
tail = (tail + 1) % Capacity;
count++;
}
public T Dequeue()
{
if (IsEmpty)
throw new InvalidOperationException("Buffer is empty");
T item = buffer[head];
head = (head + 1) % Capacity;
count--;
return item;
}
public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException("Buffer is empty");
return buffer[head];
}
}
6.4.4 - Deque (Double-Ended Queue)
A deque (pronounced "deck") is a double-ended queue that allows insertion and removal of elements from both ends. While not built into C#, you can implement it:
public class Deque<T>
{
private LinkedList<T> list = new LinkedList<T>();
public int Count => list.Count;
public bool IsEmpty => Count == 0;
public void AddFirst(T item)
{
list.AddFirst(item);
}
public void AddLast(T item)
{
list.AddLast(item);
}
public T RemoveFirst()
{
if (IsEmpty)
throw new InvalidOperationException("Deque is empty");
T value = list.First.Value;
list.RemoveFirst();
return value;
}
public T RemoveLast()
{
if (IsEmpty)
throw new InvalidOperationException("Deque is empty");
T value = list.Last.Value;
list.RemoveLast();
return value;
}
public T PeekFirst()
{
if (IsEmpty)
throw new InvalidOperationException("Deque is empty");
return list.First.Value;
}
public T PeekLast()
{
if (IsEmpty)
throw new InvalidOperationException("Deque is empty");
return list.Last.Value;
}
}
6.4.5 - Performance Considerations
When working with stacks and queues, consider the following performance aspects:
- Implementation Choice: Array-based implementations provide faster random access but may require resizing. Linked list-based implementations provide constant-time insertions and deletions but slower random access.
- Capacity Management: For array-based implementations, choose an appropriate initial capacity to avoid frequent resizing.
- Thread Safety: Use concurrent collections for multi-threaded applications.
- Memory Usage: Be mindful of memory usage, especially with large collections.
6.4.6 - Best Practices
Here are some best practices for working with stacks and queues in C#:
- Choose the Right Collection: Use Stack<T> for LIFO behavior and Queue<T> for FIFO behavior.
- Handle Empty Collections: Always check if a collection is empty before performing operations like Pop, Peek, Dequeue, etc.
- Use Generic Collections: Prefer generic collections for type safety and performance.
- Consider Thread Safety: Use concurrent collections for multi-threaded applications.
- Implement Custom Collections When Needed: Implement custom stack or queue classes when you need specific behavior not provided by the built-in collections.
In the next section, we'll explore linked lists, which are fundamental data structures that provide efficient insertions and deletions.