Application (Backtracking)
Think of a labyrinth or maze
How do you find a way from an entrance to an exit?
Application: Checking for Balanced Braces
An example of balanced braces
abc{defg{ijk}{l{mn}}op}qr
An example of unbalanced braces
abc{def}}{ghij{kl}m
Application: A Search Problem
P is origin city; Z is destination city
A Flight Map
Stacks
EHB208E
Introduction to the Stack
A stack is a data structure that stores and retrieves items in a
last-in-first-out (LIFO) manner.
1st
element
of stack
The first element that is pushed on a stack is
the last one to be removed.
Stack
Push
the operation to place a new item at the top of
the stack
Pop
the operation to remove the item from the top of
the stack
Stack Operations
Create an empty stack push pop
Destroy a stack
Determine whether a stack is
top
empty
Add a new item -- push
Remove the item that was
added most recently -- pop
Retrieve (read its value) the Stack
item that was added most
recently
Applications of Stacks
Computer systems use stacks during a program’s execution to
store function return addresses, local variables, etc.
Some calculators use stacks for performing mathematical
operations.
The simplest application of a stack is to reverse a word. You
push a given word to stack - letter by letter - and then pop
letters from the stack.
Another application is an "undo" mechanism in text editors; this
operation is accomplished by keeping all text changes in a stack.
Application of Stack (Backtracking)
Think of a labyrinth or maze
How do you find a way from an entrance to an exit?
Once you reach a dead end, you must backtrack.
But, backtrack to where? to the previous choice point.
Therefore, at each choice point you store all possible choices in a
stack . Then backtracking simply means popping a next choice from
the stack.
Stack
Computer systems use stacks
during a program’s execution to main() {
store function return addresses, int i = 5;
local variables, etc. bar
foo(i);
m=6
When a function is called, a frame }
containing local variables and
return adress is pushed on the foo(int j) {
stack int k; foo
k = j+1; j=5
When a function returns, its frame bar(k); k=6
is popped from the stack and }
control is passed to the method on
top of the stack. bar(int m) { main
… i=5
}
Run-time Stack
Example: Factorial function
int fact(int n)
{
if (n == 0)
return (1);
else
return (n * fact(n-1));
}
Tracing the call fact (N=3)
When a function returns, its frame is
popped from the stack and control is
passed to the item on top of the stack N=0
if (N==0) true
return (1)
N=1
N=1
if (N==0) false
if (N==0) false
return (1*fact(0))
return (1*fact(0))
N=2
N=2 if (N==0) false
N=2
if (N==0) false return (2*fact(1))
if (N==0) false
return (2*fact(1)) return (2*fact(1)) N=3
if (N==0) false
N=3 return (3*fact(2))
N=3 N=3
if (N==0) false After 3rd call
if (N==0) false if (N==0) false
return (3*fact(2))
return (3*fact(2)) return (3*fact(2))
After original
call After 1st call After 2nd call
Tracing the call fact (3)
When a function returns, its frame is
popped from the stack and control is
passed to the item on top of the stack
N=1
if (N==0) false
return (1* 1)
N=2
if (N==0) false N=2
return (2*fact(1)) if (N==0) false
N=3 return (2* 1)
if (N==0) false
return (3*fact(2)) N=3 N=3
if (N==0) false if (N==0) false
After return return (3*fact(2)) return (3* 2)
from 3rd call
After return
from 2nd call
After return
from 1st call
return 6
Application: Checking for Balanced Braces
A stack can be used to verify whether a program contains balanced
braces
An example of balanced braces
abc{defg{ijk}{l{mn}}op}qr When the algortihm encounters
‘open braces’ push operation is
An example of unbalanced braces
implemented. Otherwise pop
abc{def}}{ghij{kl}m operation is implemented.
Application: A Search Problem
Beginning at the origin city, the algorithm will try every possible
sequence of flights until either it finds a sequence that gets to the
destination city.
P is origin city; Z is destination city
A Flight Map
Calculating Arithmetic Expression
Evaluation of arithmetic expressions
((A/(B*C))+(D*E))-(A*C)
operands: A,B,C,D,E
operators: / , * , + ,- , *
Each operation has a certain precedence. The use of parentheses
affects the result. Using parentheses, different results could be
obtained.
Application: Algebraic Expressions
To evaluate an infix expression
Convert the infix expression to postfix form
Evaluate the postfix expression
Infix Expression Postfix Expression
5+2*3 523*+
5*2+3 52*3+
5*(2+3)-4 523+*4-
While generating code, compilers first convert the given
expression to a representation called “postfix”.
This “postfix” expression is then processed using the stack
structure. In this representation (postfix), the operands are
written before the operators (A B +).
Calculating Postfix Expression
Infix: (3 + 2) * 10
Postfix: 3 2 + 10 *
Scan the postfix expression from left to right :
1) If an operand found, then push it into stack.
2) If an operator found, pop two operands from the
stack.
3) Perform the arithmetic operator, then push the result
into the stack.
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
3 2 + 10 *
Empty stack
5
4
3
2
1
0
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
3 2 + 10 *
Stack
5
Push(3)
4
3
2
1
0 3
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
3 2 + 10 *
Stack
5
Push(2)
4
3
2
1 2
0 3
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
3 2 + 10 *
Stack
5
+ operator found.
4
Pop two operands 3
from stack. 2
1 2
0 3
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
3 2 + 10 *
Stack
5
4
3
2
1 2 poped
0 3 poped
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
Perform the arithmetic
3 2 + 10 * operator, then push the result
into the stack.
Stack
5
Push the result of
4
+ operator into
stack. 3
2
1 2+3 = 5
0 5 Push(5)
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
Perform the arithmetic
3 2 + 10 * operator, then push the result
into the stack.
Stack
5
Push(10)
4
3
2
1 10
0 5
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
Perform the arithmetic
3 2 + 10 * operator, then push the result
into the stack.
Stack
5
* operator found.
4
Pop two operands 3
from stack. 2
1 10
0 5
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
Perform the arithmetic
operator, then push the result
3 2 + 10 * into the stack.
Stack
5
4
3
2
1 10 poped
0 5 poped
If an operand found push it
into stack
If an operator found, pop two
Postfix expression: operands from the stack.
Perform the arithmetic
3 2 + 10 * operator, then push the result
into the stack.
Stack
5
Push the result of 4
* operator into 3
stack.
2
1 10*5= 50
0 50 Push(50)
Postfix expression:
3 2 + 10 *
Stack
End of expression. 5
4
Pop the final result 3
from stack. 2
1
0 50 poped
Static and Dynamic Stacks
Static Stacks
Fixed size
Can be implemented
with an array
Dynamic Stacks
Grow in size as needed
Can be implemented
with a linked list
Array implementation of stacks
To implement a stack, items are inserted and removed at the
same end (called the top).
To use an array to implement as a stack, you need both the
array itself and an integer variable.
The integer tells you either:
Which location is currently the top of the stack, or
How many elements are in the stack
Array implementation of stacks
0 1 2 3 4 5 6 7 8 9
stk: 17 23 97 44
top = 3 or count=4
The bottom of the stack is at location top=0
How can an empty stack be represented?
Empty stack is represented by top = -1 or count = 0
0 1 2 3 4 5 6 7 8 9
stk:
top = -1 or count=0
Pushing
0 1 2 3 4 5 6 7 8 9
stk: 17 23 97 44
top = 3 or count=4
To add (push) an element:
Increment top and store the element in stk[top]
0 1 2 3 4 5 6 7 8 9
stk: 17 23 97 44 21
top = 4 or count=5
Popping
0 1 2 3 4 5 6 7 8 9
stk: 17 23 97 44
top = 3 or count=4
To remove (pop) an element:
Get the element from stk[top] and decrement [top]
0 1 2 3 4 5 6 7 8 9
stk: 17 23 97 44
top = 2 or count = 3
After popping
0 1 2 3 4 5 6 7 8 9
stk: 17 23 97 44
top = 2 or count = 3
When you pop an element, do you leave the “deleted” element
sitting in the array?
The surprising answer is, “it depends”
If you are programming in C or C++, then doing anything
more is just a waste of time
If you are programming in Java, and the array contains
objects, you should set the “deleted” array element to null
Why? To allow it to be garbage collected!
Stack definition
#define SIZE 50
int stk[SIZE];
int top=-1;
void init_stack() { // Empty stack is represented by top = -1
top=-1;
}
Push and Pop operations
void push( int n ) {
if( top==SIZE-1) printf("\nStack is full");
else stk[++top]= n;
}
int pop( ) {
if(top== -1) {
printf("\nStack is empty");
return -1; }
else return stk[top--];
}
Display all elements of stack
void display( ) {
int i;
if(top== -1) printf("\nStack is empty.");
else {
printf("\nElements are : \n");
for(i=top; i>=0; i--)
printf("%5d ", stk[i]);
}
}
Check
int isEmpty( ) {
if ( top== -1 ) return 1;
else return 0;
}
int peek( ) { //for reading the top element’s value
return stk[top]; }
Array implementation of stacks
#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
void display( ) {
int i;
#define SIZE 50
if(top== -1) printf("\nStack is empty.");
else {
int stack[SIZE];
printf("\nElements are : \n");
int top;
for(i=0;i<=top;i++)
printf("%5d ",stack[i]);
void init_stack() {
}
top=-1;
}
}
int isEmpty( ) {
void push( int n ) {
if ( top== -1 ) return 1;
if( top==SIZE-1) printf("\nStack is full");
else return 0;
else stack[++top]= n;
}
}
int pop( ) {
int peek( ){ return stack[top]; }
if(top== -1) {
printf("\nStack is empty");
return -1;
} else return stack[top--];
}
Array implementation of stacks(Cont.)
switch(choice)
{
case 1:printf("\nEnter the element to push : ");
int main() { scanf("%d",&item);
int choice, item; push(item); break;
init_stack(); case 2:item = pop();
printf("\nElement poped : %d",item);
do printf("\nPress a key to continue...");
{ getche(); break;
printf("\n\tMenu\n\[Link].\n\[Link]."); case 3:item = peek();
printf("\nElement at top : %d",item);
printf("\n\[Link].\n\[Link].\n\[Link].\n"); printf("\nPress a key to continue...");
printf("\nYour Choice: "); getche(); break;
scanf("%d",&choice); case 4:display();
printf("\nPress a key to continue...");
getche(); break;
case 5:exit(0);
}
} while(1);
} // end of main
Sharing space
Of course, the bottom of the stack could be at the other end
0 1 2 3 4 5 6 7 8 9
stk: 44 97 23 17
top = 6 or count = 4
Sometimes this is done to allow two stacks to share the same
storage area
0 1 2 3 4 5 6 7 8 9
stks: 49 57 3 44 97 23 17
topStk1 = 2 topStk2 = 6
Dynamic Stacks
Grow in size as needed
Can be implemented with a linked list
Bottom of stack
Top of stack
What are Big O notations of Push and POP
operations?
Bottom of stack
Top of stack
Empty stack
head
Push(50)
head
50
Push(30)
head
Bottom of stack
30 50
Push(70)
head
Bottom of stack
70 30 50
Pop()
head 70 poped
Bottom of stack
30 50
Pop()
head 30 poped
50
Pop()
head 50 poped
Stack definition
struct s_node {
int data;
struct s_node *link;
} *stack=NULL;
stack
Push operation
//Pushing element in to stack
void push(int j) {
struct s_node *m;
m=new s_node ;
m->data= j ; m->link=stack;
stack=m; return;
} Top of stack Bottom of stack
Stack
a b c
stack = m; m->link = stack;
m=new s_node ;
Pop operations
//Popping element from stack
int pop( ) {
struct s_node *temp=NULL;
if(stack==NULL) {
printf("\nSTACK is Empty."); }
else {
int i=stack->data;
temp = stack ;
stack=stack->link;
delete temp;
return (i); }
}
Top of stack
Display all elements of stack
//Displaying Stack
void display() {
struct s_node *temp=stack;
while(temp!=NULL) {
printf("%d\t", temp->data);
temp=temp->link;
}
}
Linked List implementation of stacks
#include<stdio.h> //Calling in main()
#include<conio.h> int main() {
#include <stdlib.h>
int choice,num,i;
struct s_node { while(1) {
int data;
s_node *link; printf("\n\t MENU\n1. Push\n2. Pop\n");
} *stack=NULL; printf("\n3. Elements in Stack\n4. Exit\n");
printf("\n\tEnter your choice: ");
//Pushing element in to stack
void push(int j) { scanf("%d",&choice);
s_node *m; switch(choice) {
m=new s_node ;
m->data= j ; m->link=stack; case 1: printf("\nElement to be pushed:");
stack=m; return; scanf("%d",&num);
}
push(num); break;
//Popping element from stack case 2: num=pop();
int pop( ) {
s_node *temp=NULL;
printf("\nElement popped: %d ",num);
if(stack==NULL) { getch(); break;
printf("\nSTACK is Empty."); }
case 3: printf("\nElements present in stack : " );
else {
int i=stack->data; display();getch(); break;
temp = stack ; stack=stack->link; case 4: exit(1);
delete temp; return (i);
} default: printf("\nInvalid Choice\n"); break;
} }
//Displaying Stack
void display() { }
s_node *temp=stack; }
while(temp!=NULL) {
printf("%d\t",temp->data);
temp=temp->link;
}
}
Following is C like pseudo code of a function that takes a
number as an argument, and uses a stack S to do processing.
void fun(int n)
{
Stack S; // Say it creates an empty stack S
while (n > 0)
{
// This line pushes the value of n%2 to stack S
push(&S, n%2);
n = n/2;
}
// Run while Stack S is not empty
while (!isEmpty(&S))
printf("%d ", pop(&S)); // pop an element from S and print it
}
(A) Prints binary representation of n in reverse order
(B) Prints binary representation of n
(C) Prints the value of Logn
(D)Prints the value of Logn in reverse order
Consider the following pseudocode that uses a stack
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}
What is output for input "geeksquiz"?
(A) geeksquizgeeksquiz
(B) ziuqskeeg
(C) geeksquiz
(D) ziuqskeegziuqskeeg
A single array A[1..MAXSIZE] is used to implement two
stacks. The two stacks grow from opposite ends of the array.
Variables top1 and top2 (top1<top 2) point to the location of
the topmost element in each of the stacks. If the space is to
be used efficiently, the condition for “stack full” is
(A) (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
(B) top1 + top2 = MAXSIZE
(C) (top1= MAXSIZE/2) or (top2 = MAXSIZE)
(D) top1= top2 -1
Explanation:
If we are to use space efficiently then size of the any stack can be
more than MAXSIZE/2. Both stacks will grow from both ends and if
any of the stack top reaches near to the other top then stacks are
full. So the condition will be top1 = top2 -1 (given that top1 < top2)
To evaluate an mathematical expression without any embedded
function calls:
(A) One stack is enough
(B) Two stacks are needed
(C) As many stacks as the height of the expression tree are needed
(D) A Turing machine is needed in the general case
Explanation:
Any expression can be converted into Postfix or Prefix form.
Prefix and postfix evaluation can be done using a single stack.
For example : Expression '10 2 8 * + 3 -' is given. PUSH 10 in the
stack. PUSH 2 in the stack. PUSH 8 in the stack. When operator
'*' occurs, POP 2 and 8 from the stack. PUSH 2 * 8 = 16 in the
stack. When operator '+' occurs, POP 16 and 10 from the stack.
PUSH 10 * 16 = 26 in the stack. PUSH 3 in the stack. When
operator '-' occurs, POP 26 and 3 from the stack. PUSH 26 - 3 =
23 in the stack. So, 23 is the answer obtained using single stack.
The result evaluating the postfix expression
10 5 + 60 6 / * 8 – is
(A) 284
(B) 213
(C) 142
(D) 71
Explanation:
10 5 + 60 6 / * 8 –
15 60 6 / * 8 –
15 10 * 8 –
150 8 –
142
Consider the following C program:
#define EOF -1
void push (int); /* push the argument on the stack */
int pop (void); /* pop the top of the stack */
void flagError ();
int main ()
{ int c, m, n, r;
while ((c = getchar ()) != EOF) {
if (isdigit (c) ) push (c);
else if ((c == '+') || (c == '*’)) {
m = pop ();
n = pop ();
r = (c == '+') ? n + m : n*m;
push (r); }
else if (c != ' ') What is the output of the program for
flagError (); the following input:
} 5 2 * 3 3 2 + * +
printf("% c", pop ()); }
(A) 15
(B) 25
(C) 30
(D)150
What is the output of the program for the following input:
5 2 * 3 3 2 + * +
(A) 15 Explanation:
(B) 25 The function of the program is:
(C) 30 1) If the current character is a digit it pushes into stack
(D)150 2) Else if the current character is operator, it pops two
elements and then performs the operation. Finally it pushes
the resultant element into stack. Initially stack s is empty.
5 2 * 3 3 2 + * +
1) 5 -> It pushes into s
2) 2 -> It pushes into s
3) * -> It pops two elements n = 2, m=5 n*m = 10 It pushes 10
into s
4) 3 -> It pushes into s
5) 3 -> It pushes into s
6) 2 -> It pushes into s
7) + -> n=2, m=3 n+m=5 It pushes 5 into s
8) * -> n=5, m=3 n*m=15 It pushes 15 into s
9) + -> n=15, m=10 n+m = 25 It pushes 25 into s. Finally the
result value is the only element present in stack.
The best data structure to check whether an arithmetic
expression has balanced parenthesis is a
(A) Queue
(B) Stack
(C) Tree
(D) List
Consider the following operations performed on a stack of size 5 :
Push (a); Pop() ; Push(b); Push(c); Pop(); Push(d); Pop();Pop(); Push
(e) Which of the following statements is correct?
(A) Underflow occurs
(B) Stack operations are performed smoothly
(C) Overflow occurs
(D) None of the above
Convert the following infix expression into its equivalent post
fix expression (A + B^ D) / (E – F) + G
(A) ABD^ + EF – / G+
(B) ABD + ^EF – / G+
(C) ABD + ^EF / – G+
(D) ABD^ + EF / – G+
Explanation:
(A + B^ D) / (E – F) + G
(A + BD ^) / (E – F) + G
(A B D ^+) / (E F -) + G
A B D ^+ E F - / + G
A B D ^+ E F - / G +
The number of recursive calls is limited to the _____ of the
stack.
a. Time
b. Ability
c. Quality
d. Size
View Answer
Answer: d
The data structure used to implement recursive function calls
_____________
a) Array
b) Linked list
c) Binary tree
d) Stack
Answer: d
Explanation: The compiler uses the data type stack for implementing
normal as well as recursive function calls.