Linked stacks and queues

Linked stacks and queues

 

---

LINKED LIST IMPLEMENTATION OF STACK

An array implementation of stack has certain limitations. One of the limitations is that such a stack cannot grow or shrink dynamically. This drawback can be overcome by using linked implementation. A stack implemented using a linked list is also called linked stack.

Each element of the stack will be represented as a node of the list. The addition and deletion of a node will be only at one end. The first node is considered to be at the top of the stack, and it will be pointed to by a pointer called top. The last node is the bottom of the stack, and its link field is set to Null. An empty stack will have Top = Null. 

Algorithm for push operation in Linked Stack

//Algorithm: push operation on linked stack

push(Top)
1. Allocate memory for nptr
2. If nptr=NULL
    Print “overflow: Memory not allocated”
    End If
3. Read Item
4. Set nptr ->info = item
5. Set nptr ->next = Top
6. Set Top=nptr
7. END

Algorithm for pop operation in Linked Stack

Algorithm: Pop operation on Linked List

pop(Top)

1. If Top=NULL
   Print “underflow: stack is empty!”
   End If

2. Set item=Top->info
3. Set temp=Top
4. Set Top = Top->next
5. Deallocate temp
6. Print “popped element is item:  ”,item
7. END

LINKED LIST IMPLEMENTATION OF QUEUE

The  array implementation can not be used for the large scale applications where the queues are implemented. One of the alternatives of array implementation is linked list implementation of queue.

Operation on Linked Queue

There are two basic operations which can be implemented on the linked queues. The operations are Insertion and Deletion.

Insert operation

The insert operation appends the queue by adding an element to the end of the queue. The new element will be the last element of the queue.

Algorithm
Step 1: Allocate the space for the new node PTR
Step 2: SET PTR -> DATA = VAL
Step 3: IF FRONT = NULL
           SET FRONT = REAR = PTR
           SET FRONT -> NEXT = REAR -> NEXT = NULL
        ELSE
           SET REAR -> NEXT = PTR
           SET REAR = PTR
           SET REAR -> NEXT = NULL
        [END OF IF]
Step 4: END

Deletion

Deletion operation removes the element that is first inserted among all the queue elements. Firstly, we need to check either the list is empty or not. The condition front == NULL becomes true if the list is empty, in this case , we simply write underflow on the console and make exit.

Otherwise, we will delete the element that is pointed by the pointer front.

Algorithm
Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
Step 2: SET PTR = FRONT
Step 3: SET FRONT = FRONT -> NEXT
Step 4: FREE PTR
Step 5: END