Implementing Stack and Queue Using Linked Lists in C#

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

Prerequisite

Please visit my earlier article on linked list implementation in C# to get a basic understanding of linked lists.

We will be learning about:

• What a stack is.
• Implementing stack functionalities using linked lists.
• Uses of stacks.
• What a queue is.
• Implementing queue functionalities using linked lists.
• Uses of queues.

Before proceeding further, I would recommend downloading the source code from GitHub.

What Is a Stack?

A stack is a linear data structure which allows the adding and removing of elements in a particular order. New elements are added at the top of the stack. If we want to remove an element from the stack, we can only remove the top element from the 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, it is called the 'Last in First Out' data structure (LIFO).

Here we will define three operations on a 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 a stack overflow condition.
• Pop – it specifies removing an element from the stack. Elements are always removed from the top of the stack. If we try to perform a pop operation on an empty stack, then it is said to be a stack underflow condition.
• Peek – it will show the element on the top of the stack (without removing it).

Implementing Stack Functionalities Using a Linked List

Stack can be implemented using both arrays and linked lists. The limitation, in the case of an 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 a 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 also implement the queue 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 Onto a Stack

Now, our stack and Node class is ready. So, we will proceed to push the operation onto the stack. We will add a new element at the top of the 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 the 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 the Stack

We will remove the top element from the stack.

Algorithm

• If the stack is empty, terminate the method as it is stack underflow.
• If the stack is not empty, increment the top to point to the next node.
• Hence the element pointed to by the top earlier is now removed.

The time complexity for Pop operation is O(1). The method for pop will look like the 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 the stack without removing it from the 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 to by the top.

The time complexity for the peek operation is O(1). The peek method will look like the 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 features 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 a 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 the queue and the deletion of existing elements 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, the queue is called the 'First in First Out' data structure (FIFO).

Here, we will define two operations on the queue.

• Enqueue – It specifies the insertion of a new element to the queue. Enqueue will always take place at the rear end of the queue.
• Dequeue – It specifies the deletion of an existing element from the queue. Dequeue will always take place at 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 lists. 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 the stack implementation. We will define the 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 to the rear of 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 look 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 the front to point to the next node.
• Finally, check if the front is null, then set rear to null also. This signifies an empty queue.

The time complexity for Dequeue operation is O(1). The method for Dequeue will look like the 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 systems uses queues. The processes that are ready to execute and the requests of CPU resources wait in a queue and the request is served on a 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 lists. Please refer to the attached code for better understanding. You can also find the array implementation of stack and queue in the attached code.

You can also find this article at C# Corner.

You can find my other articles on data structures here.