Data structures and algorithms form the basis for software development. As a software engineer, it is important to understand different data structures and algorithms and their implementations in different programming languages. In this tutorial, we will learn about stacks and queues and how to implement them in C#. We will also discuss different applications of these data structures.
Overview of Stacks and Queues
Stacks and queues are two of the most commonly used data structures. A stack is a data structure that follows the Last-In-First-Out (LIFO) principle, which means that the last element added to the stack is the first one to be removed. A queue, on the other hand, follows the First-In-First-Out (FIFO) principle, which means that the first element added to the queue is the first one to be removed.
Implementing Stacks and Queues using Arrays
We can implement stacks and queues using arrays in C#. To implement a stack using an array, we need to keep track of the index of the element at the top of the stack. We can use a variable to store this index. Then, we can push elements onto the stack by incrementing this index and adding the element at that index. To pop an element off the stack, we can decrement the index and return the element at that index.
The following code snippet illustrates how to implement a stack using an array in C#:
public class Stack
{
private int[] array;
private int top;
public Stack(int size)
{
array = new int[size];
top = -1;
}
public void Push(int element)
{
if (top == array.Length - 1)
{
throw new StackOverflowException();
}
array[++top] = element;
}
public int Pop()
{
if (top == -1)
{
throw new InvalidOperationException();
}
return array[top--];
}
}Similarly, we can implement a queue using an array in C#. We need to keep track of the index of the element at the front and the back of the queue. We can use two variables to store these indices. Then, we can enqueue elements by incrementing the back index and adding the element at that index. To dequeue an element, we can increment the front index and return the element at that index.
The following code snippet illustrates how to implement a queue using an array in C#:
public class Queue
{
private int[] array;
private int front;
private int back;
public Queue(int size)
{
array = new int[size];
front = 0;
back = -1;
}
public void Enqueue(int element)
{
if (back == array.Length - 1)
{
throw new QueueOverflowException();
}
array[++back] = element;
}
public int Dequeue()
{
if (front > back)
{
throw new InvalidOperationException();
}
return array[front++];
}
}Implementing Stacks and Queues using Classes
We can also implement stacks and queues using classes in C#. To implement a stack using a class, we need to create a class that has a reference to the top node of the stack. We can use a variable to store this reference. Then, we can push elements onto the stack by creating a new node and setting its next reference to the top node. To pop an element off the stack, we can return the element of the top node and set the top node to its next reference.
The following code snippet illustrates how to implement a stack using a class in C#:
public class Stack
{
private class Node
{
public int element;
public Node next;
}
private Node top;
public Stack()
{
top = null;
}
public void Push(int element)
{
Node node = new Node();
node.element = element;
node.next = top;
top = node;
}
public int Pop()
{
if (top == null)
{
throw new InvalidOperationException();
}
int element = top.element;
top = top.next;
return element;
}
}Similarly, we can implement a queue using a class in C#. We need to create a class that has a reference to the front and back nodes of the queue. We can use two variables to store these references. Then, we can enqueue elements by creating a new node and setting its next reference to the back node. To dequeue an element, we can return the element of the front node and set the front node to its next reference.
The following code snippet illustrates how to implement a queue using a class in C#:
public class Queue
{
private class Node
{
public int element;
public Node next;
}
private Node front;
private Node back;
public Queue()
{
front = null;
back = null;
}
public void Enqueue(int element)
{
Node node = new Node();
node.element = element;
node.next = null;
if (back == null)
{
front = node;
}
else
{
back.next = node;
}
back = node;
}
public int Dequeue()
{
if (front == null)
{
throw new InvalidOperationException();
}
int element = front.element;
front = front.next;
if (front == null)
{
back = null;
}
return element;
}
}Using the Collections Framework for Stacks and Queues
The .NET Framework provides a set of collection classes that can be used to implement stacks and queues. These classes are part of the System.Collections.Generic namespace.
To implement a stack using the collections framework, we can use the Stack<T> class. This class provides methods for pushing elements onto the stack and popping elements off the stack.
The following code snippet illustrates how to use the Stack<T> class to implement a stack in C#:
Stack<int> stack = new Stack<int>();
// Push elements onto the stack
stack.Push(1);
stack.Push(2);
// Pop elements off the stack
int element1 = stack.Pop();
int element2 = stack.Pop();To implement a queue using the collections framework, we can use the Queue<T> class. This class provides methods for enqueuing elements into the queue and dequeuing elements from the queue.
The following code snippet illustrates how to use the Queue<T> class to implement a queue in C#:
Queue<int> queue = new Queue<int>();
// Enqueue elements into the queue
queue.Enqueue(1);
queue.Enqueue(2);
// Dequeue elements from the queue
int element1 = queue.Dequeue();
int element2 = queue.Dequeue();Applications of Stacks and Queues
Stacks and queues have many applications in software development. One of the most common applications of stacks is in recursion. When a recursive method is called, the parameters and local variables of the method are pushed onto the stack. When the method returns, the parameters and local variables are popped off the stack.
Queues are commonly used for task scheduling. When tasks need to be executed in the order in which they are received, a queue can be used to store the tasks and execute them in the correct order.
Conclusion
In this tutorial, we learned about stacks and queues and how to implement them in C#. We discussed how to implement stacks and queues using arrays and classes. We also discussed how to use the collections framework for implementing stacks and queues. Finally, we discussed some of the applications of stacks and queues.
Exercises
Write a C# program to create a stack using classes.
using System;
public class Stack
{
int[] stack;
int top;
public Stack(int size)
{
stack = new int[size];
top = -1;
}
public void Push(int data)
{
if (top == stack.Length - 1)
{
Console.WriteLine("Stack Overflow!");
}
else
{
stack[++top] = data;
}
}
public int Pop()
{
if (top == -1)
{
Console.WriteLine("Stack Underflow!");
return -1;
}
else
{
return stack[top--];
}
}
}Write a C# program to implement a queue using an array.
using System;
public class Queue
{
int[] queue;
int front, rear;
public Queue(int size)
{
queue = new int[size];
front = rear = -1;
}
public void Enqueue(int data)
{
if (rear == queue.Length - 1)
{
Console.WriteLine("Queue Overflow!");
}
else
{
queue[++rear] = data;
}
}
public int Dequeue()
{
if (front == rear)
{
Console.WriteLine("Queue Underflow!");
return -1;
}
else
{
return queue[++front];
}
}
}Write a C# program to implement a stack using the collections framework.
using System;
using System.Collections.Generic;
public class Stack
{
Stack<int> stack = new Stack<int>();
public void Push(int data)
{
stack.Push(data);
}
public int Pop()
{
if (stack.Count == 0)
{
Console.WriteLine("Stack Underflow!");
return -1;
}
else
{
return stack.Pop();
}
}
}Write a C# program to implement a queue using the collections framework.
using System;
using System.Collections.Generic;
public class Queue
{
Queue<int> queue = new Queue<int>();
public void Enqueue(int data)
{
queue.Enqueue(data);
}
public int Dequeue()
{
if (queue.Count == 0)
{
Console.WriteLine("Queue Underflow!");
return -1;
}
else
{
return queue.Dequeue();
}
}
}Write a C# program to demonstrate the application of stacks in expression conversion.
using System;
using System.Collections.Generic;
public class ExpressionConversion
{
public static void Main()
{
string expression = "(A+B)*C-(D-E)*(F+G)";
string postfix = "";
Stack<char> stack = new Stack<char>();
for (int i = 0; i < expression.Length; i++)
{
char ch = expression[i];
if (ch == '(')
{
stack.Push(ch);
}
else if (ch == ')')
{
while (stack.Peek() != '(')
{
postfix += stack.Pop();
}
stack.Pop();
}
else if (IsOperator(ch))
{
while (stack.Count != 0 && stack.Peek() != '(' && HasHigherPrecedence(ch, stack.Peek()))
{
postfix += stack.Pop();
}
stack.Push(ch);
}
else
{
postfix += ch;
}
}
while (stack.Count != 0)
{
postfix += stack.Pop();
}
Console.WriteLine("Postfix expression: " + postfix);
}
public static bool IsOperator(char ch)
{
return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}
public static bool HasHigherPrecedence(char operator1, char operator2)
{
if ((operator1 == '*' || operator1 == '/') && (operator2 == '+' || operator2 == '-'))
{
return true;
}
else
{
return false;
}
}
}