In this article, we will be discussing two data structures – Stack and Queue. We will discuss various I/O operations on these data structures and their implementation using another data structure, i.e., Linked List.
Please visit my earlier article on Linked List implementation in C# to get a basic understanding of Linked List.
We will be learning about,
Before proceeding further i would recommend to download source code from Github
A Stack is a linear data structure which allows adding and removing of elements in a particular order. New elements are added at the top of Stack. If we want to remove an element from the Stack, we can only remove the top element from Stack. Since it allows insertion and deletion from only one end and the element to be inserted last will be the element to be deleted first, hence it is called Last in First Out data structure (LIFO).
Stack can be implemented using both, arrays and linked list. The limitation in case of array is that we need to define the size at the beginning of the implementation. This makes our Stack static. It can also result in “Stack overflow” if we try to add elements after the array is full. So, to alleviate this problem, we use linked list to implement the Stack so that it can grow in real time.
First, we will create our Node class which will form our Linked List. We will be using this same Node class to implement the Queue also in the later part of this article.
internal class Node { internal int data; internal Node next; // Constructor to create a new node.Next is by default initialized as null public Node(int d) { data = d; next = null; } }
Now, we will create our Stack Class. We will define a pointer, top, and initialize it to null. So, our LinkedListStack class will be –
internal class LinkListStack { Node top; public LinkListStack() { this.top = null; } }
Now, our Stack and Node class is ready. So, we will proceed to Push operation on Stack. We will add a new element at the top of Stack.
internal void Push(int value) { Node newNode = new Node(value); if (top == null) { newNode.next = null; } else { newNode.next = top; } top = newNode; Console.WriteLine("{0} pushed to stack", value); }
We will remove the top element from Stack.
internal void Pop() { if (top == null) { Console.WriteLine("Stack Underflow. Deletion not possible"); return; } Console.WriteLine("Item popped is {0}", top.data); top = top.next; }
The peek operation will always return the top element of Stack without removing it from Stack.
The time complexity for Peek operation is O(1). The Peek method will be like following.
internal void Peek() { if (top == null) { Console.WriteLine("Stack Underflow."); return; } Console.WriteLine("{0} is on the top of Stack", this.top.data); }
A Queue is also a linear data structure where insertions and deletions are performed from two different ends. A new element is added from the rear of Queue and deletion of existing element occurs from the front. Since we can access elements from both ends and the element inserted first will be the one to be deleted first, hence Queue is called First in First Out data structure (FIFO).
Here, we will define two operations on Queue.
Similar to Stack, the Queue can also be implemented using both, arrays and linked list. But it also has the same drawback of limited size. Hence, we will be using a Linked list to implement the Queue.
The Node class will be the same as defined above in Stack implementation. We will define LinkedListQueue class as below.
internal class LinkListQueue { Node front; Node rear; public LinkListQueue() { this.front = this.rear = null; } }
Here, we have taken two pointers – rear and front – to refer to the rear and the front end of the Queue respectively and will initialize it to null.
We will add a new element to our Queue from the rear end.
internal void Enqueue(int item) { Node newNode = new Node(item); // If queue is empty, then new node is front and rear both if (this.rear == null) { this.front = this.rear = newNode; } else { // Add the new node at the end of queue and change rear this.rear.next = newNode; this.rear = newNode; } Console.WriteLine("{0} inserted into Queue", item); }
We will delete the existing element from the Queue from the front end.
The time complexity for Dequeue operation is O(1). The Method for Dequeue will be like following.
internal void Dequeue() { // If queue is empty, return NULL. if (this.front == null) { Console.WriteLine("The Queue is empty"); return; } // Store previous front and move front one node ahead Node temp = this.front; this.front = this.front.next; // If front becomes NULL, then change rear also as NULL if (this.front == null) { this.rear = null; } Console.WriteLine("Item deleted is {0}", temp.data); }
Introduction Blazor is a .NET web framework that allows us to create client-side applications using…
Introduction In this article, we are going to create a sudoku solver with the help…
Introduction In this article, we will learn how to implement Azure serverless with Blazor web…
Introduction Angular is an open-source framework that allows us to create applications for multiple platforms…
Introduction In this article, we will create an optical character recognition (OCR) application using Angular…
Introduction In this article, we will create an optical character recognition (OCR) application using Blazor…