Introduction
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.
Prerequisite
Please visit my
earlier article on Linked List implementation in C# to get a
basic understanding of Linked List.
We will be learning
about,
- Stack
- Implementing Stack functionalities using Linked List
- Uses of Stack
- Queue
- Implementing Queue functionalities using Linked List.
- Uses of Queue
What is Stack?
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).
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).
Here we will define three operations on Stack,
- Push - it specifies adding an element to the Stack. If we try to
insert an element when the Stack is full, then it is said to be Stack
Overflow condition
- Pop - it specifies removing an element from the Stack. Elements are
always removed from top of Stack. If we try to perform pop operation on an
empty Stack, then it is said to be Stack Underflow condition.
- Peek - it will show the element on the top of Stack(without
removing it).
Implementing Stack functionalities
using Linked List
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.
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.
1.
internal class Node
2.
{
3.
internal int data;
4.
internal Node next;
5.
6.
// Constructor to create a new node.Next is by default initialized as null
7.
public Node(int d)
8.
{
9.
data = d;
10.
next = null;
11.
}
12. }
|
Now, we will create our Stack Class. We will define
a pointer, top, and initialize it to null. So, our LinkedListStack class will
be -
1.
internal class LinkListStack
2.
{
3.
Node top;
4.
5.
public LinkListStack()
6.
{
7.
this.top = null;
8.
}
9. }
|
Push an element
into Stack
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.
Algorithm
- Create a new node with the value to be inserted.
- If the Stack is empty, set the next of the new node to null.
- If the Stack is not empty, set the next of the new node to top.
- Finally, increment the top to point to the new node.
The time complexity for Push operation
is O(1). The method for Push will look like this.
1.
internal void Push(int value)
2.
{
3.
Node newNode = new Node(value);
4.
if (top == null)
5.
{
6.
newNode.next = null;
7.
}
8.
else
9.
{
10.
newNode.next = top;
11.
}
12.
top = newNode;
13.
Console.WriteLine("{0} pushed to stack", value);
14. }
|
Pop an element from
Stack
We will remove the
top element from Stack.
Algorithm
- If the Stack is empty, terminate the method as it is Stack
underflow.
- If the Stack is not empty, increment top to point to the next node.
- Hence the element pointed by top earlier is now removed.
The time complexity for Pop operation is O(1). The
method for Pop will be like following.
1.
internal void Pop()
2.
{
3.
if (top == null)
4.
{
5.
Console.WriteLine("Stack Underflow. Deletion not possible");
6.
return;
7.
}
8.
9.
Console.WriteLine("Item popped is {0}", top.data);
10.
top = top.next;
11. }
|
Peek the element
from Stack
The peek operation
will always return the top element of Stack without removing it from Stack.
Algorithm
- If the Stack is empty, terminate the method as it is Stack
underflow.
- If the Stack is not empty, return the element pointed by
the top.
The time complexity
for Peek operation is O(1). The Peek method will be like following.
1.
internal void Peek()
2.
{
3.
if (top == null)
4.
{
5.
Console.WriteLine("Stack Underflow.");
6.
return;
7.
}
8.
9.
Console.WriteLine("{0} is on the top of Stack", this.top.data);
10. }
|
Uses of Stack
- Stack can be used to implement back/forward button in the browser.
- Undo feature in the text editors are also implemented using Stack.
- It is also used to implement recursion.
- Call and return mechanism for a method uses Stack.
- It is also used to implement backtracking.
What is Queue?
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.
- Enqueue - It specifies the insertion of a new element to the Queue.
Enqueue will always take place from the rear end of the Queue.
- Dequeue - It specifies the deletion of an existing element from the
Queue. Dequeue will always take place from the front end of the
Queue.
Implementing Queue functionalities
using Linked List
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.
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.
1.
internal class LinkListQueue
2.
{
3.
Node front;
4.
Node rear;
5.
6.
public LinkListQueue()
7.
{
8.
this.front = this.rear = null;
9.
}
10. }
|
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.
Enqueue of an Element
We will add a new element to our Queue from the rear end.
Algorithm
We will add a new element to our Queue from the rear end.
Algorithm
- Create a new node with the value to be inserted.
- If the Queue is empty, then set both front and rear to point to
newNode.
- If the Queue is not empty, then set next of rear to the new
node and the rear to point to the new node.
The time complexity for Enqueue operation is O(1).
The Method for Enqueue will be like the following.
1.
internal void Enqueue(int item)
2.
{
3.
Node newNode = new Node(item);
4.
5.
// If queue is empty, then new node is front and rear both
6.
if (this.rear == null)
7.
{
8.
this.front = this.rear = newNode;
9.
}
10.
else
11.
{
12.
// Add the new node at the end of queue and change rear
13.
this.rear.next = newNode;
14.
this.rear = newNode;
15.
}
16.
Console.WriteLine("{0} inserted into Queue", item);
17. }
|
Dequeue of an Element
We will delete the existing element from the Queue from the front end.
We will delete the existing element from the Queue from the front end.
Algorithm
- If the Queue is empty, terminate the method.
- If the Queue is not empty, increment front to point to next node.
- Finally, check if the front is null, then set rear to null also.
This signifies empty Queue.
The time complexity
for Dequeue operation is O(1). The Method for Dequeue will
be like following.
1.
internal void Dequeue()
2.
{
3.
// If queue is empty, return NULL.
4.
if (this.front == null)
5.
{
6.
Console.WriteLine("The Queue is empty");
7.
return;
8.
}
9.
10.
// Store previous front and move front one node ahead
11.
Node temp = this.front;
12.
this.front = this.front.next;
13.
14.
// If front becomes NULL, then change rear also as NULL
15.
if (this.front == null)
16.
{
17.
this.rear = null;
18.
}
19.
20.
Console.WriteLine("Item deleted is {0}", temp.data);
21.
}
|
Uses of Queue
- CPU scheduling in Operating system uses Queue. The processes ready
to execute and the requests of CPU resources wait in a queue and the
request is served on first come first serve basis.
- Data buffer - a physical memory
storage which is used to temporarily store data while it is being moved
from one place to another is also implemented using Queue.
Conclusion
We learned about Stack and Queue data structures
and also implemented them using Linked List. Please refer to the attached code
for better understanding. You can also find the array implementation of Stack
and Queue in the attached code.
EmoticonEmoticon