DS Module 2

CP 1243 DATA STRUCTURES IN C Module 2
Module II:
Stack: Representation and operations on Stack using arrays and linked list, application of Stack Polish
Notation- Conversions to Infix, postfix and prefix notations, Infix to postfix conversion using stack,
Evaluation of postfix expression using stack Queue: Implementation and operations on Queue using
arrays and linked list, Deque- Types Input and output restricted, Priority Queues-Array and Linked
list representation.
STACK DATA STRUCTURE
A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is
named stack as it behaves like a real-world stack,for example – a deck of cards or a pile of plates, etc.
A real-world stack allows operations at one end only. For example, we can place or remove a card or
plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only.
At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first- out. Here, the element which
is placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is called
PUSH operation and removal operation is called POP operation.
Stack Representation
The following diagram depicts a stack and its operations –
S2 BCA Page 1
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack
can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going
to implement stack using arrays, which makes it a fixed size stack implementation.
Basic Operations
Stack operations may involve initializing the stack, using it and then de- initializing it. Apart
from these basic stuffs, a stack is used for the following two primary operations −
 push() − Pushing (storing) an element on the stack.
 pop() − Removing (accessing) an element from the stack. When data is PUSHed
onto stack.
To use a stack efficiently, we need to check the status of stack as well. For the same purpose,
the following functionality is added to stacks −
 peek() − get the top data element of the stack, without removing it.
 isFull() − check if stack is full.
 IsEmpty() - check if stack is empty.
At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer
always represents the top of the stack, hence named top. The top pointer provides top
value of the stack without actually removing it.
PUSH OPERATION
The process of putting a new data element onto stack is known as a Push Operation. Push
operation involves a series of steps −
 Step 1 − Checks if the stack is full.
 Step 2 − If the stack is full, produces an error and exit.
 Step 3 − If the stack is not full, increments top to point next emptyspace.
 Step 4 − Adds data element to the stack location, where top is pointing.
 Step 5 − Returns success.
S2 BCA Page 2
If the linked list is used to implement the stack, then in step 3, we need to allocate space
dynamically.
Algorithm for PUSH Operation
A simple algorithm for Push operation can be derived as follows −

Push (int stack[], int item)
{
if(IsStackFull()
{
printf(“\n Stack Overflow”);
exit(0);
}
top++;
stack[top]=item;
}
POP OPERATION
Accessing the content while removing it from the stack, is known as a Pop Operation. In an
array implementation of pop() operation, the data elementis not actually removed, instead top
is decremented to a lower position in the stack to point to the next value. But in linked-list
implementation, pop() actually removes data element and deallocates memory space.
A Pop operation may involve the following steps −
 Step 1 − Checks if the stack is empty.
S2 BCA Page 3
 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is
pointing.
 Step 4 − Decreases the value of top by 1.
 Step 5 − Returns success.
Algorithm for Pop Operation
A simple algorithm for Pop operation can be derived as follows −

Pop (int stack[])
{
int item;
if(IsStackEmpty()
{
printf(“\n Stack Underflow”);
exit(0);
}
item=stack[top];
top--;
return(item);
}
peek()
Algorithm of peek() function −
int peek()
S2 BCA Page 4
{
return stack[top];
}
isfull()
Algorithm of isfull() function −
bool isfull()
{
if(top == MAXSIZE)
return true;
else
return false;
}
isempty()
Algorithm of isempty() function –

bool isempty()
{
if(top == -1)return
true;
else
return false;
}
(Implementation of Stack using Array)
STACK USING LINKED LIST
 The major problem with the stack implemented using array is, it works only for fixed
number of data values. That means the amount of data must be specified at the
beginning of the implementation itself. Stack implementedusing array is not suitable,
when we don't know the size of data which we are going to use.
S2 BCA Page 5
 A stack data structure can be implemented by using linked list data structure. The
stack implemented using linked list can work for unlimited number of values. That
means, stack implemented using linked list works for variable size of data. So, there
is no need to fix the size at the beginning of the implementation. The Stack
implemented using linked list can organize as many data values as we want.
 In linked list implementation of a stack, every new element is inserted as 'top'

element. That means every newly inserted element is pointed by 'top'. Whenever we
want to remove an element from the stack, simply remove the node which is pointed
by 'top' by moving 'top' to its next node in the list. The next field of the first
element must be always NULL.
Example
In above example, the last inserted node is 99 and the first inserted nodeis 25. The order of
elements inserted is 25, 32,50 and 99.
Operations
To implement stack using linked list, we need to set the following things
before implementing actual operations.
Step 1: Include all the header files which are used in the program. And declare all
the user defined functions.
Step 2: Define a 'Node' structure with two members data and next.
Step 3: Define a Node pointer 'top' and set it to NULL.

Step 4: Implement the main method by displaying Menu with list of operations and
S2 BCA Page 6
make suitable function calls in the main method. push(value) - Inserting an

element into the Stack
To insert a new node into the stack...
Step 1: Create a newNode with given value.
Step 2: Check whether stack is Empty (top == NULL)
Step 3: If it is Empty, then set newNode → next = NULL.
Step 4: If it is Not Empty, then set newNode → next = top.
Step 5: Finally, set top = newNode.

pop() - Deleting an Element from a Stack
Step 1: Check whether stack is Empty (top == NULL).
Step 2: If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and
terminate the function
Step 3: If it is Not Empty, then define a Node pointer 'temp' and setit to 'top'.
Step 4: Then set 'top = top → next'.
Step 7: Finally, delete 'temp' (free(temp)).
display() - Displaying stack of elements
Step 1: Check whether stack is Empty (top == NULL).
Step 2: If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
Step 3: If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
Step 4: Display 'temp → data --->' and move it to the next node. Repeat the same until
temp reaches to the first node in the stack (temp → next != NULL).
Step 5: Finally! Display 'temp → data ---> NULL'.
(Program to implement Stack Using Linked List)
Application of Stack
The stack data structure can be use to implement the following concepts:
S2 BCA Page 7
1. Parsing
2. Recursive Function
3. Calling Function
4. Expression Evaluation
5. Expression Conversion
o Infix to Postfix
o Infix to Prefix
o Postfix to Infix
o Prefix to Infix
6. Towers of Hanoi
1. Convert decimal to Binary Using Stack [Decimal to Binary Conversion ]
Decimal number can be converted into equivalent binary number using stack.
2. Reverse String Using Stack : Data Structure
Accept Characters continuously and push characters onto stack.Accept characters till
occurrence newline character is encountered.
3. Evaluation of postfix expression : Using stack
Expression Representation Techniques :
 Infix Expression
 Prefix Expression
 Postfix Expression
Expression Example Note
Infix a+b Operator Between Operands
S2 BCA Page 8
Prefix +ab Operator before Operands
Postfix ab+ Operator after Operands
Generally postfix expressions are free from Operator Precedence thats why they are
preferred in Computer system.Computer System Uses Postfix form to represent
expression. Following is the example that shows evaluation of the Postfix expression using
stack as data structure.
EXPRESSION PARSING
The way to write arithmetic expression is known as a notation. An arithmetic expression can
be written in three different but equivalent notations, i.e., without changing the essence or
output of an expression. These notations are −
 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse-Polish) Notation
These notations are named as how they use operator in expression.

Infix Notation
Operators are written in-between their operands. We write expression in infix notation,
e.g. a - b + c, where operators are used in-between operands. It is easy for us humans to read,
write, and speak in infix notation but the same does not go well with computing devices. An
algorithm to process infix notation could be difficult and costly in terms of time and space
consumption.
Prefix Notation (Polish Notation)
Operators are written before their operands. In this notation, operator is prefixed to
operands, i.e. operator is written ahead of operands. For example, +ab. This is equivalent to
its infix notation a + b. Prefix notation is also known as Polish Notation.
Postfix Notation (Reversed Polish Notation)
Operators are written after their operands. This notation style is knownas Reversed Polish
Notation. In this notation style, the operator is postfixed to the operands i.e., the operator is
S2 BCA Page 9
written after the operands. For example, ab+. This is equivalent to its infix notation a + b.
The following table briefly tries to show the difference in all three notations −
Sr.No
Infix Notation Prefix Notation Postfix Notation
.
1 a+b +ab ab+
2 (a + b) ∗ c ∗+abc ab+c∗
3 a ∗ (b + c) ∗a+bc abc+∗
4 a/b+c/d +/ab/cd ab/cd/+
5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗
6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-
Parsing Expressions
As we have discussed, it is not a very efficient way to design an algorithm or program to

parse infix notations. Instead, these infix notations are first converted into either postfix or
prefix notations and then computed.
To parse any arithmetic expression, we need to take care of operator precedence and
associativity also.
Precedence
When an operand is in between two different operators, which operator will take the operand
first, is decided by the precedence of an operator over others. For example −
As multiplication operation has precedence over addition, b * c will be evaluated first. A

table of operator precedence is asfollows:
Operators Symbols
Parenthesis { }, ( ), [ ]
S2 BCA Page 10
Exponential notation ^
Multiplication and *, /
Division
Addition and +, -
Subtraction
Associativity
Associativity describes the rule where operators with the same precedence appear in an
expression. For example, in expression a + b − c, both
+ and – have the same precedence, then which part of the expression will be evaluated first,
is determined by associativity of those operators. Here, both + and − are left associative, so
the expression will be evaluated as (a + b) − c.
Precedence and associativity determines the order of evaluation of an expression. Following

is an operator precedence and associativity table (highest to lowest) −
Sr.No. Operator Precedence Associativity
1 Exponentiation ^ Highest Right to Left
2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left to Right
3 Addition ( + ) & Subtraction ( − ) Lowest Left to Right

The above table shows the default behavior of operators. At any point of time in expression
evaluation, the order can be altered by using parenthesis.
For example −
In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence
over addition. We here use parenthesis for a +b to be evaluated first, like (a + b)*c.
Postfix Evaluation Algorithm
Step 1 − scan the expression from left to rightStep 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation Step 4 − store the
output of step 3, back to stack
S2 BCA Page 11
Step 5 − scan the expression until all operands are consumed Step 6 − pop the stack and
perform operation
POLISH NOTATION
Polish notation (PN), also known as normal Polish notation (NPN), Łukasiewicz notation,
Warsaw notation, Polish prefix notation or simply prefix notation, is a form of notation for
logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left
of their operands. If the arity of the operators is fixed, the result is a syntax lacking
parentheses or other brackets that can still be parsed without ambiguity.
The Polish logician Jan Łukasiewicz invented this notation in 1924 in order to simplify
sentential logic.
The term Polish notation is sometimes taken (as the opposite of infix notation) to also
include Polish postfix notation, or reverse Polishnotation (RPN), in which the operator is
placed after the operands.
When Polish notation is used as a syntax for mathematical expressions by programming
language interpreters, it is readily parsed into abstract syntax trees and can, in fact, define a
one-to-one representation for the same. Because of this, Lisp (see below) and related
programming languages define their entire syntax in terms of prefix notation (and others use
postfix notation).
Arithmetic
The expression for adding the numbers 1 and 2 is, in prefix notation, written "+ 1 2" rather
than "1 + 2". In more complex expressions, the operators still precede their operands, but the
operands may themselves be nontrivial expressions including operators of their own. For
instance, the expression that would be written in conventional infix notation as
(5 − 6) × 7
can be written in prefix as
× (− 5 6) 7
Since the simple arithmetic operators are all binary (at least, in arithmetic contexts), any
prefix representation thereof is unambiguous, and bracketing the prefix expression is
S2 BCA Page 12
unnecessary. As such, the previous expression can be further simplified to

×−567
The processing of the product is deferred until its two operands are available (i.e., 5 minus
6, and 7). As with any notation, the innermost expressions are evaluated first, but in
prefix notation this "innermost-ness" canbe conveyed by order rather than bracketing.
In the classical notation, the parentheses in the infix version were required, since
moving them
5 − (6 × 7)
or simply removing them5 − 6 × 7

would change the meaning and result of the overall expression, due to the
precedence rule.
Similarly
5 − (6 × 7)
can be written in Polish notation as
−5×67
Computer Programming
Prefix notation has seen wide application in Lisp s-expressions, where the brackets are
required since the operators in the language are themselves data (first-class functions).
Lisp functions may also have variable arity.The Tcl programming language, much
like Lisp also uses Polish notation through the mathop library. The Ambi programming
language uses Polish Notation for arithmetic operations and program construction.
The postfix reverse Polish notation is used in many stack-based programming languages like
PostScript and Forth. CoffeeScript syntax also allows functions to be called using prefix
notation, while still supporting the unary postfix syntax common in other languages.
The number of return values of an expression equals the difference between the number of
operands in an expression and the total arity of the operators minus the total number of return
values of the operators. Here is an implementation (in pseudocode) of prefix evaluation using
a stack. Note that under this implementation the input string is scanned from right to left. This
differs from the algorithm described above in which the string is processed from left to right.
S2 BCA Page 13
Both algorithms compute the same value for all valid strings.
Scan the given prefix expression from right to left

for each symbol
{
if operand then
push onto stack if
operator then
{
operand1=pop stack
operand2=pop stack
compute operand1 operator operand2push
result onto stack
}
}
return top of stack as result
Example
− × ÷ 15 − 7 + 1 1 3 + 2 + 1 1
Token Action Stack Notes
1 Operand 1 Push onto stack.

Pop the two operands (1, 1), calculate (1 + 1 = 2)and
+ Operator 2
push onto stack.
+ Operator 4
push onto stack.
S2 BCA Page 14

+ Opera-tor 234
push onto stack.
Pop the two operands (7, 2), calculate (7 − 2 = 5)and
− Operator 534
push onto stack.
15 Operand 15 5 3 4 Push onto stack.
Pop the two operands (15, 5), calculate (15 ÷ 5 = 3)and

÷ Operator 334
push onto stack.
Pop the two operands (3, 3), calculate (3 × 3 = 9)and
× Operator 94
push onto stack.
Pop the two operands (9, 4), calculate (9 − 4 = 5)and
− Operator 5
push onto stack.
The result is at the top of the stack.
QUEUE DATA STRUCTURE

 Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a
queue is open at both its ends. One end is always used to insert data (enqueue) and the
other is used to remove data (dequeue).
 Queue follows First- In-First-Out methodology, i.e., the data item stored first will be
accessed first.
A real-world example of queue can be a single-lane one-way road, where the vehicle enters
S2 BCA Page 15
first, exits first. More real-world examples can be seen as queues at the ticket windows and
bus-stops.
Queue Representation
The following diagram given below tries to explain queue representation as data structure −
As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and
Structures. For the sake of simplicity, we shall implement queues using one-dimensional
array.
Basic Operations
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 queueoperation efficient.
These are −
 peek() − Gets the element at the front of the queue withoutremoving it.
 isfull() − Checks if the queue is full.
 isempty() − Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and while
enqueing (or storing) data in the queue we take help of rear pointer.
peek()
This function helps to see the data at the front of the queue. The algorithmof peek() function
S2 BCA Page 16
is as follows:
int peek()
{
return queue[front];
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 −
bool isfull()
if(rear == MAXSIZE - 1)return

true;
else
return false;
isempty()
If the value of front is less than MIN or 0, it tells that the queue is not yet initialized,
hence empty.
Algorithm of isempty() function –
bool isempty()
if(front < 0 || front > rear)return

true;
else
S2 BCA Page 17
return false;
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
Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen
situations.
S2 BCA Page 18
Algorithm for enqueue operation
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
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 dataelement.

Step 5 − Return success.
S2 BCA Page 19
Algorithm for dequeue operation
int dequeue()
if(isempty())
return 0;
int data = queue[front];
(Implementation of QUEUE using Array )
QUEUE USING LINKED LIST
The major problem with the queue implemented using array is, It will work for only fixed
number of data. That means, the amount of data must be specified in the beginning itself.
Queue using array is not suitable when wedon't know the size of data which we are going
to use. A queue data structure can be implemented using linked list data structure. The queue
which is implemented using linked list can work for unlimited number of values. That
means, queue using linked list can work for variable size of data (No need to fix the size at
beginning of the implementation). The Queue implemented using linked list can organize as
S2 BCA Page 20
many data values as we want.

In linked list implementation of a queue, the last inserted node is always pointed by 'rear'
and the first node is always pointed by 'front'.
Example
In above example, the last inserted node is 50 and it is pointed by 'rear' and the first inserted
node is 10 and it is pointed by 'front'. The order of elements inserted is 10, 15, 22 and 50.
Operations
To implement queue using linked list, we need to set the following things before
implementing actual operations.
Step 1: Include all the header files which are used in the program. Anddeclare all the user
defined functions.
Step 2: Define a 'Node' structure with two members data and next.
Step 3: Define two Node pointers 'front' and 'rear' and set both to
NULL.
Step 4: Implement the main method by displaying Menu of list of operations and make
suitable function calls in the main method to perform user selected operation.
enQueue(value) - Inserting an element into the Queue
Step 1: Create a newNode with given value and set 'newNode → next'to NULL.
Step 2: Check whether queue is Empty (rear == NULL)
Step 3: If it is Empty then, set front = newNode and rear = newNode.
Step 4: If it is Not Empty then, set rear →next = newNode and rear = newNode.
deQueue() - Deleting an Element from Queue
Step 1: Check whether queue is Empty (front == NULL).
S2 BCA Page 21
Step 2: If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and
terminate from the function
Step 3: If it is Not Empty then, define a Node pointer 'temp' and set it to'front'.
Step 4: Then set 'front = front → next' and delete 'temp' (free(temp)).
display() - Displaying the elements of Queue
Step 1: Check whether queue is Empty (front == NULL).
Step 2: If it is Empty then, display 'Queue is Empty!!!' and terminatethe function.

Step 3: If it is Not Empty then, define a Node pointer 'temp' andinitialize with front.
Step 4: Display 'temp → data --->' and move it to the next node. Repeat the same until
'temp' reaches to 'rear' (temp → next != NULL).
Step 4: Finally! Display 'temp → data ---> NULL'.
(Implementation of QUEUE using Link List in C language)
CIRCULAR QUEUE
In a normal Queue Data Structure, we can insert elements until queue becomes full. But once
if queue becomes full, we cannot insert the next element until all the elements are deleted
from the queue. For example consider the queue below...
Ater inserting all the elements into the queue.
Now consider the following situation after deleting three elements from the queue...
This situation also says that Queue is Full and we can not insert the new element because,
S2 BCA Page 22
'rear' is still at last position. In above situation, even though we have empty positions in the
queue we can not make use of them to insert new element. This is the major problem in
normal queue data structure. To overcome this problem we use circular queue data structure.
What is Circular Queue?
Circular Queue is a linear data structure in which the operations are performed based
on FIFO (First In First Out) principle and the last position is connected back to the first
position to make a circle.
Graphical representation of a circular queue is as follows...
Implementation of Circular Queue
To implement a circular queue data structure using array, we first perform the following
steps before we implement actual operations.
Step 1: Include all the header files which are used in the program and define a constant
'SIZE' with specific value.
Step 2: Declare all user defined functions used in circular queue implementation.
Step 3: Create a one dimensional array with above defined SIZE (intcQueue[SIZE])
Step 4: Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front
= -1, rear = -1)
Step 5: Implement main method by displaying menu of operations list and make suitable
function calls to perform operation selected by the user on circular queue.
enQueue(value) - Inserting value into the Circular Queue
In a circular queue, enQueue() is a function which is used to insert an element into the
circular queue. In a circular queue, the new element is always inserted at rear position. The
S2 BCA Page 23
enQueue() function takes one integer value as parameter and inserts that value into the
circular queue.
Pseudo code for enqueue operation
void enqueue(int item)

{
if(front = = -1 && rear = = -1)
{
front = 0;
rear = 0; CQ[rear]=item
}
else if ( ((rear +1)%MAX) = = front)
printf("Queue Overflow");
else
{
rear = (rear +1)%MAXCQ[rear]=item
}
}
deQueue() - Deleting a value from the Circular Queue
In a circular queue, deQueue() is a function used to delete an element from the circular
queue. In a circular queue, the element is always deleted from front position. The
deQueue() function doesn't take any value asparameter.
Pseudo code for dequeue operation
void dequeue()
{
if(front = = -1 && rear = = -1)
{
printf("Queue Underflow");
}
else if (rear = = front)
S2 BCA Page 24
front = rear = -1
else
{
printf("Dequeueing %d", CQ[front]);front = (front +1)%MAX
}
}
display() - Displays the elements of a Circular Queue
Step 1: Check whether queue is EMPTY. (front == -1)
Step 2: If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then define an integer variable 'i' and set'i = front'.
Step 4: Check whether 'front <= rear', if it is TRUE, then display 'queue[i]' value and
increment 'i' value by one (i++). Repeat the same until 'i <= rear' becomes FALSE.
Step 5: If 'front <= rear' is FALSE, then display 'queue[i]' value and increment 'i' value by
one (i++). Repeat the same until'i <= SIZE - 1' becomes FALSE.
Step 6: Set i to 0.
Step 7: Again display 'cQueue[i]' value and increment i value by one (i++). Repeat the same
until 'i <= rear' becomes FALSE.
DOUBLE ENDED QUEUE (DEQUEUE)
Double Ended Queue is also a Queue data structure in which the insertion and deletion
operations are performed at both the ends (front and rear). That means, we can insert at both
front and rear positions and can delete from both front and rear positions.
Double Ended Queue can be represented in TWO ways, those are as follows...
1. Input Restricted Double Ended Queue
S2 BCA Page 25
2. Output Restricted Double Ended Queue
Input Restricted Double Ended Queue
In input restricted double ended queue, the insertion operation is performed at only one
end and deletion operation is performed at both the ends.
Output Restricted Double Ended Queue
In output restricted double ended queue, the deletion operation is performed at only one
end and insertion operation is performed at both the ends.
Function to perform insertion from the front

void enqueue_front(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("deque is full");
}
else if((f==-1) && (r==-1))
{
f=r=0; deque[f]=x;
}
else if(f==0)
{
f=size-1; deque[f]=x;
}
S2 BCA Page 26
else
{
f=f-1; deque[f]=x;
}}
Function to perform insertion from the rear
void enqueue_rear(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("deque is full");
}
else if((f==-1) && (r==-1))
{
r=0;
deque[r]=x;
}
else if(r==size-1)
{
r=0;
deque[r]=x;
}
else
{
r++;
deque[r]=x;
}
}
Function to perform Deletion from the front

void dequeue_front()
{
if((f==-1) && (r==-1))
S2 BCA Page 27
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[f]);f=-1;
r=-1;
}
else if(f==(size-1))
{
printf("\nThe deleted element is %d", deque[f]);f=0;
}
else
{
printf("\nThe deleted element is %d", deque[f]);f=f+1;
}
}
Function to perform Deletion from the rear

void dequeue_rear()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[r]);f=-1;
r=-1;
}
else if(r==0)
S2 BCA Page 28
{
printf("\nThe deleted element is %d", deque[r]);r=size-1;
}
else
{
printf("\nThe deleted element is %d", deque[r]);r=r-1;
}
}
S2 BCA Page 29
PROGRAMS
1. Implementation of Stack using Array

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 50
int top;
void main()
{
int choice,item,flag;
int stack[size];
initializestack();
clrscr();
while(1)
{
printf("\n\nArray Implementation of Stack");
printf("\n\n1.Push\n2.Pop\n3.Top of Stack\n4.Display\n5.Exit");
printf("\nEnter a choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("\nEnter the item to be pushed:");
scanf("%d",&item);
push(stack,item,&flag);
if(flag==1)
{
printf("\nStack Overflow. It cannot be pushed");
continue;
}
break;
S2 BCA Page 30
case 2:pop(stack,&item,&flag);
if(flag==1)
{
printf("\nStack underflow. It cannot be poped");
continue;
}
else
printf("\npoped Item=%d\n",item);
break;
case 3:stacktop(stack,&item,&flag);
if(flag==-1)
{
printf("\nStack underflow.");
continue;
}
else
printf("\nTop element of Stack=%d\n",item);
break;
case 4:display(stack);
break;
case 5:exit(0);
break;
}
}
getch();
}
initializestack()
{
top=-1;
}
push(int stack[],int item,int *flag)
S2 BCA Page 31
{
if(Isstackfull())
{
*flag=1;
return;
}
*flag=0;
top++;
stack[top]=item;
}
pop(int stack[],int *item,int *flag)
{
if(Isstackempty())
{
*flag=1;
return;
}
*flag=0;
*item=stack[top];
top--;
}
stacktop(int stack[],int *item,int *flag)
{
if(Isstackempty())
{
*flag=1;
return;
}
*flag=0;
*item=stack[top];
}
S2 BCA Page 32
display(int stack[])
{
int i;
if(Isstackempty())
{
printf("\nStack is Empty");
return;
}
printf("\nStack Contents are as .....");
for(i=top;i>=0;i--)
printf("\n%d",stack[i]);
printf("\n");
}
Isstackfull()
{
if(top==size-1)
return 1;
else
return 0;
}
Isstackempty()
{
if(top==-1)
return 1;
else
return 0;
}
2. Implementation of Stack using Linked List
#include<stdio.h>
#include<conio.h>
void push();
S2 BCA Page 33
void pop();
void display();
struct node
{
int info;
struct node *link;
}
*top=NULL;
int item;
void main()
{
int ch;
clrscr();
do
{
printf("\n \n LINKED LIST IMPLEMENTATION OF STACK");
printf("\n \n 1.PUSH \n\n 2.POP \n\n 3.DISPLAY \n\n 4.EXIT");
printf("\n \n Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:exit();
default:printf("\n Invalid Choice\n");
break;
}
S2 BCA Page 34
}
while(ch!=4);
getch();
}
void push()
{
struct node *ptr;
printf("\n \n Enter item:");
scanf("%d",&item);
if(top==NULL)
{
top=(struct node *) malloc(sizeof(struct node));
top->info=item;
top->link=NULL;
}
else
{
ptr=top;
top=(struct node *) malloc(sizeof(struct node));
top->info=item;
top->link=ptr;
}
printf("\nItem inserted:%d \n",item);
}
void pop()
{
struct node *ptr;
if(top==NULL)
printf("\n \n Stack is Empty");
else
{
S2 BCA Page 35
ptr=top;
printf("\n Element Deleted=%d\n",ptr->info);
free(ptr);
top=top->link;
}
}
void display()
{
struct node *ptr;
if(top==NULL)
printf("\n \n Stack is Empty");
else
{
ptr=top;
printf("\nList :\n");
while(ptr!=NULL)
{
printf("%d->",ptr->info);
ptr=ptr->link;
}
printf("NULL");
}
getch();
}
3. Implementation of Queue using Array
(Pending)
4. Implementation of Queue using Linked List
(Pending)
5. Program to evaluate postfix expression
#include<stdio.h>
#include<conio.h>
S2 BCA Page 36
#include<string.h>
#include<stdlib.h>
#define size 50
int top;
void main()
{
char item;
char postfix[size];
int value,n;
clrscr();
top=-1;
printf("\nEnter the postfix expression:");
gets(postfix);
value=evaluate(postfix);
printf("\nValue is %d",value);
getch();
}
void push(int stack[],int item)
{
if(top==size-1)
{
printf("\n Stack Overflow");
exit(0);
}
top++;
stack[top]=item;
}
pop(int stack[])
{
int item;
if(top==-1)
S2 BCA Page 37
{
return (0);
}
item=stack[top];
top--;
return(item);
}
int evaluate(char postfix[])
{
int post=0,length,value,num,t1,t2;
char ch;
int stack[50];
length=strlen(postfix);
while(post<length)
{
if(postfix[post]=='\t')
{
post++;
continue;
}
else if(isdigit(postfix[post]))
{
num=(int)(postfix[post]-'0');
push(stack,num);
}
else
{
t2=pop(stack);
t1=pop(stack);
switch(postfix[post])
{
S2 BCA Page 38
case '+':value=t1+t2;
break;
case '-':value=t1-t2;
break;
case '*':value=t1*t2;
break;
case '/':value=t1/t2;
break;
case '%':value=t1%t2;
break;
default:printf("\n Illegal expression \n");
getch();
exit(0);
}
push(stack,value);
}
post++;
}
value=pop(stack);
return(value);
}
6. Program to convert infix expression to postfix expression

(Pending)
S2 BCA Page 39

DS Module 2

Uploaded by

Copyright:

Available Formats

DS Module 2

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS Module 2

Uploaded by

Copyright:

Available Formats

CP 1243 DATA STRUCTURES IN C Module 2

STACK DATA STRUCTURE

The following diagram depicts a stack and its operations –

 isFull() − check if stack is full.

 IsEmpty() - check if stack is empty.

 Step 2 − If the stack is full, produces an error and exit.

 Step 5 − Returns success.

A simple algorithm for Push operation can be derived as follows −

 Step 1 − Checks if the stack is empty.

 Step 2 − If the stack is empty, produces an error and exit.

 Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

Algorithm of peek() function −

Algorithm of isfull() function −

Algorithm of isempty() function –

STACK USING LINKED LIST

 In linked list implementation of a stack, every new element is inserted as 'top'

Step 3: Define a Node pointer 'top' and set it to NULL.

make suitable function calls in the main method. push(value) - Inserting an

To insert a new node into the stack...

Step 1: Create a newNode with given value.

Step 2: Check whether stack is Empty (top == NULL)

Step 3: If it is Empty, then set newNode → next = NULL.

Step 4: If it is Not Empty, then set newNode → next = top.

Step 5: Finally, set top = newNode.

Step 1: Check whether stack is Empty (top == NULL).

Step 7: Finally, delete 'temp' (free(temp)).

display() - Displaying stack of elements

Step 1: Check whether stack is Empty (top == NULL).

3. Evaluation of postfix expression : Using stack

Expression Representation Techniques :

Infix a+b Operator Between Operands

Prefix +ab Operator before Operands

Postfix ab+ Operator after Operands

 Prefix (Polish) Notation

 Postfix (Reverse-Polish) Notation

These notations are named as how they use operator in expression.

1 a+b +ab ab+

4 a/b+c/d +/ab/cd ab/cd/+

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

As we have discussed, it is not a very efficient way to design an algorithm or program to

As multiplication operation has precedence over addition, b * c will be evaluated first. A

Precedence and associativity determines the order of evaluation of an expression. Following

Sr.No. Operator Precedence Associativity

1 Exponentiation ^ Highest Right to Left

2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left to Right

3 Addition ( + ) & Subtraction ( − ) Lowest Left to Right

can be written in prefix as

unnecessary. As such, the previous expression can be further simplified to

or simply removing them5 − 6 × 7

can be written in Polish notation as

Scan the given prefix expression from right to left

Token Action Stack Notes

1 Operand 1 Push onto stack.

3 Operand 34 Push onto stack.

Pop the two operands (15, 5), calculate (15 ÷ 5 = 3)and

QUEUE DATA STRUCTURE

 enqueue() − add (store) an item to the queue.