Implementation Of Stack And Queue Using Linked List

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). 

 

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.

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;
    }
 }

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.

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);
}

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.

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;
}

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.

internal void Peek()
 {
     if (top == null)
     {
         Console.WriteLine("Stack Underflow.");
         return;
     }

     Console.WriteLine("{0} is on the top of Stack", this.top.data);
 }

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.

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.

Enqueue of an Element

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.

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);
 }

Dequeue of an Element

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.

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);
 }

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.