STACKS

Stacks
• Subcase of sequential data structures - limited access data structures
• Arrays : Random access
• Lists : Sequential access
• Last In First Our (LIFO) List
• Operations
• Push, Pop and peek
• isempty
• Applications
• Reverse a word
• Solve Maze game
• space for parameters and local variables is created internally using a stack.
• compiler's syntax check for matching braces is implemented by using stack.
• support for recursion
Pre and post conditions

Operation Precondition Postcondition

isEmpty none returns true if the stack is empty, false if not
peek ! isEmpty returns top element
push none element pushed is new top element
pop ! isEmpty returns top element, stack size decreases by 1
Two primary operations
• push() − Pushing (storing) an element on the stack.
• pop() − Removing (accessing) an element from the stack.
Functionality added to use a stack efficiently
• peek() − get the top data element of the stack, without removing it.
• isFull() − check if stack is full.
• isEmpty() − check if stack is empty.
Basic Operation
Suppose that an intermixed sequence of stack push and pop operations
are performed. The pushes push the integers 0 through 9 in order; the
pops print out the return value. Which of the following sequence could
not occur?
a) 1 2 3 4 5 6 9 8 7 0
b) 0 4 6 5 3 8 1 7 2 9
c) 1 4 7 9 8 6 5 3 0 2
d) 2 1 4 3 6 5 8 7 9 0
Suppose an intermixed sequence of stack push and pop operations are
performed. The pushes push into the stack the integers 0 through 9 in
order; popped values are printed in the order they are popped. Which
of the below sequences could occur as the printed output?
a) 1 2 3 0 6 5 4 7 8 9
b) 2 3 4 5 6 7 8 9 0 1
c) 6 7 8 9 5 4 3 2 1 0
d) 7 8 9 6 5 4 2 3 1 0
Write an algorithm to return an exact copy of a stack.
Solution :
Stack stack_copy(stack S)
{
stack tmp = stack_new(); // temporary stack
stack copy = stack_new(); // stack to be returned

// move all elements of S into tmp -- they will be in the reverse order
while (!stack_empty(S))
push(tmp, pop(S));

// move them back to both S and to copy

while (!stack_empty(tmp)) {
string x = pop(tmp);
push(S, x); // restore x onto S
push(copy, x); // put a copy of x onto copy
}

return copy;
}
What does the following code fragment print when n is 50? In general,
what does it do when presented with a positive integer n?

Stack s = new Stack();

while (n > 0) {
s.push(n % 2);
n = n / 2;
}
while (!s.isEmpty())
print(s.pop());
Count the number of elements in a stack
Check whether contents of stack are sorted
Parenthesis Matching
• Balanced Parentheses
(()()()())
(((())))
(()((())()))

• Unbalanced Parentheses
((((((())
()))
(()()(()
Parentheses check : Illustration
(a*(b + c)-(d/(e+(a-c)+d)*(c+e)))

(
( ( ( (
( ( ( ( ( ( ( (
( ( ( ( ( ( ( ( ( ( (

Valid Parentheses
Parentheses check : Illustration
(a*(d/e+(a-c))+d))*(c+e)))

(
( ( (
( ( ( ( (

)
In Valid Parentheses
Parentheses check : Illustration
{a*(b + c)-[d/(e+(a-c)+d]*(c+e)]}

(
( ( (
( [ [ [ [
{ { { { { { {

Invalid Parentheses
• In using a stack to check delimiter matching, three different kinds of
errors can occur. Give example expressions that would create each
kind of error, and indicate the stack status in each case
Algorithm ParenthesesCheck(infix)
1. Create stack s
2. balanced = True
3. index = 0
4. while index < len(infix) and balanced == True
i. symbol = infix[index]
ii. if symbol == "("
push(S, symbol)
else if symbol == ‘)’
if isEmpty(S)
balanced = False
else
pop(S)
iii. index = index + 1
5. if balanced and isEmpty(S)
return True
else
return False
Infix to Postfix notation
• Read in the tokens one at a time
• If a token is an operand, write it into the output
• If a token is an operator,
• push it to the stack, if the stack is empty.
• If the stack is not empty, pop entries with higher or equal priority and then push that token
to the stack.
• If a token is a left parentheses '(',
• push it to the stack
• If a token is a right parentheses ')',
• pop entries until '(‘ and add to output ; ignore ‘)’
• When you finish reading the string, you pop up all tokens which are left there.
[Arithmetic precedence is in increasing order: '+', '-', '*', '/‘]
 Conversion of Infix expression to Postfix
While characters remain in the infix string
1. read the next character in the infix string
2. if the character is an operand,
append the character to the postfix expression
3. if the character is an operator @
while the stack is not empty and an operator of greater or equal priority is on the stack
pop the stack and append the operator to the postfix
push @
4. if the character is a left parenthesis ‘(‘
push the parenthesis onto the stack
5. if the character is a right parenthesis ‘)’
while the top of the stack is not a left parenthesis ‘(‘
pop the stack and append the operator to postfix expression
pop the stack ‘(‘ and discard the returned left parenthesis
Pop any remaining items on the stack and append to postfix.
Infix to Postfix notation - Example
Infix Expression a+(b+c*a+d)/c
Postfix Expression a
ab
abc
abca
abca*+
abca*+d
*
abca*+d+
+ + + abca*+d+c
( ( ( ( ( /
abca*+d+c/+
+ + + + + + + +
Evaluating a Postfix Expression
while characters remain in the postfix string
1. read a character
2. if the character is an operand, push it onto a stack
3. if the character is an operator
i. pop the second operand
ii. pop the first operand
iii. perform the operation
iv. push the result
Pop the final value from the stack