STACKS

Stack is an important data structure which stores its elements in an ordered manner. We
will explain the concept of stacks using an analogy. You must have seen a pile of plates where
one plate is placed on top of another. Now, when you want to remove a plate,you remove the top
most plate first. Hence, you can add and remove an element (i.e., a plate) only at/from one
position which is the topmost position.

A stack is a linear data structure which uses the same principle, i.e., the elements in a
stack are added and removed only from one end, which is called the TOP. Hence, a stack is
called a LIFO (Last-In-First-Out) data structure, as the element that was inserted last is the first
one to be taken out.

Applications of stack :

1) Function calls
2) Recursion
3) Evaluation of expression in a program.

Consider an example, where we are executing function A. In the course of its execution,
function A calls another function B. Function B in turn calls another function C, which alls
function D. In order to keep track of the returning point of each active function, a special stack
called system stack or call stack is used. Whenever a function calls another function, the calling
function is pushed onto the top of the stack. This is because after the called function gets
executed, the control is passed back to the calling function.

1
Implementation of Stacks

Stacks can be implemented using either arrays or linked lists.

ARRAY REPRESENTATION OF STACKS

In the computer’s memory, stacks can be represented as a linear array. Every stack has a
variable called TOP associated with it, which is used to store the address of the topmost element
of the stack. It is this position where the element will be added to or deleted from. There is
another variable called MAX, which is used to store the maximum number of elements that the
stack can hold.

If TOP = NULL or Top=-1, then it indicates that the stack is empty and if TOP = MAX–
1, then the stack is full.( why we have written MAX–1. It is because array indices start from 0.)

The stack in Fig. 7.4 shows that TOP = 4, so insertions and deletions will be done at this
position.

OPERATIONS ON A STACK
A stack supports three basic operations: push, pop, and peek(Top). The push operation
adds an element to the top of the stack and the pop operation removes the element from the top
of the stack. The peek operation returns the value of the topmost element of the stack.

Push Operation

The push operation is used to insert an element into the stack. The new element is added
at the topmost position of the stack. However, before inserting the value, we must first check if
TOP=MAX–1,because if that is the case, then the stack is full and no more insertions can be
done. If an attempt is made to insert a value in a stack that is already full, an OVERFLOW
message is printed. Consider the stack given in Fig.

2
 To insert an element with value 6, we first check if TOP=MAX–1. If the condition is false,
then we increment the value of TOP and store the new element at the position given by
stack[TOP]. Thus, the updated stack becomes as shown in Figure

Algorithm for PUSH:

IF TOP = MAX-1 // if stack is full

PRINT OVERFLOW;

Else

TOP <- TOP + 1; STACK[TOP];

End if;

END //End of Push

PROGRAM :

void push()

int pele;

if(top>=max-1)

printf("Stack is full");

else

printf("\nEnter value to Push to Stack :");

scanf("%d",&pele);

top++;

stack[top]=pele;

In the algorithm to insert an element in a stack. In Step 1, we first check for the
OVERFLOW condition. In Step 2, TOP is incremented so that it points to the next location in the
array. In Step 3, the value is stored in the stack at the location pointed by TOP.

3
 Pop Operation

The pop operation is used to delete the topmost element from the stack. However, before
deleting the value, we must first check if TOP=NULL or TOP=-1 because if that is the case, then
it means the stack is empty and no more deletions can be done. If an attempt is made to delete a
value from a stack that is already empty, an UNDERFLOW message is printed. Consider the
stack given in Fig.

To delete the topmost element, we first check if TOP=NULL or TOP=-1. If the condition
is false, then we decrement the value pointed by TOP. Thus, the updated stack becomes as shown
in Fig.

Algorithm Pop()
IF TOP <= -1 Then // If stack is empty
PRINT UNDERFLOW or EMPTY
Else // if stack not empty

VAL  STACK[TOP]; // move top element in to a val

variable
TOP  TOP – OR (TOP-1); // decrement top value by 1.
End if;
END//End of Pop

In Step 1, we first check for the UNDERFLOW condition. In Step 2, the value of the location in the
stack pointed by TOP is stored in VAL. In Step 3, TOP is decremented.
PROGRAM:
Void Pop()
{
Int val;
If(top<=-1)
printf(”\nSTACK IS EMPTY”);
Else
{ Val=stack[top];
printf(”\nPoped Element is : %d”,val);
top--;
} }

4
Peek(Top) Operation
Peek is an operation that returns the value of the topmost element of the stack without
deleting it from the stack.

ALGORITHAM :

Step 1: IF TOP = -1
PRINT STACK IS EMPTY
Goto Step 3
Step 2: RETURN STACK[TOP]
Step 3: END

PROGRAM:
Void peek()
{
If(top<=-1)
Printf(”Stack is Full”);
Else
Printf(”%d”,stack[top]);
}
The Peek operation first checks if the stack is empty, i.e., if TOP = -1, then an appropriate
message is printed, else the value is returned. Consider the stack given in Fig.

Here, the Peek operation will return 5, as it is the value of the topmost element of the stack.

Different Type of Questions On Stack :

---------------------------------------------
1. What is Stack? Explain Operations on Stack.[10 Marks]
2. What is Stack? Implement the Stack Operations?
3. Implement the Stack using Arrays.
4. What is Stack? Implement Static stack and its operations.
5. Explain in detail about Stack Operations
6. Explain about LIFO(Last In First Out) or FILO (First In Last Out) Data
Structure.

5
 Queues
A queue is a FIFO (First-In, First-Out) data structure in which the element that is
inserted first is the first one to be taken out. The elements in a queue are added at one end called
the REAR and removed from the other end called the FRONT.

Analogies using concept of queues.

 People waiting for a bus. The first person standing in the line will be the first one to get
into the bus.
 Cars lined at a toll bridge. The first car to reach the bridge will be the first to leave.
 Taking a Tickets in the Cinema Theater Queue.The First Person will collect the Ticket and
Enter into the Hall.

Implementation of Queues

Queues can be implemented by using either arrays or linked lists.

ARRAY REPRESENTATION OF QUEUEs

Queues can be easily represented using linear arrays. Every queue has front and rear
variables that point to the position from where deletion and insertions can be done respectively.

The array representation of a queue is shown in following Fig.

Operations on Queues

In the following Fig FRONT = 0 and REAR = 5.

12 9 7 18 14 36

0 1 2 3 4 5 6 7 8 9

Suppose we want to add another element with value 45, then REAR would be
incremented by 1 and the value would be stored at the position pointed by REAR. The queue
after addition would be as shown in Following Fig

6
 Queue after insertion of a new element

Here, FRONT = 0 and REAR = 6. Every time a new element has to be added, we repeat
the same procedure.
If we want to delete an element from the queue, then the value of FRONT will be
incremented. Deletions are done from only front end of the queue. The queue after deletion will
be as shown in Fig.

F R

Algorithms
To ADD elements into Queue

Before inserting an element in a queue, we must check for overflow conditions. An

overflow will occur when we try to insert an element into a queue that is already full.

When REAR = MAX – 1, where MAX is the size of the queue, we have an overflow
condition. Note that we have written MAX – 1 because the index starts from 0.

procedure Enqueue(element)
//insert item into the queue represented in Q(l:n)//
if rear = MAX-1 then // if queue is full
call QUEUE_FULL;
Else // queue is not full
rear  rear + 1; //forward rear pointer by 1.
Q(rear)element; // store element at rear end
End If;
End ADDQ;

Program :
Void Enqueue()
{
Int element;
If(rear>=MAX-1)
Printf(“QUEUE is Full”);
Else
{
Printf(“Enter the Element to insert : ”);
Scanf(“%d”,&element);
7
 Rear++;
Q[rear]=element;
}
}
To DELETE elements From Queue

Before deleting an element from a queue, we must check for underflow conditions. An
underflow condition occurs when we try to delete an element from a queue that is already
empty. If FRONT = –1 and REAR = –1, it means there is no element in the queue.

Algorithm:
--------------

procedure Dequeue()
//delete an element from queue
if front=-1 and rear=-1 then //if queue empty
call Queue is Empty;
else if front==rear //if rear and front both are equal
set rear =-1 and front=-1
else //if queue is not empty
front<-front+1; //forward front pointer by 1
End if;
end Dequeue;

Program:
-----------
Void Dequeue()
{
In dele;
If(front<=-1 && rear<=-1)
Printf(“Queue is empty”);
Else if (rear==front)
{
Rear=-1;
Front=-1;
}
Else
{
Dele=q[front];
Printf(“Dequeued Element is : %d”,q[front]);
Front++ (or )front +1;

8
TO DISPLAY THE ELEMENTS IN THE QUEUE:

To Display the Elements present the queue we will use the

Display operation to show. What are the elements present in the Queue.

Algorithm :

procedure Display()
//Displaying Elements in the queue
Decalre i=0
if front=-1 and rear=-1 then //if queue empty
call Queue is Empty;
else //if queue is not Empty
for loop: i=front and i<=rear //Display the values from front to rear
display values q[i]; //Displaying all values
End loop
End if
end display

Program:

Void display()
{
Int I;
If(front==-1 && rear==-1)
Printf(“Queue is Empty”);
Else
{
For(i=front;i<=rear;i++)
{
Printf(“Queue values are : %d”,q[i]);
}
}
}
Different Type of Questions On Queue :
---------------------------------------------
1. What is Queue? Explain Operations on Queue.
2. What is Queue? Implement the Queue Operations?
3. Implement the Queue using Arrays or FIFO Operations.
4. What is Queue? Implement Static Queue and its operations.
5. Explain in detail about Queue Operations
9


10