Stacks and Queues

A stack is a linear data structure which uses the same principle i.e. in a stack the insertion and deletion of an element is done only at one end called TOP.

Stack is called a LIFO (Last In, First Out) data structure as the element inserted last is the first one to be taken out.

Example: Pile of plates where one plate is placed on the top of another plate. A plate can be removed only from the top and if someone wants to add another plate it will be placed on the topmost position. So you can add or remove the plate only from one end i,e. topmost position.

Stacks can be implemented either using an array or a linked list.

Array Representation of Stacks

➤ Every stack has a variable TOP associated with it. 

➤ TOP is used to store the address of the topmost element of the stack. 

➤ It is the position where elements are added or removed.

➤ There is another variable MAX which is used to store the maximum number of elements a stack can hold.

➤ If TOP=NULL, it means stack is empty.

➤ If TOP=MAX - 1, then the stack is full.

Basic Operations performed on stack are:

PUSH Operation: PUSH operation is used to insert an element in the array. New element is added on the top of the stack.

Before inserting an element, we have to check first that stack is full or not. If TOP=MAX-1, means stack is full and no further insertion can be made. If tried to insert then OVERFLOW message is printed.

Here Push operation will insert a new element Q on the top of the stack.

POP Operation: POP Operation is used to remove an element from the topmost position of the stack. 

Before removing an element, we must check that if stack is empty or not. If TOP=NULL, means stack is empty and no deletion is possible. If tried to delete from the empty stack then UNDERFLOW message is printed.

Here POP operation will delete the topmost element Q.

Peep Operation: Peep operation is used to return the value of the topmost element of the stack without deleting it from the stack.

Peep operation first checks if the stack is empty or contain some elements.

If TOP=NULL, then appropriate message is printed else the value is returned.

Here peep operation will return Q as it is the topmost element in the stack

Algorithms:

Algorithm to PUSH an element in a stack
Step 1: IF TOP = MAX-1, then
                PRINT “OVERFLOW”
                Goto Step 4     
                [END OF IF]
Step 2: SET TOP = TOP + 1
Step 3: SET STACK[TOP] = VALUE
Step 4: END

Algorithm to POP an element from a stack
Step 1: IF TOP = NULL, then
                PRINT “UNDERFLOW”
                Goto Step 4
                [END OF IF]
Step 2: SET VAL = STACK[TOP]
Step 3: SET TOP = TOP - 1
Step 4: END

Algorithm for Peep Operation
Step 1: IF TOP=NULL, then
                PRINT “STACK IS EMPTY”
                Go TO Step 3
                [END OF IF]   
Step 2: RETURN STACK[TOP]
Step 3: END

Linked Representation of Stacks

In a linked stack, every node has two parts: first part stores data and other part stores the address of the next node.

The START pointer of the linked list is used as TOP.

If TOP=NULL, then it indicates that the stack is empty.

Algorithm to PUSH an element in a linked stack
Step 1: Allocate memory for the new node and name it as New_Node
Step 2: SET New_Node->DATA = VAL
Step 3: IF TOP = NULL, then
            SET New_Node->NEXT = NULL
            SET TOP = New_Node
        ELSE
            SET New_node->NEXT = TOP
            SET TOP = New_Node
        [END OF IF]
Step 4: END

Algorithm to POP an element from a stack
Step 1: IF TOP = NULL, then
                PRINT “UNDERFLOW”
                Go to Step 5
            [END OF IF]
Step 2: SET PTR = TOP
Step 3: SET TOP = TOP ->NEXT
Step 4: FREE PTR
Step 5: END

Queues

Queue is a data structure which stores its elements in an ordered manner. 

Queue is a FIFO (First In, First Out) data structure in which the elements that are inserted first are the first ones to be taken out.

The elements in a queue are added at one end called rear and removed from other end called front.

Example: 

Lets consider an example of Cinema Hall. People are standing in a line at the counter for a ticket forming a queue. Here, both the addition and deletion of person will be at different ends. The first person standing at the counter will get its ticket first and will be the one leaving the queue first. So here, deletion takes place from FRONT end and addition occurs at REAR end.

Array Representation of Queues

Queues can be easily represented using linear arrays.

Before inserting an element in a queue we must check for an overflow condition. 

Overflow occurs when we try to insert an element into a queue that is already full i.e. when rear=MAX-1, where MAX is maximum number of elements that a queue can hold.

Underflow occurs when we try to delete an element from a queue that is already empty.

When front=-1 and rear=-1, means there is no element in the queue.

Consider the queue:

Here, front=0 and rear=6. Insertion will be done at rear end.

If we want to delete an element from the queue, then the value of front will be incremented. Deletion can be done from front end only. 

Linked Representation of Queues

In linked queue, every queue have two parts: one contains the data and another part contains the address of the next node.

The FRONT indicates the START pointer of the linked list. We will also use another pointer called REAR which will store the address of the last element in the queue.

Insertion takes place at rear end and deletion takes place from front end. If FRONT=REAR=NULL, then queue is empty.

Types of Queues

The different types of queues are as follows:

1. Circular Queue
2. Deque
3. Priority Queue
4. Multiple Queue