Module 3

• Stacks: • Applications of Stacks:

• Introduction • Conversion of an infix expression
• Array Representation of Stacks into a postfix expression,
• Operations on a Stack • Evaluation of a postfix expression,
• Linked Representation of Stacks • Recursion.

• Queues: Introduction
• Array Representation of Queues,
• Linked Representation of Queues
• Types Of Queues: Circular Queue, Priority Queues
 Stacks
• Stack is a linear data structure which uses the principle i.e., the elements
in a stack are added and removed only from one end, which is called
the TOP.
• 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.

Smitha B, Assistant Professor, NIE 2

• Stacks in computer science is used
in function calls.
• Example: function A calls another
function B, Function B in turn calls
another function C, which calls
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 return
address 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 by popping back the stored Smitha B, Assistant Professor, NIE 3
return address
• Now when function E is executed, function D will be removed from the top of the
stack and executed.
• Once function D gets completely executed, function C will be removed from the
stack for execution.

• The whole procedure will be repeated until all the functions get executed.

Smitha B, Assistant Professor, NIE 4

• Main() calls average(), average() calls add()
• The system stack ensures a proper execution order of functions.
• Therefore, stacks are frequently used in situations where the order of processing is very
important, especially when the processing needs to be postponed until other conditions
are fulfilled.
• Stack can be implemented using array or linked list
Smitha B, Assistant Professor, NIE 5
 ARRAY REPRESENTATION OF STACKS
• In the computer’s memory, stacks can be represented as a linear array, Hence
stack size is fixed.
• Every stack has a pointer called TOP associated with it, which is used to store
the address of the topmost element of the stack.
• An element is added to or deleted from the position of TOP.
• There is another variable called MAX, which is the size of the stack - used to
represent the maximum number of elements that the stack can hold.
• If TOP == NULL, then it indicates that the stack is empty
• If TOP == MAX–1, then the stack is full.

Smitha B, Assistant Professor, NIE

Smitha B, Assistant Professor, NIE
 OPERATIONS ON A STACK
• A stack supports three basic operations: push, pop, peek, display.
• The push operation adds an element to the top of the stack
• 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.

Smitha B, Assistant Professor, NIE

 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, 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 indicated.

Smitha B, Assistant Professor, NIE

Smitha B, Assistant Professor, NIE
 Pop Operation
• The pop operation is used to delete the topmost element from a stack.
• However, before deleting the value, first check if TOP=NULL, for 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.

Smitha B, Assistant Professor, NIE

Smitha B, Assistant Professor, NIE
 Peek Operation
• Peek is an operation that returns the value of the topmost element of
the stack without deleting it from the stack.
• The Peek operation first checks if the stack is empty, i.e., if TOP =
NULL, then an appropriate message is printed, else the value is
returned.

Smitha B, Assistant Professor, NIE

#include<stdio.h> switch(choice)
#include<stdlib.h> {
int MAX, stack[10]; case 1: printf("Enter value to push ");
int push(int,int); scanf("%d",&num);
int pop(int); top = push(top, num);
void display(int); break;
int main() case 2: top = pop(top);
{ break;
int top=-1,choice,num; case 3: display(top);
printf("\n Enter the size of STACK: "); break;
scanf("%d",&MAX); case 4: printf("\n EXIT POINT\n");
while(1) exit(0);
{ break;
printf("\n1.PUSH\n 2.POP default: printf ("\nEnter Valid Choice\n");
\n3.DISPLAY\n4.EXIT"); } }
printf("\n Enter the Choice: "); return 0;
Smitha B, Assistant Professor,
Amruthasre NIE
istant Professor, NIE 14
scanf("%d",&choice); }
int push(int top, int num) int pop(int top) void display(int top)
{ { {
if(top >= MAX-1) if(top == -1) int i;
{ if(top == -1)
{
{
printf("\n OVERFLOW\n"); printf(“Underflow");
printf(“Underflow");
} } }
else else else
{ { {
top++; printf("\nPopped element: printf("\n STACK DATA\n");
stack[top]=num; %d",stack[top]); for(i=top; i>=0; i--)
} top--; {
return top; } printf("%d\n",stack[i]);
return top; }
}
} }
}

Smitha B, Assistant Professor, NIE

Drawback of array representation of stack
• This technique of creating a stack is easy, but the drawback is that the
array must be declared to have some fixed size.

• In case the stack is a very small one or its maximum size is known in
advance, then the array implementation of the stack gives an efficient
implementation.

• But if the array size cannot be determined in advance, then the other
alternative, i.e., linked representation, is used.

Smitha B, Assistant Professor, NIE

Lab Program - 5

Smitha B, Assistant Professor, NIE

 LINKED REPRESENTATION OF STACK
• In a linked stack, every node has two parts—one that stores data and
another that stores the address of the next node.

• The FIRST pointer of the linked list is used as TOP here.

• All insertions and deletions are done at the node pointed by TOP.

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

• It’s a singly linked list where insertion at front is PUSH operation and
deletion at front is POP operation.

Smitha B, Assistant Professor, NIE

#include <stdio.h>
printf("Enter your choice\n");
#include <stdlib.h>
printf("1. PUSH\n“);
printf("2. POP\n");
struct node printf("3. DISPLAY\n");
{ printf("4. EXIT\n");
int data; scanf("%d", &choice);
struct node *next; switch(choice)
}; {
typedef struct node NODE; case 1: printf(" Enter data to insert\n");
scanf("%d",&num);
NODE* push(NODE *, int); top = push(top, num);
NODE* pop(NODE *); break;
void display(NODE *); case 2: top = pop(top);
break;
void main() case 3: display(top);
{ break;
NODE *top=NULL; case 4: exit(0);
int num,choice; }
while(1) }
{ }
Smitha B, Assistant Professor, NIE
 PUSH (insert front)
NODE* push(NODE *top, int n)
{
NODE *new_node;
new_node = (NODE *)malloc(sizeof(struct node));
new_node->data = n;
new_node->next = top;
top = new_node;
return top;
}

Smitha B, Assistant Professor, NIE 20

 POP (delete front)
NODE * pop(NODE *top)
{
NODE *ptr;
if(top == NULL)
{
printf(“Stack is empty\n");
return top;
}
else
{
ptr = top;
top = top->next;
printf(“Popped data %d\n",ptr->data);
free(ptr);
return top;
}
Smitha B, Assistant
Amruthasree Professor,Professor,
V M, Assistant NIE NIE 21
}
 void display(NODE *top)
{
Display Stack NODE *ptr;
ptr = top;
if (ptr == NULL)
{
printf(“Stack is empty\n");
return;
}
printf("The stack data \n");
while(ptr != NULL)
{
printf("%d\n", ptr->data);
ptr = ptr->next;
}
return;
}
Smitha B, Assistant Professor, NIE