AAST
Stacks & its Applications
Topics
• Stacks
• Overview
• Implementing stack by array
• Implementing stack by linked list
• Main operations
• Examples
• Stack Applications
2
Overview
• It is data structure that stores data in such way where the last
piece of data would be the first one to be retrieved (Last In …
First Out; LIFO).
3
Implementing stack by array
4
Implementing stack by array
5
Implementing stack by array
6
Implementing stack by array
7
Implementing stack by array
• Challenges:
• Fixed size after allocation
• Direct access (not convenient, e.g. accessing item at
position nth)
• Insertion and Delete are difficult (at front/middle), common
limitation in all stack implementation.
8
Implementing stack by linked list
S
Assume we have empty stack S:
S 30 0
Push 30
Push 20 S 20 30 0
Push 10 S 10 20 30 0
Pop S 20 30 0
Pop S 30 0
Pop
S
9
Implementing stack by linked list
• Advantages:
• Implementing stack by linked list allow push & pop
operations to be executed in a constant time (similar to
arrays).
• Not Fixed size.
• Challenges:
• Since it relies on pointers, the access to particular
element is little slow, this is due to indirect access.
10
Main Operations
• Push
• Pop
• isEmpty
11
Main Operations
• It uses similar structure definition as singly linked list.
//Initialize stack to Null
Stack *S = NULL;
//Push …
similar to insert element at the beginning for singly linked list.
//Pop …
similar to delete element from the beginning for singly linked
list.
12
Push
void push (stack *&S, int X)
{
stack * curr = new (stack);
curr->data = X;
curr->next = S;
S = curr;
}
13
Pop
Before calling pop, isEmpty has to be called to check stack
status.
int pop (stack *&S)
{
stack* curr = S;
int x = S->Data;
S = S->next;
free(curr);
return( x );
}
14
isEmpty
int isEmpty (stack *S)
{
return (S == NULL); // return 1 for empty stack
}
Before calling Pop … You have to check stack status:
if(! isEmpty(S))
{ pop(…) }
15
Examples
• Get sum of elements
• Search for certain element
16
Get sum of elements
int Stack_sum (stack *&S)
{
stack * curr = NULL;
int temp, sum = 0;
while( ! isEmpty(S) ) Get summation for nodes in S and store these numbers in curr
{
temp = pop(S);
sum = sum + temp;
push (curr, temp);
}
while( ! isEmpty(curr) ) Retrieve nodes from curr to Stack S
{
temp = pop(curr);
push (S, temp);
}
return(sum);
} 17
Search for certain element
int search (stack *&S, int key) // search for key in Stack S
{
stack* curr = NULL; int found;
int x = pop(S);
while ( (! isEmpty(S)) && (x != key) )
Store elements from S to curr until
{
either element is found or stack S is
push (curr, x);
empty
x = pop(S);
}
if ( isEmpty(S) && (x != key) )
found = 0; // item is not found
else
{
found = 1; // item is found
push (S, x);
}
while( ! isEmpty(curr) ) Retrieve nodes from curr to Stack S
{
x = pop(curr);
push (S, x);
}
return(found);
18
}
Stack Applications
• Reverse codes
• Numbering system conversions
• Bracket checker
• Recursion support
• Infix expression evaluation
• Postfix expression evaluation
• Infix to postfix conversion
• Other uses of stack
Reverse codes
• Reversed word (String)
• ABCDEF ….. will be ….. FEDCBA
F
E
D
C
B
A
Numbering system conversions
• An algorithm converting (26)10 into (11010)2
Bracket checker
• ([]({()}[()])) is balanced; ([]({()}[())]) is not
• Simple counting is not enough to check balance
• You can do it with a stack: going left to right,
• If you see a (, [, or {, push it on the stack
• If you see a ), ], or }, pop the stack and check
whether you got the corresponding (, [, or {
• When you reach the end, check that the stack is
empty
Bracket checker
• c[d] // correct
• a{b[c]d}e // correct
• a{b(c]d}e // not correct; ] doesn't match (
• a[b{c}d]e} // not correct; nothing matches final }
• a{b(c) // not correct; Nothing matches opening {
Recursion support
int factorial(int n)
{
if (n = 1) return 1;
else return n * factorial(n - 1);
}
• If you call x = factorial(3), this enters the factorial
method with n=3 on the stack
•| factorial calls itself, putting n=2 on the stack
•| | factorial calls itself, putting n=1 on the stack
•| | factorial returns 1
• | factorial has n=2, computes and returns 2*1 = 2
• factorial has n=3, computes and returns 3*2 = 6
Other uses for stacks
• Stacks are used for:
• Implementing function or method calls
• Temporary variables—parameters and local variables of a
method—are stored in a stack
• These values are popped off the stack when the method returns
• The value returned from a method is also temporary, and is put on the
stack when the method returns, and removed again by the calling
program
• Keeping track of previous choices (as in
backtracking)
Infix expression evaluation
• Infix form
• operand operator operand
• 2+3
• a+b
• Need precedence rules
• May use parentheses
• 4*(3+5) or
• a*(b+c)
Infix expression evaluation
• To evaluate an expression, such as 1+2*3+4, going left to right;
you need two stacks:
one for operands (numbers), the other for operators:
• If you see a number, push it on the number stack
• If you see an operator, Calculate the previous operator
• While the top of the operator stack holds an operator of equal or higher
precedence:
• pop the old operator
• pop the top two values from the number stack and apply the old operator to them
• push the result on the number stack
• push the new operator on the operator stack
• At the end, perform any remaining operations
Example: 1+2*3+4
• 1 : push 1 on number stack
• + : push + on op stack
• 2 : push 2 on number stack
• * : because * has higher precedence than +, push * onto op stack
• 3 : push 3 onto number stack
• + : because + has lower precedence than *:
• pop 3, 2, and *
• compute 2*3=6, and push 6 onto number stack
• pop 6, 1, and +
• compute 6+1=7 and push 7 onto number stack
• push + onto op stack
• 4 : push 4 onto number stack
• end : pop 4, 7 and +, compute 7+4=11, push 11
• 11 (at the top of the stack) is the answer
Handling parentheses
• When you see a left parenthesis, (, treat it as a low-priority
operator, and just put it on the operator stack
• When you see a right parenthesis , ), perform all the
operations on the operator stack until you reach the
corresponding left parenthesis; then remove the left
parenthesis
Handling variables
• There are two ways to handle variables in an expression:
• When you encounter the variable, look up its value, and put its
value on the operand (number) stack
• This simplifies working with the stack, since everything on it is a
number
• When you encounter a variable, put the variable itself on the
stack; only look up its value later, when you need it
Handling the = operator
• The assignment operator is just another
operator
• It has a lower precedence than the arithmetic
operators
• To evaluate the = operator:
• Evaluate the right-hand side (this will already have
been done)
• Store the value of the right-hand side into the
variable on the left-hand side
• You can only do this if your stack contains
variables as well as numbers
• Push the value onto the stack
Postfix expression evaluation
• Postfix form
• Operator appears after the operands
• (4+3)*5 43+5*
• 4+(3*5) 435*+
• No precedence rules
• Input expression given in postfix form
• How to evaluate it?
Postfix expression evaluation
• Use a stack, assume binary operators +,*
• Input: postfix expression
• Scan the input
• If operand,
• push to stack
• If operator
• pop the stack twice
• apply operator
• push result back to stack
Postfix expression evaluation
• Way of inputting numbers to a calculator
• (5 + 3) * 6 becomes 53+6*
• 5+3*6 becomes 536*+
• We can use a stack to implement this
• consider 5 3 + 6 *
+ 6 *
3 6
5 8 8 48
– try doing 5 3 6 * +
Example: 598+46*7+*+
Example: 598+46*7+*+
• Evaluation
push(5)
push(9)
push(8)
push(pop() + pop()) //17
push(4)
push(6)
push(pop() * pop()) //24
push(7)
push(pop() + pop()) //31
push(pop() * pop()) //527
push(pop() + pop()) //532
print(pop()) //532
Infix to postfix conversion
How to convert expression into postfix form
Infix to postfix conversion
Higher or equal
Infix to postfix conversion
Infix to postfix conversion
Infix to postfix conversion
Infix to postfix conversion
Infix to postfix conversion
Thank You
45