University of Gondar

Faculty of Informatics
Department of Computer Science
CoSc2083 – Data structures and Algorithms
Chapter 4 Handout – Linear Data Structures (PART – II)
4. STACK:

“A stack is an ordered list in which all insertions and deletions are made at one end, called the
top”. Stacks are sometimes referred to as Last In First Out (LIFO) lists.

Stacks have some useful terminology associated with them:

 Push To add an element to the stack

 Pop To remove an element from the stock
 LIFO Refers to the last in, first out behavior of the stack
 FILO Refers to the first in, last out Equivalent to LIFO

Initial Stack Push(8) Pop

TOS=> 8
TOS=> 4 4 TOS=> 4
1 1 1
3 3 3
6 6 6

Implementation:

Stacks can be implemented both as an array (contiguous list) and as a linked list. We want a set
of operations that will work with either type of implementation: i.e. the method of
implementation is hidden and can be changed without affecting the programs that use them.

The Basic Operations:

Push()
{
if there is room {
put an item on the top of the stack
else
give an error message
}
}

Data Structures and Algorithms (CoSc2083) Page 1 of 30

Pop()
{
if stack not empty {
return the value of the top item
remove the top item from the stack
}
else {
give an error message
}
}

CreateStack()
{
remove existing items from the stack
initialise the stack to empty
}

4.1 Array Implementation of Stacks: The PUSH operation

Here, as you might have noticed, addition of an element is known as the PUSH operation. So, if
an array is given to you, which is supposed to act as a STACK, you know that it has to be a
STATIC Stack; meaning, data will overflow if you cross the upper limit of the array. So, keep this
in mind.

Algorithm:

Step-1: Increment the Stack TOP by 1. Check whether it is always less than the Upper Limit of
the stack. If it is less than the Upper Limit go to step-2 else report -"Stack Overflow"
Step-2: Put the new element at the position pointed by the TOP

Implementation:

static int stack[UPPERLIMIT];

int top= -1; /*stack is empty*/
..
..
main()
{
..
..
push(item);
..
..
}

Data Structures and Algorithms (CoSc2083) Page 2 of 30

push(int item)
{
top = top + 1;
if(top < UPPERLIMIT)
stack[top] = item; /*step-1 & 2*/
else
cout<<"Stack Overflow";
}

Note:- In array implementation, we have taken TOP = -1 to signify the empty stack, as this
simplifies the implementation.

4.2 Array Implementation of Stacks: the POP operation

POP is the synonym for delete when it comes to Stack. So, if you're taking an array as the stack,
remember that you'll return an error message, "Stack underflow", if an attempt is made to Pop
an item from an empty Stack. OK.

Algorithm

Step-1: If the Stack is empty then give the alert "Stack underflow" and quit; or else go to step-2
Step-2: a) Hold the value for the element pointed by the TOP in some variable.
b) Decrement the TOP by 1

Implementation:

static int stack[UPPPERLIMIT];

int top=-1;
..
..
main()
{
..
..
poped_val = pop();
..
..
}

int pop()
{
int del_val = 0;
if(top == -1)

Data Structures and Algorithms (CoSc2083) Page 3 of 30

 cout<<"Stack underflow"; /*step-1*/
else
{
del_val = stack[top]; /*step-2*/
top = top -1;
}
return(del_val);
}

Note: - Step-2 :( b) signifies that the respective element has been deleted.

4.3 Linked List Implementation of Stacks: the PUSH operation

It’s very similar to the insertion operation in a dynamic singly linked list. The only difference is
that here you'll add the new element only at the end of the list, which means addition can
happen only from the TOP. Since a dynamic list is used for the stack, the Stack is also dynamic,
means it has no prior upper limit set. So, we don't have to check for the Overflow condition at
all!

In Step [1] we create the new element to be pushed to the Stack.

In Step [2] the TOP most element is made to point to our newly created element.
In Step [3] the TOP is moved and made to point to the last element in the stack, which is our
newly added element.

Algorithm

Step-1: If the Stack is empty go to step-2 or else go to step-3

Step-2: Create the new element and make your "stack" and "top" pointers point to it and quit.
Step-3: Create the new element and make the last (top most) element of the stack to point to it
Step-4: Make that new element your TOP most element by making the "top" pointer point to it.

Implementation:
struct node{
int item;
struct node *next;
}
struct node *stack = NULL; /*stack is initially empty*/
struct node *top = stack;
Data Structures and Algorithms (CoSc2083) Page 4 of 30
main()
{
..
..
push(item);
..
}

push(int item)
{
if(stack == NULL) /*step-1*/
{
newnode = new node /*step-2*/
newnode -> item = item;
newnode -> next = NULL;
stack = newnode;
top = stack;
}
else
{
newnode = new node; /*step-3*/
newnode -> item = item;
newnode -> next = NULL;
top ->next = newnode;
top = newnode; /*step-4*/
}
}

4.4 Linked List Implementation of Stacks: the POP Operation

This is again very similar to the deletion operation in any Linked List, but you can only delete
from the end of the list and only one at a time; and that makes it a stack. Here, we'll have a list
pointer, "target", which will be pointing to the last but one element in the List (stack). Every
time we POP, the TOP most element will be deleted and "target" will be made as the TOP most
element.

Data Structures and Algorithms (CoSc2083) Page 5 of 30

 In step[1] we got the "target" pointing to the last but one
node.
In step[2] we freed the TOP most element.
In step[3] we made the "target" node as our TOP most
element.

Supposing you have only one element left in the Stack, then
we won't make use of "target" rather we'll take help of our
"bottom" pointer. See how...

Algorithm:

Step-1: If the Stack is empty then give an alert message "Stack Underflow" and quit; or else
proceed
Step-2: If there is only one element left go to step-3 or else step-4
Step-3: Free that element and make the "stack", "top" and "bottom" pointers point to NULL
and quit
Step-4: Make "target" point to just one element before the TOP; free the TOP most element;
make "target" as your TOP most element

Implementation:

struct node
{
int nodeval;
struct node *next;
}
struct node *stack = NULL; /*stack is initially empty*/
struct node *top = stack;

main()
{
int newvalue, delval;
..
push(newvalue);
..
delval = pop(); /*POP returns the deleted value from the stack*/
}

int pop( )
{
int pop_val = 0;

Data Structures and Algorithms (CoSc2083) Page 6 of 30

struct node *target = stack;
if(stack == NULL) /*step-1*/
cout<<"Stack Underflow";
else
{
if(top == bottom) /*step-2*/
{
pop_val = top -> nodeval; /*step-3*/
delete top;
stack = NULL;
top = bottom = stack;
}
else /*step-4*/
{
while(target->next != top) target = target ->next;
pop_val = top->nodeval;
delete top;
top = target;
target ->next = NULL;
}
}
return(pop_val);
}

4.5 Applications of Stacks

4.5.1 Evaluation of Algebraic Expressions

e.g. 4 + 5 * 5

Simple calculator: 45

Scientific calculator: 29 (correct)

Question:
Can we develop a method of evaluating arithmetic expressions without having to ‘look
ahead’ or ‘look back’? ie consider the quadratic formula:
x = (-b+(b^2-4*a*c)^0.5)/(2*a)

where ^ is the power operator, or, as you may remember it :

Data Structures and Algorithms (CoSc2083) Page 7 of 30

In it’s current form we cannot solve the formula without considering the ordering of the
parentheses. i.e. we solve the innermost parenthesis first and then work outwards also
considering operator precedence. Although we do this naturally, consider developing an
algorithm to do the same is possible but complex and inefficient.

Re-expressing the Expression

Computers solve arithmetic expressions by restructuring them so the order of each calculation
is embedded in the expression. Once converted, expression can then be solved in one pass.

Types of Expression

The normal (or human) way of expressing mathematical expressions is called infix form, e.g.
4+5*5. However, there are other ways of representing the same expression, either by writing
all operators before their operands or after them,
e.g.: 4 5 5 * +

+4*55

This method is called Polish Notation (because this method was discovered by the Polish
mathematician Jan Lukasiewicz).

When the operators are written before their operands, it is called the prefix form

e.g. + 4 * 5 5

When the operators come after their operands, it is called postfix form (suffix form or reverse
polish notation)

e.g. 4 5 5 * +

The valuable aspect of RPN (Reverse Polish Notation or postfix)

 Parentheses are unnecessary

 Easy for a computer (compiler) to evaluate an arithmetic expression

Postfix (Reverse Polish Notation)

Postfix notation arises from the concept of post-order traversal of an expression tree (see
Weiss p. 93 - this concept will be covered when we look at trees).

For now, consider postfix notation as a way of redistributing operators in an expression so that
their operation is delayed until the correct time.

Data Structures and Algorithms (CoSc2083) Page 8 of 30

Purpose

The reason for using postfix notation is that a fairly simple algorithm exists to evaluate such
expressions based on using a stack.

Postfix Evaluation

Consider the postfix expression:

6523+8*+3+*
Algorithm
initialise stack to empty;
while (not end of postfix expression) {
get next postfix item;
if(item is value)
push it onto the stack;
else if(item is binary operator) {
pop the stack to x;
pop the stack to y;
perform y operator x;
push the results onto the stack;
} else if (item is unary operator) {
pop the stack to x;
perform operator(x);
push the results onto the stack
}
}
The single value on the stack is the desired result.
Binary operators: +, -, *, /, etc.,

Unary operators: unary minus, square root, sin, cos, exp, etc.,

So for 6 5 2 3 + 8 * + 3 + *

The first item is a value (6) so it is pushed onto the stack

the next item is a value (5) so it is pushed onto the stack
the next item is a value (2) so it is pushed onto the stack
the next item is a value (3) so it is pushed onto the stack and the stack becomes

Data Structures and Algorithms (CoSc2083) Page 9 of 30

 TOS=> 3
2
5
6

the remaining items are now: + 8 * + 3 + *

So next a '+' is read (a binary operator), so 3 and 2 are popped from the stack and their sum
'5' is pushed onto the stack:

TOS=> 5
5
6

Next 8 is pushed and the next item is the operator *:

TOS=> 8
5 TOS=> 40
5 5
6 6
(8, 5 popped, 40 pushed)

Next the operator + followed by 3:

TOS=> 3
TOS=> 45 45
6 6
(40, 5 popped, 45 pushed, 3 pushed)

Next is operator +, so 3 and 45 are popped and 45+3=48 is pushed

Data Structures and Algorithms (CoSc2083) Page 10 of 30

 TOS=> 48
6

Next is operator *, so 48 and 6 are popped, and 6*48=288 is pushed

TOS=> 288

Now there are no more items and there is a single value on the stack, representing the final
answer 288.

Note the answer was found with a single traversal of the postfix expression, with the stack
being used as a kind of memory storing values that are waiting for their operands.

4.5.2 Infix to Postfix (RPN) Conversion

Of course postfix notation is of little use unless there is an easy method to convert standard
(infix) expressions to postfix. Again a simple algorithm exists that uses a stack:

Algorithm

initialize stack and postfix output to empty;

while(not end of infix expression) {
get next infix item
if(item is value) append item to pfix o/p
else if(item == ‘(‘) push item onto stack
else if(item == ‘)’) {
pop stack to x
while(x != ‘(‘)
app.x to pfix o/p & pop stack to x
} else {
while(precedence(stack top) >= precedence(item))
pop stack to x & app.x to pfix o/p
push item onto stack

Data Structures and Algorithms (CoSc2083) Page 11 of 30

 }
}
while (stack not empty)
pop stack to x and append x to pfix o/p

Operator Precedence (for this algorithm):

4 : ‘(‘ - only popped if a matching ‘)’ is found

3 : All unary operators

2:/*

1:+-

The algorithm immediately passes values (operands) to the postfix expression, but remembers
(saves) operators on the stack until their right-hand operands are fully translated.

eg., consider the infix expression a+b*c+(d*e+f)*g

Stack Output

ab
TOS=> +

TOS=> * abc
+

abc*+
TOS=> +

TOS=> *
abc*+de
(
+

TOS=> +
abc*+de*f
(
+

Data Structures and Algorithms (CoSc2083) Page 12 of 30

 abc*+de*f+
+
TOS=>

TOS=> * abc*+de*f+g
+

empty abc*+de*f+g*+

4.5.3 Function Calls

When a function is called, arguments (including the return address) have to be passed to the
called function.
If these arguments are stored in a fixed memory area then the function cannot be called
recursively since the 1st return address would be overwritten by the 2nd return address before
the first was used:
10 call function abc(); /* retadrs = 11 */
11 continue;
...
90 function abc;
91 code;
92 if (expression)
93 call function abc(); /* retadrs = 94 */
94 code
95 return /* to retadrs */

A stack allows a new instance of retadrs for each call to the function. Recursive calls on the
function are limited only by the extent of the stack.
10 call function abc(); /* retadrs1 = 11 */
11 continue;
...
90 function abc;
91 code;
92 if (expression)
93 call function abc(); /* retadrs2 = 94 */
94 code
95 return /* to retadrsn */

Data Structures and Algorithms (CoSc2083) Page 13 of 30

 4.6 Queue

 a data structure that has access to its data at the front and rear.
 operates on FIFO (Fast In First Out) basis.
 uses two pointers/indices to keep tack of information/data.
 has two basic operations:
o enqueue - inserting data at the rear of the queue
o dequeue – removing data at the front of the queue

dequeue enqueue

Front Rear
Example:

Operation Content of queue

Enqueue(B) B
Enqueue(C) B, C
Dequeue() C
Enqueue(G) C, G
Enqueue (F) C, G, F
Dequeue() G, F
Enqueue(A) G, F, A
Dequeue() F, A

4.6.1 Simple array implementation of enqueue and dequeue operations

Analysis:
Consider the following structure: int Num[MAX_SIZE];
We need to have two integer variables that tell:
- the index of the front element
- the index of the rear element
We also need an integer variable that tells:
- the total number of data in the queue
int FRONT =-1,REAR =-1;
int QUEUESIZE=0;
 To enqueue data to the queue
o check if there is space in the queue
REAR<MAX_SIZE-1 ?

Data Structures and Algorithms (CoSc2083) Page 14 of 30

 Yes: - Increment REAR
- Store the data in Num[REAR]
- Increment QUEUESIZE
FRONT = = -1?
Yes: - Increment FRONT
No: - Queue Overflow
 To dequeue data from the queue
o check if there is data in the queue
QUEUESIZE > 0 ?
Yes: - Copy the data in Num[FRONT]
- Increment FRONT
- Decrement QUEUESIZE
No: - Queue Underflow

Implementation:
const int MAX_SIZE=100;
int FRONT =-1, REAR =-1;
int QUEUESIZE = 0;

void enqueue(int x)
{
if(Rear<MAX_SIZE-1)
{
REAR++;
Num[REAR]=x;
QUEUESIZE++;
if(FRONT = = -1)
FRONT++;
}
else
cout<<"Queue Overflow";
}
int dequeue()
{
int x;
if(QUEUESIZE>0)
{
x=Num[FRONT];
FRONT++;
QUEUESIZE--;

}
else
cout<<"Queue Underflow";

Data Structures and Algorithms (CoSc2083) Page 15 of 30

 return(x);
}

4.6.2 Circular array implementation of enqueue and dequeue operations

A problem with simple arrays is we run out of space even if the queue never reaches the size of
the array. Thus, simulated circular arrays (in which freed spaces are re-used to store data) can
be used to solve this problem.

Example: Consider a queue with MAX_SIZE = 4

Simple array Circular array

Operation Content of Content of QUEUE Message Content of Content of QUEUE Message
the array the Queue SIZE the array the queue SIZE
Enqueue(B) B B 1 B B 1
Enqueue(C) B C BC 2 B C BC 2
Dequeue() C C 1 C C 1
Enqueue(G) C G CG 2 C G CG 2
Enqueue (F) C G F CGF 3 C G F CGF 3
Dequeue() G F GF 2 G F GF 2
Enqueue(A) G F GF 2 Overflow A G F GFA 3
Enqueue(D) G F GF 2 Overflow A D G F GFAD 4
Enqueue(C) G F GF 2 Overflow A D G F GFAD 4 Overflow
Dequeue() F F 1 A D F FAD 3
Enqueue(H) F F 1 Overflow A D H F FADH 4
Dequeue () Empty 0 A D H ADH 3
Dequeue() Empty 0 Underflow D H DH 2
Dequeue() Empty 0 Underflow H H 1
Dequeue() Empty 0 Underflow Empty 0
Dequeue() Empty 0 Underflow Empty 0 Underflow

The circular array implementation of a queue with MAX_SIZE can be simulated as follows:

12 11
13
10
9

MAX_SIZE - 1 8

0 7

1 6

2 5
3 4
Analysis:
Consider the following structure: int Num[MAX_SIZE];

Data Structures and Algorithms (CoSc2083) Page 16 of 30

 We need to have two integer variables that tell:
- the index of the front element
- the index of the rear element
We also need an integer variable that tells:
- the total number of data in the queue
int FRONT =-1,REAR =-1;
int QUEUESIZE=0;

 To enqueue data to the queue

o check if there is space in the queue
QUEUESIZE<MAX_SIZE ?
Yes: - Increment REAR
REAR = = MAX_SIZE ?
Yes: REAR = 0
- Store the data in Num[REAR]
- Increment QUEUESIZE
FRONT = = -1?
Yes: - Increment FRONT
No: - Queue Overflow

 To dequeue data from the queue

o check if there is data in the queue
QUEUESIZE > 0 ?
Yes: - Copy the data in Num[FRONT]
- Increment FRONT
FRONT = = MAX_SIZE ?
Yes: FRONT = 0
- Decrement QUEUESIZE
No: - Queue Underflow
Implementation:
const int MAX_SIZE=100;
int FRONT =-1, REAR =-1;
int QUEUESIZE = 0;

void enqueue(int x)
{
if(QUEUESIZE<MAX_SIZE)
{
REAR++;
if(REAR = = MAX_SIZE)
REAR=0;
Num[REAR]=x;
QUEUESIZE++;
if(FRONT = = -1)

Data Structures and Algorithms (CoSc2083) Page 17 of 30

 FRONT++;
}
else
cout<<"Queue Overflow";
}
int dequeue()
{
int x;
if(QUEUESIZE>0)
{
x=Num[FRONT];
FRONT++;
if(FRONT = = MAX_SIZE)
FRONT = 0;
QUEUESIZE--;

}
else
cout<<"Queue Underflow";
return(x);
}

4.6.3 Linked list implementation of enqueue and dequeue operations

Enqueue- is inserting a node at the end of a linked list
Dequeue- is deleting the first node in the list

4.6.4 Deque (pronounced as Deck)

- is a Double Ended Queue
- Insertion and deletion can occur at either end
- has the following basic operations
EnqueueFront – inserts data at the front of the list
DequeueFront – deletes data at the front of the list
EnqueueRear – inserts data at the end of the list
DequeueRear – deletes data at the end of the list
- implementation is similar to that of queue
- is best implemented using doubly linked list

Front Rear

DequeueFront EnqueueFront
4.6.5 Priority Queue DequeueRear EnqueueRear
- is a queue where each data has an associated key that is provided at the time of
insertion.

Data Structures and Algorithms (CoSc2083) Page 18 of 30

 - Dequeue operation deletes data having highest priority in the list
- One of the previously used dequeue or enqueue operations has to be modified

Example: Consider the following queue of persons where females have higher priority
than males (gender is the key to give priority).

Abebe Alemu Aster Belay Kedir Meron Yonas

Male Male Female Male Male Female Male

Dequeue()- deletes Aster

Abebe Alemu Belay Kedir Meron Yonas
Male Male Male Male Female Male

Dequeue()- deletes Meron

Abebe Alemu Belay Kedir Yonas
Male Male Male Male Male

Now the queue has data having equal priority and dequeue operation deletes the front
element like in the case of ordinary queues.

Dequeue()- deletes Abebe

Alemu Belay Kedir Yonas
Male Male Male Male

Dequeue()- deletes Alemu

Belay Kedir Yonas

Male Male Male

Thus, in the above example the implementation of the dequeue operation need to be
modified.

4.6.5.1 Demerging Queues

- is the process of creating two or more queues from a single queue.
- used to give priority for some groups of data

Example: The following two queues can be created from the above priority queue.
Aster Meron Abebe Alemu Belay Kedir Yonas
Female Female Male Male Male Male Male

Algorithm:
create empty females and males queue
while (PriorityQueue is not empty)

Data Structures and Algorithms (CoSc2083) Page 19 of 30

 {
Data=DequeuePriorityQueue(); // delete data at the front
if(gender of Data is Female)
EnqueueFemale(Data);
else
EnqueueMale(Data);
}

4.6.5.2 Merging Queues

- is the process of creating a priority queue from two or more queues.
- the ordinary dequeue implementation can be used to delete data in the newly created
priority queue.

Example: The following two queues (females queue has higher priority than the males
queue) can be merged to create a priority queue.
Aster Meron Abebe Alemu Belay Kedir Yonas
Female Female Male Male Male Male Male

Aster Meron Abebe Alemu Belay Kedir Yonas

Female Female Male Male Male Male Male
Algorithm:

create an empty priority queue

while(FemalesQueue is not empty)
EnqueuePriorityQueue(DequeueFemalesQueue());
while(MalesQueue is not empty)
EnqueuePriorityQueue(DequeueMalesQueue());

It is also possible to merge two or more priority queues.

Example: Consider the following priority queues and suppose large numbers represent
high priorities.
ABC CDE DEF FGH HIJ
52 41 35 16 12

BCD EFG GHI IJK JKL

47 32 13 10 7

Thus, the two queues can be merged to give the following priority queue.

ABC BCD CDE DEF EFG FGH GHI HIJ IJK JKL
52 47 41 35 32 16 13 12 10 7
4.7 Application of Queues

Data Structures and Algorithms (CoSc2083) Page 20 of 30

 i. Print server- maintains a queue of print jobs

ii. Disk Driver- maintains a queue of disk input/output requests

iii. Task scheduler in multiprocessing system- maintains priority queues of processes

iv. Telephone calls in a busy environment –maintains a queue of telephone calls

v. Simulation of waiting line- maintains a queue of persons

/*4. Program for STACK using Arrays */

#include<iostream>
using namespace std;
int top = -1;
const int MAXSIZE = 100;
int stack[MAXSIZE];
void push( int a)
{
top = top +1;
if(top<MAXSIZE)
stack[top] = a;
else
cout<<"STACK OVERFLOW\n";
}
void pop()
{
int p;
if(top==-1)
cout<<"STACK UNDERFLOW\n";
else
{p = stack[top];
top=top-1;
cout<< "POPPED ITEM IS:"<<p;
}
}
void display()
{
cout<<"\nSTACK CONTENTS ARE:\n";
if(top == -1)
cout<<"Empty Stack\n";
else
{
for(int i=0;i<=top;i++)
cout<<stack[i]<<"\t";

Data Structures and Algorithms (CoSc2083) Page 21 of 30

 }
}
int main()
{
int c,d;
cout<<"STACK OPERATIONS\n";
do
{
cout<<"\nEnter UR choice:\n";
cout<<"__________________\n";
cout<<"1. PUSH \t 2. POP \n";
cin>>c;
switch(c)
{
case 1:
cout<<"Enter the data to be inserted:\n";
cin>>d;
push(d);
display();
break;
case 2:
pop();
display();
break;
}
}while(c<3);
return(0);
}

// 5. Program for QUEUE using arrays

#include<iostream>
using namespace std;
int front = -1;
int rear = -1;
const int MAXSIZE = 100;
int queue[MAXSIZE];
void enqueue(int x)
{
rear++;
if(rear>=MAXSIZE)
cout<<"QUEUE OVERFLOW\n";
else
queue[rear]=x;
if(front == -1)
front=0;
}

Data Structures and Algorithms (CoSc2083) Page 22 of 30

void dequeue()
{
int y;
if(front==-1 || front > rear)
cout<<"QUEUE UNDERFLOW\n";
else
{
y = queue[front];
front++;
cout<<"Removed item is:\n"<<y;
}
}
void display()
{
cout<<"The contents in the QUEUE are:\n";
for(int j=front; j<=rear; j++)
cout<<queue[j]<<"\t";
}
int main()
{
int c,i;
do
{
cout<<"\nEnter 1 for ENQUEUE \t 2 for DEQUEUE:\n";
cin>>c;
switch(c)
{
case 1:
cout<<"Enter item to be added:\n";
cin>>i;
enqueue(i);
display();
break;
case 2:
dequeue();
display();
break;
}
} while(c<3);
return(0);
}

Data Structures and Algorithms (CoSc2083) Page 23 of 30

// 6. Program for CIRCULAR QUEUE implementation using arrays
#include<iostream>
using namespace std;
int front = -1;
int rear = -1;
const int MAXSIZE = 3;
int queue[MAXSIZE];
int QUEUESIZE = 0;
void enqueue(int x)
{
if(QUEUESIZE < MAXSIZE)
{
rear++;
if(rear == MAXSIZE)
rear = 0;
queue[rear]=x;
QUEUESIZE++;
if(front == -1)
front++;
}
else
cout<<"QUEUE OVERFLOW\n";
}
void dequeue()
{
int y;
if(QUEUESIZE < 0)
cout<<"QUEUE UNDERFLOW\n";
else
{
y = queue[front];
front++;
cout<<"Removed item is:\n"<<y;
if (front == MAXSIZE)
front =0;
QUEUESIZE--;
}
}
void display()
{
cout<<"The contents in the CIRCULAR QUEUE are:\n";
if(front<= rear)
for(int j=front; j<=rear; j++)
cout<<queue[j]<<"\t";
else
{

Data Structures and Algorithms (CoSc2083) Page 24 of 30

for(int k = front; k<=MAXSIZE -1; k++)
cout<<queue[k]<<"\t";
for(int k1=0; k1<= rear ;k1++)
cout<<queue[k1]<<"\t";;
}
}
int main()
{
int c,i;
do
{
cout<<"\nEnter 1 for ENQUEUE \t 2 for DEQUEUE:\n";
cin>>c;
switch(c)
{
case 1:
cout<<"Enter item to be added:\n";
cin>>i;
enqueue(i);
display();
break;
case 2:
dequeue();
display();
break;
}
} while(c<3);
return(0);
}

//7. Program for stack using Linked List (pointers)

#include<iostream>
using namespace std;
struct stack{
int data;
stack *next;
};
stack *top,*stackp=NULL;
void push(int x) {
stack *temp = new stack;
temp->data = x;
if(top == NULL) {
stackp = temp;
top = temp;
temp->next = NULL; }
else

Data Structures and Algorithms (CoSc2083) Page 25 of 30

{
top->next = temp;
top = temp;
temp->next = NULL;
}}
void pop() {
int y;
stack *t1 = stackp;
if(top==NULL)
cout<<"STACK UNDERFLOW";
else if (top == stackp) {
y=top->data;
top=NULL;
stackp=NULL;
cout<<"POPPED ITEM IS:"<<y; }
else {
while(t1->next != top)
t1 = t1->next;
y = top->data;
t1->next=NULL;
top = t1;
cout<<"POPPED ITEM IS:"<<y; } }
void display() {
stack *t2 = stackp;
cout<<"\nTHE CONTENTS IN THE STACK ARE:\n";
while(t2!=NULL)
{ cout<<t2->data<<"\t";
t2= t2->next; } }
int main() {
top = stackp;
int c,d;
cout<<"STACK OPERATIONS\n";
do {
cout<<"\nEnter UR choice:\n";
cout<<"__________________\n";
cout<<"1. PUSH \t 2. POP \n";
cin>>c;
switch(c) {
case 1:
cout<<"Enter the data to be inserted:\n";
cin>>d;
push(d);
display();
break;
case 2:
pop();

Data Structures and Algorithms (CoSc2083) Page 26 of 30

 display();
break; }
}while(c<3);
return(0); }

//8. Program for INFIX to POSTFIX

#include<iostream>
using namespace std;
#include <string.h>
#include <ctype.h>
int const MAX = 10;
int const EMPTY = -1;
struct stack
{
char data[MAX];
int top;
};
int isempty(struct stack *s)
{
return (s->top == EMPTY) ? 1 : 0;
}
void emptystack(struct stack* s)
{
s->top=EMPTY;
}
void push(struct stack* s,int item)
{
if(s->top == (MAX-1))
{
cout<<"\nSTACK FULL";
}
else
{
++s->top;
s->data[s->top]=item;
}
}
char pop(struct stack* s)
{
char ret=(char)EMPTY;
if(!isempty(s))
{
ret= s->data[s->top];
--s->top;
}
return ret;

Data Structures and Algorithms (CoSc2083) Page 27 of 30

 }
void display(struct stack s)
{
while(s.top != EMPTY)
{
cout<<"\n"<<s.data[s.top];
s.top--;
}
}
int isoperator(char e)
{
if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%')
return 1;
else
return 0;
}
int priority(char e)
{
int pri = 0;
if(e == '*' || e == '/' || e =='%')
pri = 2;
else
{
if(e == '+' || e == '-')
pri = 1;
}
return pri;
}
void infix2postfix(char* infix, char * postfix, int insertspace)
{
char *i,*p;
struct stack X;
char n1;
emptystack(&X);
i = &infix[0];
p = &postfix[0];
while(*i)
{
while(*i == ' ' || *i == '\t')
{
i++;
}
if( isdigit(*i) || isalpha(*i) )
{
while( isdigit(*i) || isalpha(*i))
{

Data Structures and Algorithms (CoSc2083) Page 28 of 30

 *p = *i;
p++;
i++;
}
/*SPACE CODE*/
if(insertspace)
{
*p = ' ';
p++;
}
/*END SPACE CODE*/
}
if( *i == '(' )
{
push(&X,*i);
i++;
}
if( *i == ')')
{
n1 = pop(&X);
while( n1 != '(' )
{
*p = n1;
p++;
/*SPACE CODE*/
if(insertspace)
{
*p = ' ';
p++;
}
/*END SPACE CODE*/
n1 = pop(&X);
}
i++;
}
if( isoperator(*i) )
{
if(isempty(&X))
push(&X,*i);
else
{
n1 = pop(&X);
while(priority(n1) >= priority(*i))
{
*p = n1;
p++;

Data Structures and Algorithms (CoSc2083) Page 29 of 30

 /*SPACE CODE*/
if(insertspace)
{
*p = ' ';
p++;
}
/*END SPACE CODE*/
n1 = pop(&X);
}
push(&X,n1);
push(&X,*i);
}
i++;
} }
while(!isempty(&X))
{
n1 = pop(&X);
*p = n1;
p++;
/*SPACE CODE*/
if(insertspace)
{
*p = ' ';
p++;
}
/*END SPACE CODE*/
}
*p = '\0'; }

int main(){
char in[50] = { 0 },post[50] = { 0 };
cout<<"Enter Infix Exp<b></b>ression : ";
cin>>in;
in[strlen(in) - 1] = '\0';
infix2postfix(&in[0],&post[0],1);
cout<<"Postfix Exp<b></b>ression is : \n"<<&post[0];
return 0;
}

Data Structures and Algorithms (CoSc2083) Page 30 of 30