Implementation Of Stack And Queue Using Linked List

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

internal class LinkListStack
{
    Node top;

    public LinkListStack()
    {
        this.top = null;
    }
}

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

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

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.

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 the queue is empty, then the new node is both the front and rear
    if (this.rear == null)
    {
        this.front = this.rear = newNode;
    }
    else
    {
        // Add the new node at the end of the queue and change the rear
        this.rear.next = newNode;
        this.rear = newNode;
    }

    Console.WriteLine("{0} inserted into Queue", item);
}

Dequeue of an Element

Dequeue of an ElementDequeue of an ElementDequeue of an ElementDequeue 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 the 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 to 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.