STACK

A stack is a linear data structure containing elements in which all insertions and deletions are made at one
end, called Top of the stack. The operations of a stack, if the elements A, B, C, D, and E, are inserted into
a stack, then the last element will be removed first i.e. ‘E’. Stack follows Last-In First-out mechanism.

In stack, the insertion operation is referred to as push, and the deletion operation as pop.

Overflow: If the stack is full, then print overflow.

Underflow: If the stack is empy, then print underflow.

Stack ADT
 push(): When we insert an element in a stack then the operation is known as a push. If the stack
is full then the overflow condition occurs.
 pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is
empty means that no element exists in the stack, this state is known as an underflow state.
 isEmpty(): It determines whether the stack is empty or not.
 isFull(): It determines whether the stack is full or not.'
 peek(): It returns the element at the given position.
 count(): It returns the total number of elements available in a stack.
 change(): It changes the element at the given position.
 display(): It prints all the elements available in the stack.

 The steps involved in the PUSH operation is given below:

 Before inserting an element in a stack, we check whether the stack is full.
 If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
 When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
 When the new element is pushed in a stack, first, the value of the top gets incremented,
i.e., top=top+1, and the element will be placed at the new position of the top.
 The elements will be inserted until we reach the max size of the stack.
  The steps involved in the POP operation is given below:

 Before deleting the element from the stack, we check whether the stack is empty.

 If we try to delete the element from the empty stack, then the underflow condition occurs.

 If the stack is not empty, we first access the element which is pointed by the top

 Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Stacks - Array Implementation:

To represent a stack is by using a one-dimensional array, stack[n], where n is the maximum number of
elements.
If the stack is empty then top=-1, If the stack is full, then top=n-1

For example, A stack containing six elements of integer data type, the stack is declared as int stack[6].

 Algorithm:

 begin

 if top = n then stack full

 top = top + 1

 stack (top) : = item;

 end

 Deletion of an element from a stack (Pop operation)

 The underflow condition occurs when we try to delete an element from an already empty stack.

 Algorithm :

 begin

 if top = 0 then stack empty;

 item := stack(top);

 top = top - 1;

 end;

 peek()

 Algorithm of peek() function −

 begin procedure peek()

 return stack[top]

 end procedure
  isfull()

 Algorithm of isfull() function −

 begin procedure isfull()

 if top equals to MAXSIZE

 return true

 else return false

 Endif

 end procedure

 isempty()

 Algorithm of isempty() function −

 begin procedure isempty ()

 if top less than 1

 return true

 else return false

 endif

 end procedure

What is a stack? How to implement stacks with example?

 #include<stdio.h>
 int stack[100],choice,n,top,x,i;
 void push(void);
 void pop(void);
 void display(void);
 int main()
 {
 //clrscr();
 top=-1;
 printf("\n Enter the size of STACK[MAX=100]:");
 scanf("%d",&n);
 printf("\n\t STACK OPERATIONS USING ARRAY");
 printf("\n\t--------------------------------");
 printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
 do
 {
 printf("\n Enter the Choice:");
 scanf("%d",&choice);
 switch(choice)
 {
 case 1:
 {
 push();
 break;
 }
 case 2:
 {
 pop();
 break;
 }
 case 3:
 {
 display();
 break;
 }
 case 4:
 {
 printf("\n\t EXIT POINT ");
 break;
 }
 default:
 {
 printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
 }

 }
 }
 while(choice!=4);
 return 0;
 }
 void push()
 {
 if(top>=n-1)
 {
 printf("\n\tSTACK is over flow");

 }
 else
 {
 printf(" Enter a value to be pushed:");
 scanf("%d",&x);
 top++;
 stack[top]=x;
 }
 }
 void pop()
  {
 if(top<=-1)
 {
 printf("\n\t Stack is under flow");
 }
 else
 {
 printf("\n\t The popped elements is %d",stack[top]);
 top--;
 }
 }
 void display()
 {
 if(top>=0)
 {
 printf("\n The elements in STACK \n");
 for(i=top; i>=0; i--)
 printf("\n%d",stack[i]);
 printf("\n Press Next Choice");
 }
 else
 {
 printf("\n The STACK is empty");
 }

 }

Stacks - Linked List Implementation:

A stack can be represented by using nodes of the linked list. Each node contains two fields: data (info)
and next (link). The data field of each node contains an item in the stack and the corresponding next field
points to the node containing the next item in the stack. The next field of the last node is null. The empty
stack is represented by setting top to null.
Adding a node to the stack (Push operation)
 Create a node first and allocate memory to it.
 If the list is empty then the item is to be pushed as the start node of the list. This includes
assigning value to the data part of the node and assign null to the address part of the node.
 If there are some nodes in the list already, then we have to add the new element in the beginning
of the list.

Deleting a node from the stack (POP operation)

 Check for the underflow condition: The underflow condition occurs when we try to pop from
an already empty stack. The stack will be empty if the head pointer of the list points to null.
 Adjust the head pointer accordingly: In stack, the elements are popped only from one end,
therefore, the value stored in the head pointer must be deleted and the node must be freed. The
next node of the head node now becomes the head node.

Display the nodes (Traversing)

 Copy the head pointer into a temporary pointer.
 Move the temporary pointer through all the nodes of the list and print the value field attached to
every node.
APPLICATIONS OF STACK:

o Evaluation of Arithmetic Expressions

o Backtracking
o Delimiter Checking
o Reverse a Data
o Processing Function Calls

1. Evaluation of Arithmetic Expressions

A stack is a very effective data structure for evaluating arithmetic expressions in programming
languages. An arithmetic expression consists of operands and operators.

In addition to operands and operators, the arithmetic expression may also include parenthesis like
"left parenthesis" and "right parenthesis".

Example: A + (B - C)

To evaluate the expressions, one needs to be aware of the standard precedence rules for
arithmetic expression. The precedence rules for the five basic arithmetic operators are:

Operators Associativity Precedence

^ exponentiation Right to left Highest followed by *Multiplication and /division

*Multiplication, /division Left to right Highest followed by + addition and - subtraction

 + addition, - subtraction Left to right lowest

Evaluation of Arithmetic Expression requires two steps:

o First, convert the given expression into special notation.
o Evaluate the expression in this new notation.

Notations for Arithmetic Expression

There are three notations to represent an arithmetic expression:

o Infix Notation
o Prefix Notation
o Postfix Notation

Infix Notation

The infix notation is a convenient way of writing an expression in which each operator is placed
between the operands. Infix expressions can be parenthesized or unparenthesized depending
upon the problem requirement.

Example: A + B, (C - D) etc.

All these expressions are in infix notation because the operator comes between the operands.

Prefix Notation

The prefix notation places the operator before the operands. This notation was introduced by the
Polish mathematician and hence often referred to as polish notation.

Example: + A B, -CD etc.

All these expressions are in prefix notation because the operator comes before the operands.

Postfix Notation

he postfix notation places the operator after the operands. This notation is just the reverse of
Polish notation and also known as Reverse Polish notation.

Example: AB +, CD+, etc.

All these expressions are in postfix notation because the operator comes after the operands.
Conversion of Arithmetic Expression into various Notations:

Infix Notation Prefix Notation Postfix Notation

A*B *AB AB*

(A+B)/C /+ ABC AB+C/

(A*B) + (D-C) +*AB - DC AB*DC-+

Let's take the example of Converting an infix expression into a postfix expression.

In the above example, the only change from the postfix expression is that the operator is placed
before the operands rather than between the operands.
Evaluating Postfix expression:

Stack is the ideal data structure to evaluate the postfix expression because the top element is
always the most recent operand. The next element on the Stack is the second most recent
operand to be operated on.

Before evaluating the postfix expression, the following conditions must be checked. If any one of
the conditions fails, the postfix expression is invalid.

o When an operator encounters the scanning process, the Stack must contain a pair of
operands or intermediate results previously calculated.
o When an expression has been completely evaluated, the Stack must contain exactly one
value.

Example:

Now let us consider the following infix expression 2 * (4+3) - 5.

Its equivalent postfix expression is 2 4 3 + * 5.

The following step illustrates how this postfix expression is evaluated.

2. Backtracking

Backtracking is another application of Stack. It is a recursive algorithm that is used for solving
the optimization problem.

3. Delimiter Checking

The common application of Stack is delimiter checking, i.e., parsing that involves analyzing a
source program syntactically. It is also called parenthesis checking. When the compiler translates
a source program written in some programming language such as C, C++ to a machine language,
it parses the program into multiple individual parts such as variable names, keywords, etc. By
scanning from left to right. The main problem encountered while translating is the unmatched
delimiters. We make use of different types of delimiters include the parenthesis checking (,),
curly braces {,} and square brackets [,], and common delimiters /* and */. Every opening
delimiter must match a closing delimiter, i.e., every opening parenthesis should be followed by a
matching closing parenthesis. Also, the delimiter can be nested. The opening delimiter that
occurs later in the source program should be closed before those occurring earlier.

Valid Delimiter Invalid Delimiter

While ( i > 0) While ( i >

/* Data Structure */ /* Data Structure

{ ( a + b) - c } { ( a + b) - c

To perform a delimiter checking, the compiler makes use of a stack. When a compiler translates
a source program, it reads the characters one at a time, and if it finds an opening delimiter it
places it on a stack. When a closing delimiter is found, it pops up the opening delimiter from the
top of the Stack and matches it with the closing delimiter.

On matching, the following cases may arise.

o If the delimiters are of the same type, then the match is considered successful, and the process
continues.
o If the delimiters are not of the same type, then the syntax error is reported.

When the end of the program is reached, and the Stack is empty, then the processing of the
source program stops.

Example: To explain this concept, let's consider the following expression.

[{a -b) * (c -d)}/f]

4. Reverse a Data:

To reverse a given set of data, we need to reorder the data so that the first and last elements are
exchanged, the second and second last element are exchanged, and so on for all other elements.

Example: Suppose we have a string Welcome, then on reversing it would be Emoclew.

There are different reversing applications:

o Reversing a string
o Converting Decimal to Binary
Reverse a String

A Stack can be used to reverse the characters of a string. This can be achieved by simply pushing
one by one each character onto the Stack, which later can be popped from the Stack one by one.
Because of the last in first out property of the Stack, the first character of the Stack is on the
bottom of the Stack and the last character of the String is on the Top of the Stack and after
performing the pop operation in the Stack, the Stack returns the String in Reverse order.

Converting Decimal to Binary:

Although decimal numbers are used in most business applications, some scientific and technical
applications require numbers in either binary, octal, or hexadecimal. A stack can be used to
convert a number from decimal to binary/octal/hexadecimal form. For converting any decimal
number to a binary number, we repeatedly divide the decimal number by two and push the
remainder of each division onto the Stack until the number is reduced to 0. Then we pop the
whole Stack and the result obtained is the binary equivalent of the given decimal number.

Example: Converting 14 number Decimal to Binary:

In the above example, on dividing 14 by 2, we get seven as a quotient and one as the reminder,
which is pushed on the Stack. On again dividing seven by 2, we get three as quotient and 1 as the
reminder, which is again pushed onto the Stack. This process continues until the given number is
not reduced to 0. When we pop off the Stack completely, we get the equivalent binary
number 1110.

5. Processing Function Calls:

Stack plays an important role in programs that call several functions in succession. Suppose we
have a program containing three functions: A, B, and C. function A invokes function B, which
invokes the function C.

When we invoke function A, which contains a call to function B, then its processing will not be
completed until function B has completed its execution and returned. Similarly for function B
and C. So we observe that function A will only be completed after function B is completed and
function B will only be completed after function C is completed. Therefore, function A is first to
be started and last to be completed. To conclude, the above function activity matches the last in
first out behavior and can easily be handled using Stack.
Consider addrA, addrB, addrC be the addresses of the statements to which control is returned
after completing the function A, B, and C, respectively.

The above figure shows that return addresses appear in the Stack in the reverse order in which
the functions were called. After each function is completed, the pop operation is performed, and
execution continues at the address removed from the Stack. Thus the program that calls several
functions in succession can be handled optimally by the stack data structure. Control returns to
each function at a correct place, which is the reverse order of the calling sequence.

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective
of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of
another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.
Let rod 1 = 'A', rod 2 = 'B', rod 3 = 'C'.
An example with 2 disks :
Step 1 : Shift first disk from 'A' to 'B'.

Step 2 : Shift second disk from 'A' to 'C'.

Step 3 : Shift first disk from 'B' to 'C'.

An example with 3 disks :
Step 1 : Shift first disk from 'A' to 'C'.
Step 2 : Shift second disk from 'A' to 'B'.
Step 3 : Shift first disk from 'C' to 'B'.

Step 4 : Shift third disk from 'A' to 'C'.

Step 5 : Shift first disk from 'B' to 'A'.

Step 6 : Shift second disk from 'B' to 'C'.
Step 7 : Shift first disk from 'A' to 'C'.
 (Notice the gaps)
The pattern here is :
- Shift 'n-1' disks from 'A' to 'B', using C.
- Shift last disk from 'A' to 'C'.
- Shift 'n-1' disks from 'B' to 'C', using A.

4. Image illustration for 3 disks

Recursion and Stack

When a function is called, it occupies memory in the stack to store details about the execution of
the function. And when the function ends, the memory occupied by it is also released. Now in recursion,
as we know a function is called in itself. Hence at every function call, a block of memory is created in the
stack to hold the information of the currently executing function. When the function ends, it returns to it’s
calling statement written in the outer function i.e., an outer function is resumed from where it stopped.
Let’s see the memory structure in the above example for n=3:
 Queue
A Queue is an ordered list in which all insertions take place at one end, called the rear and all deletions
are take place at the other end, called the front. A queue is a first-in-first-out (FIFO) linear data structure.
Queues are represented in the computer memory by means of arrays or linear linked lists.

Queue ADT
 Mainly the following four basic operations are performed on queue:
Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow
condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which
they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from queue.
Rear: Get the last item from queue.

Operations on queue:
 Queue operations may involve initializing or defining the queue, utilizing it, and then completely
erasing it from the memory. Here we shall try to understand the basic operations associated with
queues −
 enqueue() − add (store) an item to the queue.
 dequeue() − remove (access) an item from the queue.
 Few more functions are required to make the above-mentioned queue operation efficient. These
are
 peek() − Gets the element at the front of the queue without removing it.
 isfull() − Checks if the queue is full.
 isempty() − Checks if the queue is empty.

peek()
 This function helps to see the data at the front of the queue.
 Algorithm
 begin procedure
 peek return queue[front]
 end procedure
isfull()
 As we are using single dimension array to implement queue, we just check for the rear pointer to
reach at MAXSIZE to determine that the queue is full. In case we maintain the queue in a circular
linked-list, the algorithm will differ. Algorithm of isfull() function −
 Algorithm
 begin procedure isfull
 if rear equals to MAXSIZE
 return true
 else return false
  Endif
 end procedure
 isempty()
 Algorithm
 begin procedure isempty
 if front is less than MIN OR front is greater than rear
 return true
 else return false
 endif
 end procedure
enqueue operation
 Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively
difficult to implement than that of stacks.
 The following steps should be taken to enqueue (insert) data into a queue −
 Step 1 − Check if the queue is full.
 Step 2 − If the queue is full, produce overflow error and exit.
 Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
 Step 4 − Add data element to the queue location, where the rear is pointing.
 Step 5 − return success.


Dequeue Operation
 Accessing data from the queue is a process of two tasks − access the data where front is pointing
and remove the data after access. The following steps are taken to perform dequeue operation −
 Step 1 − Check if the queue is empty.
 Step 2 − If the queue is empty, produce underflow error and exit.
 Step 3 − If the queue is not empty, access the data where front is pointing.
 Step 4 − Increment front pointer to point to the next available data element.
 Step 5 − Return success.
Array Implementation of Queues:
A Queue will be maintained by a linear array, queue[n], where n is the maximum number of elements in
the queue. Here we can define two variables – front and rear.
 The condition front = -1 will indicate the queue is empty. Now, rear= -1
 Whenever an item is deleted from the queue, the front is incremented by 1.
front = front + 1
 Similarly, whenever an item is added to the queue, the rear is incremented by 1.
rear = rear + 1
 After n insertions, the rear element of the queue will occupy queue [n-1].
Operations on a Queue:
 The insert() method: This method adds an item to the rear end of the Queue, if the queue is not
full. In case Queue is full the method displays an error message.
 The remove() method: This method checks that the queue is not empty. Removal always starts
by obtaining the value at front and then incrementing front.
 The peek() method: The peek() method is returns the value at front.
 The isEmpty() method: The isEmpty() method is checking elements are existed or not.

Operations:
1. Queue is empty.
front = -1
rear= -1

2. Insert A, B, C into the queue

front = 0
rear= 2

3. Delete one item from the queue

front = 1
rear= 2

4. Insert D, E, F into the queue

front = 1
rear= 4
Now queue is full – no space available for F.
Linked Implementation of Queues:
Linked queue implementation has two advantages over the array implementation.
1. It is faster – locations for insertion and deletion are same
2. It wastes no space – removed nodes are deleted by the automatic garbage collector process.
Queue uses single-linked list. we keep two pointers, front and rear.
Operations:
1. Inserting first item(‘A’)
front = rear = p;
rear.next = null;

2. Inserting second item(‘B’)

rear = p;
front.next = rear;
 rear.next = null;

3. Inserting two items(‘C’, ‘D’)

rear.next = p;
rear = p;
rear.next = null;

4. Deleting one item(‘A’)

Item = front.data;
front = front.next;

Types of Queue

There are four different types of queue that are listed as follows –

o Simple Queue or Linear Queue

o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Let's discuss each of the type of queue.

Simple Queue or Linear Queue
In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which the
deletion takes place is known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even though
the space is available in a Linear Queue. In this case, the linear Queue shows the overflow
condition as the rear is pointing to the last element of the Queue.

To know more about the queue in data structure, you can click the link
- https://www.javatpoint.com/data-structure-queue

Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue
except that the last element of the queue is connected to the first element. It is also known as
Ring Buffer, as all the ends are connected to another end. The representation of circular queue is
shown in the below image -

The drawback that occurs in a linear queue is overcome by using the circular queue. If the empty
space is available in a circular queue, the new element can be added in an empty space by simply
incrementing the value of rear. The main advantage of using the circular queue is better memory
utilization.

Priority Queue
It is a special type of queue in which the elements are arranged based on the priority. It is a
special type of queue data structure in which every element has a priority associated with it.
Suppose some elements occur with the same priority, they will be arranged according to the
FIFO principle. The representation of priority queue is shown in the below image -

Insertion in priority queue takes place based on the arrival, while deletion in the priority queue
occurs based on the priority. Priority queue is mainly used to implement the CPU scheduling
algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can be inserted in arbitrary
order, but only smallest can be deleted first. Suppose an array with elements 7, 5, and 3 in the
same order, so, insertion can be done with the same sequence, but the order of deleting the
elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be inserted in arbitrary
order, but only the largest element can be deleted first. Suppose an array with elements 7, 3, and 5
in the same order, so, insertion can be done with the same sequence, but the order of deleting the
elements is 7, 5, 3.

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from both ends of the
queue either from the front or rear. It means that we can insert and delete elements from both
front and rear ends of the queue. Deque can be used as a palindrome checker means that if we
read the string from both ends, then the string would be the same.

Deque can be used both as stack and queue as it allows the insertion and deletion operations on
both ends. Deque can be considered as stack because stack follows the LIFO (Last In First Out)
principle in which insertion and deletion both can be performed only from one end. And in
deque, it is possible to perform both insertion and deletion from one end, and Deque does not
follow the FIFO principle.
The representation of the deque is shown in the below image -

To know more about the deque, you can click the link - https://www.javatpoint.com/ds-deque

There are two types of deque that are discussed as follows -

o Input restricted deque - As the name implies, in input restricted queue, insertion operation can
be performed at only one end, while deletion can be performed from both ends.

o Output restricted deque - As the name implies, in output restricted queue, deletion operation
can be performed at only one end, while insertion can be performed from both ends.

Now, let's see the operations performed on the queue.

Operations performed on queue
The fundamental operations that can be performed on queue are listed as follows -

o Enqueue: The Enqueue operation is used to insert the element at the rear end of the queue. It
returns void.
o Dequeue: It performs the deletion from the front-end of the queue. It also returns the element
which has been removed from the front-end. It returns an integer value.
o Peek: This is the third operation that returns the element, which is pointed by the front pointer in
the queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue is completely full.
o Queue underflow (isempty): It shows the underflow condition when the Queue is empty, i.e., no
elements are in the Queue.

Now, let's see the ways to implement the queue.

Ways to implement the queue

There are two ways of implementing the Queue:

o Implementation using array: The sequential allocation in a Queue can be implemented using an
array. For more details, click on the below link: https://www.javatpoint.com/array-representation-
of-queue
o Implementation using Linked list: The linked list allocation in a Queue can be implemented
using a linked list. For more details, click on the below link:

Priority Queue: Priority Queues may be used for task scheduling in computers, where some
programs and activities should be executed as sooner than others and therefore given a higher
priority. In a time-sharing system, programs of high priority are processed first, and programs
with the same priority form a standard FIFO Queue. In priority Queue, items are removed
according to their priority and their current queue position.

A priority queue is essentially a list of items in which each item has associated with it a priority.
----------------------------------------------------------------------------------------------------------------
Deque ADT:

A deque is a double-ended queue. we can insert at either end and delete them from either end. Methods
are addFirst (), addLast (), removeFirst () and removeLast ().

To addFirst () and removeFirst () (or their equivalents on the right), then the deque acts like a stack. To
addFirst () and removeLast () (or the opposite pair), then it acts like a queue.

A deque provides a more versatile data structure than either a stack or a queue, and is sometimes used in
container class libraries to serve both purposes. However, it is not used as often as stacks and queues.

The functions of deque ADT are as follows:

addFirst (item) Inserts an item at the left side of deque
addLast (item) Inserts an item at the right side of deque
removeFirst () Deletes an item from the left of deque
removeLast () Deletes an item from the right of deque
getFirst () Returns an item from the left, without deleting the item
getLast() Returns an item from the right, without deleting the item
size () Returns the current number of items in the deque
isEmpty () Returns true, if deque is empty else returns false.

Array Implementaion of Deque

first last 0 1 2 3 4 5

(a) Add A, B, C, D to the right of the 1 3 B C D

deque and delete one item from left

(b) Insert E into the right of the deque 1 4 B C D E

(c) Delete two items from the B C right 1 2

(d) P, Q, R added to the left of the deque 4 2 P B C R Q

(e) Delete one item from the left 5 2 P B C Q

(f) Add X to the left of the deque 4 2 P B C X Q

(g) Insert Y into the right of the deque 4 2 P B C Y X Q

 (h) Add Z to the right of the deque Deque is full

Linked Implementation of Deque

A deque is implemented by using a doubly linked list with references to first and last. The figure
given below illustrates the linked deque operations. Each node of the doubly linked list contains three
fields: data, prev and next. The fields prev and next refer to the node itself.

first last
(a) addFirst(‘A’); x C B A

addFirst(‘B’);
addFirst(‘C’);

first last
(b) addLast(‘D’); x C B A D E

addLast(‘E’);

first last
(c) removeFirst(); x C X B A D E x

first last
(d) removeLast(); X B A D x E x

first last
(e) After deleting first x B A D x
and last items
----------------------------------------------------------------------------------------------------------------

Circular Queue

A queue represented using array when the REAR pointer reaches at the end, insertion will be
denied even if room is available at the front. One way to remove this is using a circular array is the same
as ordinary array say, A[1……N], but logically it implies that A[1) comes after A[N] or after A[N], A[1]
appears.
Both pointers will move in clockwise direction. This is controlled by the MOD operation; for example, if
the current pointer is at i then shift to the next location will be i MOD LENGH+1, 1≤ i≤ LENGTH (where
LENGTH is the queue length). Thus, if i =LEGNGTH (that is at the end), then next position for the
pointer is 1.
With this principle the two states of the queue regarding its empty or full will be decided as:
Circular queue is empty
FRONT = 0
REAR = 0

Circular queue is full

FRONT = (REAR MOD LENGH) + 1
Following two algorithms describe the insertion and deletion operations on a circular queue.
Algorithm ENCQUEUE(ITEM)

Input: An element ITEM to be inserted into the circular queue.

Output: Circular queue with the ITEM at FRONT, if the queue is not full.
Date Structures : CQ be the array to represent the circular queue. Two pointers FRONT and
REAR are known.

Steps
1. If (FRONT = 0) then // When queue is empty
1. FRONT = 1
2. REAR = 1
3. CQ[FRONT] = ITEM
2. Else // Queue is not empty
1. Next = (REAR MOD LENGH) +1
2. If (next ≠ FRONT) then // If queue is not full
1. REAR = next
2. CQ[REAR] = ITEM
3. ELSE
1. Print “Queue is full”
4. End1f
3. End1f
4. Stop

Algorithm DECQUEUE( )
Input: A queue CQ with elements. Two pointers FRONT and REAR are known.
Output: The deleted element is ITEM if the queue is not empty.
Date Structures : CQ is the array representation of circular queue.
Steps
1. If (FRONT = 0) then
1. Print “Queue is empty”
2. Exit
2. Else // Queue is not empty
1. ITEM = CQ[FRONT]
2. If (FRONT = REAR) then // If the queue contains single element
1. FRONT = 0
2. REAR = 0
3. Else
1. FRONT = (FRONT MOD LENGH) + 1
4. End1f
3. End1f
4. Stop

Applications of Queue:

1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
2. Queues are used in asynchronous transfer of data (where data is not being transferred at the same
rate between two processes) for eg. pipes, file IO, sockets.
3. Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.
4. Queue are used to maintain the play list in media players in order to add and remove the songs
from the play-list.
5. Queues are used in operating systems for handling interrupts.