Stacks and Queues

Stacks and Queues are linear data structures. A data structure is said to be linear if its elements are stored in a sequential manner. Therefore, in this data structure, a linear relationship is formatted between elements with the help of sequential memory locations.

Stacks

A stack is an ordered collection of an item in which new items may be inserted and the item may be deleted at one end, called the top of the stack. A stack is also known as LIFO structure because the element which is inserted last is the first element to be deleted.

By the definition of the stack, there is no upper limit on the number of items that can be kept in a stack. Pushing element results in a larger collection of items on stack and popping an element leads to a lesser collection of elements.

Representation of Stack

Primitive Operations on Stack

There are two primitive operations performed on the stack.

• Insertion(push)
• Deletion(pop)

Insertion Operation on Stack

The method of inserting an element into a stack is called the “Push” operation. It adds a new item to the top of the stack. The top is incremented by 1, each time when an element is inserted into the stack. A stack is also called a last-in-first-out structure where the element inserted at the last is the first to be deleted. Push operation is nothing but writing values into the stack. When the stack is full, no element can be inserted and this situation is called stack overflow.

Algorithm for Push Operation

Procedure push(S,top,MAX,item)

• Step 1: [check for overflow]
  • if to>MAX then
  • print “Stack overflow”
  • return
• otherwise, Step 2:
  • [increment top]
  • top = top+1
• Step 3: [insert the item into stack]
  • S[top] =item
• Step 4: return

Deletion Operations on Stack

The method of deleting an element from a stack is called “Pop” operation. It deletes the topmost elements present on the stack. The top is decremented by 1, each time when an element is deleted from the stack. A pop operation is nothing but deleting values from the stack. When the stack is empty, no element can be deleted and this situation is called stack underflow.

Algorithm for Pop Operation:

Procedure pop(S,top)

• Step 1: if top==-1 then
  • print “Stack underflow”
  • return
• Step 2: [Retrieve the top element]
  • item = S[top]
• Step 3: [decrement top]
  • top = top-1
• Step 4: [Return top element]
• Return (item)

Applications of Stacks

• a stack is used in a conversation of expression from infix notion to postfix notion
• stacks are used for the evaluation of infix and postfix forms.
• stacks are used in tree traversal techniques.
• recursive functions are implemented using stacks. The copies of variables at each level of recursion are stored in a stack.
• compilers use stacks in the syntax analysis phase to check whether a particular statement in a program is syntactically correct or not.
• computers use stack during interrupts and function calls. The information regarding actual parameters return values, return addresses and machines status is stored in a stack.
• stacks are used in depth-first search of a graph.

Queue

A queue is an ordered collection of items in which items may be inserted at one end known as rear end and items may be inserted at one end known as front end. A queue is also known as FIFO (first in first out) structure because the element which is inserted first will be the first element to be deleted. Diagrammatically it is shown as,

Primitive Operations

Two basics operations performed on queues are

• Insertion
• Deletion

Queues are implemented sequentially in C using an array and two variables ‘front’ and ‘rear’ to hold the position of first and last elements in queue respectively. A queue can have 0 to MAX-1 elements where MAX is the size of an array. Initially when the queue is empty, front=rear=-1

Insertion Operation

Insertion operation performs the following actions, If rear==MAX-1 i.e., the queue is full, then prints a message that ‘Queue is full’ and no new element can be added to a queue. Otherwise, increments rear by 1 and insert a new element at rear position.

Algorithm:

Inserting elements into a queue procedure Qinsert(Q,front,rear,MAX,item)

• Step 1: [check for overflow] if rear>max then
  • print “Queue overflow”
  • return
• Step 2: otherwise [increment rear]
  • rear=rear+1
• Step 3: [insert the element into queue]
  • Q[rear]=item
• Step 4: return

Deletion Operation:

Deletion operations perform the following actions. If the queue is empty which is given by front =-1, then prints a message that “no deletion is possible”. Otherwise, retrieves the front element and then increments front by 1.

Algorithm

Deletion from a Queue procedure Qdelete(Q,front,rear)

• Step 1: [check for empty] if front=-1
  • print “Queue empty”
• Step 2: otherwise, [retrieve element to be deleted]
  • Item=Q[front]
  • Q[front]=0
• Step 3: if front=rear then
  • begin
    • front=-1
    • rear=-1
  • end
  • goto step 5.
• Step 4: else front++
• Step 5: return (item)

Applications of Queue

• Queues are often used in the simulation of a real system when experimenting with real-time systems inexpensive or dangerous.
• Queues are used in the breadth-first traversal.
• In multiprogramming systems, different programs are put in a queue and are executed one after another in their respective time slots.
• In a computer network, different systems may request for the same resource. In such case resources requests are queued and serviced one by one.

Circular Queue

Circular Queue is a queue in which elements are stored in a circular manner. Circular queues are implemented using arrays. Let us consider an array CQ that contains ‘K’ elements in which CQ[1] comes after CQ[K] in the array. A liner queue can be transformed into a circular queue when the last room comes just before the first room.

In circular queue if an element is inserted when rear=K, then this element is assigned CQ[1] i.e., inserted of incrementing the rear value to K+1, the rear is reset to 1. If there is only a single element then front=rear and if that element is deleted than front=NULL and rear=NULL which indicates that queue is empty.

It is very easy to perform the insertion and deletion operation on a linear queue. At the same time, there are many drawbacks to implementing a simple queue. If an element is deleted, that empty memory location cannot be used again. Whereas in a circular queue it can be used.

It is possible to insert an element even at the beginning of the queue if that location is empty. Because of this limitation, disk space is wasted. In order to overcome these problems, a circular queue is implemented.

Priority Queue

A priority queue is a data structure similar to stacks and queue .the difference between them is that in stack and queue insertion and deletion operation are performed based on the order in which elements are inserted, but in a priority queue, the operation is performed are based on priority.

 Rules required for maintaining a priority queue

• preference should be given to the element with the highest priority
• If an element has the same priority, the processing is done based on the FIFO order.

Priority queues are generally used while scheduling jobs and in simulation systems. There are two types of the priority queues.

1. Maximum priority queue
2. Minimum priority queue

Max Priority Queue

in a max priority queue, elements can be inserted regardless of the order, but while performing deletion only the largest element is removed.

Min Priority Queue

a min-priority queue is the same as max priority queue but the only difference is that in the main priority queue only the smallest element is removed. Operations that can be applied to max priority queue and min priority queue are,

• pqinsert(Mpq, K): This operation inserts an element ‘K’ into Mpq.
• pqmaxdelete(Mpq): This operation deletes the largest element from the queue and returns the remaining elements in the queue.
• pqinsert(Minpq, K): This operation inserts an element ‘K’ into Minpq and is logically similar to pginsert of Mpg.
• pqmindelete(Minpq): This operation deletes the smallest element from the queue and returns the deleted value. After the element is deleted, this method can be applied recursively to delete the smallest element in ascending order.
• empty(pq): This operation is used to know if the max priority queue or min priority queue is empty or not.