CHAPTER FIVE:

STACKS AND QUEUES

December 20, 2010

 STACKS

December 20, 2010

What is Stack?
 Stack is a simple data structure or a list with the restriction
 in which insertion and deletion occur at the same end.
 It is a LIFO (Last In First Out) structure.
 A Stack is an ordered collection of data items,
 into which new items may be inserted and from which items may be
deleted at only one end; and that end is called Top of the Stack.

 The other end is called bottom

 Operations of Stack
 The operations of insertion and deletion are called
 Push - push (put) item onto stack
 Pop - pop (get) item from stack

empty stack push an element push another pop

push
push
empty
pop
ananother top
element
stack B
top
top B
A
top top top
A A A
top
Implementation of Stacks
 Any list implementation could be used to implement a stack
 Arrays (contiguous list)(static: the size of stack is given initially)
 Linked lists (dynamic: never become full) – Next Chapter
 Let’s see how to use an array to implement a stack first
 Unlike an array,
 stack provides the insertion and deletion of items.
 So a stack is a dynamic, constantly changing object.
 Although an array cannot be a stack it can be the home of the
stack
 The stack will grow and shrink within the space reserved for it.
 One end of the array will be fixed as bottom of the stack,
 while the top of the stack will constantly shift as items are popped and
pushed.
Array Implementation of Stacks:
 The basic operations:
 The PUSH Operation
 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
 The POP Operation
 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
             b) Put a NULL value instead
            c) Decrement the TOP by 1
Array Implementation …
Push()
{
if there is no room
give an error message
else
put an item on the top of the stack
}

Pop()
{
if stack empty
give an error message
else {
return the value of the top item
remove the top item from the stack
}
}
Example of Push & Pop operations
 A stack is some time called as LIFO (Last In First Out) list

top
4 50
top
3 40
Push
Push20
40 top
Empty
Pushstack
Again
Pop10
Pop 2 30
Push
Push30
50 Top= -1
1 20
top
10
0
A Stack in “C++” declared as a class.

class stack
{
private: int
st[MAXSIZE];
int top; class definition
public: void init();
void push();
void pop();
void list();
};
stack s ; Object declaration
A Stack in “C++” …
Constructor to initialize the stack:
void stack::init()
{
top=0;
}
Member function definition for PUSH operation
void stack::push()
{
if(top==MAXSIZE)
{
cout <<"\t\t\t Stack is Overflow.\n";
return;
}
cout <<"Enter Element :";
cin >>ele;
st[top]=ele;
top++;
count++;
}
A Stack in “C++” …
Member Function definition to pop an element from a stack.
 
void stack::pop()
{
if(top==0)
{
cout <<"\t\t\t Stack is Underflow.\n";
return;
}
top--;
count--;
cout <<"The Deleted Element is :"<<st[top]<<endl;
}
A Stack in “C++” …
Member Function definition to display the elements of stack.
void stack::list()
{
if(top==0)
{
cout <<"\t\t\t Stack is Empty.\n";
return;
}
else
{
cout <<"The Elements Are :";
for(i=0;i<count;i++)
{
cout <<st[i]<<"->";
}
cout <<"TOP\n";
}
}
 Applications of stacks
 Although the stack data structure is one of the simplest,
it is essential in certain important applications:
 To reverse a sequence
 Matching braces and parentheses
 Stacks are used to hold the return addresses of the function
calls
 In recursive programs
 Expression evaluation
 In converting the in-fix expression into postfix form.
 In graph traversals. Etc,.
Matching braces and
parentheses
 To check that every right brace, bracket, and
parentheses must correspond to its left counterpart
 e.g. [( )] is legal, but [( ] ) is illegal
 Algorithm
(1)   Make an empty stack.
(2)   Read characters until end of file
i.    If the character is an opening symbol, push it onto the stack
ii.   If it is a closing symbol, then if the stack is empty, report an
error
iii.  Otherwise, pop the stack. If the symbol popped is not the
corresponding opening symbol, then report an error
(3)   At end of file, if the stack is not empty, report an error
Matching braces & …
0. Create an empty stack S.
1. While( there are characters left ){
2. Read a character ch.
3. If is ch an opening paren (of any kind), push it onto S
4. Else
5. If ch is a closing paren (of any kind), look at the top of S.
6. If S is empty as this point, report failure.
7. If the top of S is the opening paren that corresponds to c,
then pop S and continue to 1, this paren matches OK.
8. Else report failure.
9. If at the end of input the stack S is not empty, return failure.
Else return success.
Matching braces & …
Matching braces & …
 Familiar Stacks: Web Browser
 Web Browsers use stacks. Where?
 To validate HTML tags to make sure that they match.
 `<b>bold text</b> plain text <i>italics</i>
 <b>bold <i>italics with messed up</b> tags</i>

 Stack of pages visited

 Used by Back and Forward
Return addresses of the function calls

 When a function is called, arguments (including the return

address) have to be passed to the called function.
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 */
Evaluation of Algebraic Expressions

 e.g. 4 + 5 * 5 (type as it is in both calculator)

 simple calculator ?
 scientific calculator ?
 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)

Re-expressing the Expression

Expression…
 Infix form
 The normal (or human) way of expressing mathematical expressions
 e.g. 4+5*5
 Prefix form
 the operators are written before their operands
 e.g. + 4 * 5 5
 This method is called Polish Notation (because this method was
discovered by the Polish mathematician Jan Lukasiewicz).
 Postfix form
 the operators come after their operands
 e.g. 4 5 5 * +
 This method called suffix form or reverse polish notation
 Expression …

 Infix, Postfix and Prefix notations are used in many calculators.

 The valuable aspect of RPN (Reverse Polish Notation or postfix )
 Parentheses are unnecessary 
 Easy for a computer (compiler) to evaluate an arithmetic expression
Postfix (RPN)
 The easiest way to implement the Postfix expression is to use
stack.
 Infix and prefix notations can be converted to postfix notation
using stack.
 postfix calculations
 Scan the postfix expression left to right
 If the character x is a digit
 Push it into the stack
 if the character is an operator (+,-,*,/)
 pop two values from the stack
 Perform the operation
 Push the result of the operation into the stack

 When all characters in postfix expression are

processed
 pop the value from the stack and output it.
 Postfix Evaluation

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.,
postfix calculation
Stack
Postfix Expression
6523+8*+3+*

=
postfix calculation
Stack
Postfix Expression
523+8*+3+*

=

6
postfix calculation
Stack
Postfix Expression
23+8*+3+*

5
6
postfix calculation
Stack
Postfix Expression
3+8*+3+*

2 =
5
6
postfix calculation
Stack
Postfix Expression
+8*+3+*

3
2 =
5
6
postfix calculation
Stack
Postfix Expression

8*+3+*

3
2 +=
5
6
postfix calculation
Stack
Postfix Expression
8*+3+*

2 +3=
-5
(6
postfix calculation
Stack
Postfix Expression
8*+3+*

2+3=

-5
(6
postfix calculation
Stack
Postfix Expression
8d *– +( e3 ++ f*)

a2 b+ +3 c= -5

-5
*(6
postfix calculation
Stack
Postfix Expression
8– *( e+ +3 f+)*

a b+c=- d
5
-5
*(6
postfix calculation
Stack
Postfix Expression
*(– e+( +e3 +
f+)f*)

8
a b+c=-–dd *
5
-5
-*(6
postfix calculation
Stack
Postfix Expression
+e(– e+
3( +e+
f+)f*)f )

8
a b* + c=-–dd *
5
(-5
-*(6
postfix calculation
Stack
Postfix Expression
+(– e3f( +
)e++
f*)f )

a b* +8 c= -–dd * e
5
(-5
-*(6
postfix calculation
Stack
Postfix Expression
f+(–)e3( +e++
f*)f )

+ a5 b* +
8=c -–dd * e

(-5
-*(6
postfix calculation
Stack
Postfix Expression
+
)(– e3( +e++
f*)f )

+ a5 b* +
8=c -–40
dd * e f

(-5
-*(6
postfix calculation
Stack
Postfix Expression
+(– e3( +e++
f*)f )

a b+c=-–dd * e f +
40
-5
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

a b+ +c=-–dd * e f + -
40
-5
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

a b+ +40c =
-– dd * e f +

-5
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

a5 b+ +40c =-– d
d*ef+

-
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

a5 b+ +40c =-– d45

d*ef+

-
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

ab+c =-– dd * e f +

-45
18
-*(6
postfix calculation
Stack
Postfix Expression
3+(– e+*( +e* +
f )f )

ab+c =-– dd * e f +

3
-45
18
-*(6
postfix calculation
Stack
Postfix Expression
3*(– e+( +e* +
f )f )

ab++c=-– 
dd * e f +
3
-45
18
-*(6
postfix calculation
Stack
Postfix Expression
3*(– e+( +e* +
f )f )

ab++3c=-–dd * e f +

-45
18
-*(6
postfix calculation
Stack
Postfix Expression
3*(– e+( +e* +
f )f )

a45b + 3c -–=dd * e f +

-18
-*(6
postfix calculation
Stack
Postfix Expression
3*(– e+( +e* +
f )f )

a45b + 3c -–=dd48* e f +

-18
-*(6
postfix calculation
Stack
Postfix Expression
3*(– e+( +e* +
f )f )

ab+ c -–=dd * e f +

-18
48
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

ab*+ c =
-– dd * e f +

-18
48
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

ab*+ 48
c -–=dd* e f +

-18
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

c -–=dd* e f +
a6b*+48

-18
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

a6b*+48
c -–=dd288
*ef+

-18
-*(6
postfix calculation
Stack
Postfix Expression
3(– e+( +e* +
f )f )

ab+c =-– dd * e f +

-18
*-(6
288
 Infix to postfix conversion
 Scan the Infix expression left to right
 If the character x is an operand
 Output the character into the Postfix Expression
 If the character x is a left or right parenthesis
 If the character is “(“
 Push it into the stack
 if the character is “)”
 Repeatedly pop and output all the operators/characters until “(“ is popped from
the stack.
 If the character x is a is a regular operator
 Step 1: Check the character y currently at the top of the stack.
 Step 2: If Stack is empty or y=‘(‘ or y is an operator of lower precedence than x, then
push x into stack.
 Step 3: If y is an operator of higher or equal precedence than x, then pop and output y
and push x into the stack.
 When all characters in infix expression are processed
 repeatedly pop the character(s) from the stack and output them until the stack
is empty.
Infix to Postfix (RPN) Conversion
initialise 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
}
}
while(stack not empty)
pop stack to x and append x to pfix o/p  
Infix to Postfix (RPN) Conversion
 Operator Precedence (for this algorithm):
4 : ‘(‘ - only popped if a matching ‘)’ is found
3 : All unary operators
2:/*
1:+-
Infix to postfix conversion
Stack

Infix Expression
(a+b-c)*d–(e+f)

Postfix Expression
Infix to postfix conversion
Stack

Infix Expression
a+b-c)*d–(e+f)

Postfix Expression

(
Infix to postfix conversion
Stack

Infix Expression
+b-c)*d–(e+f)

Postfix Expression
a

(
Infix to postfix conversion
Stack

Infix Expression
b-c)*d–(e+f)

Postfix Expression
a

+
(
Infix to postfix conversion
Stack

Infix Expression
-c)*d–(e+f)

Postfix Expression
ab

+
(
Infix to postfix conversion
Stack

Infix Expression
c)*d–(e+f)

Postfix Expression
ab+

-
(
Infix to postfix conversion
Stack

Infix Expression
)*d–(e+f)

Postfix Expression
ab+c

-
(
Infix to postfix conversion
Stack

Infix Expression
*d–(e+f)

Postfix Expression
ab+c-
Infix to postfix conversion
Stack

Infix Expression
d–(e+f)

Postfix Expression
ab+c-

*
Infix to postfix conversion
Stack

Infix Expression
–(e+f)

Postfix Expression
ab+c-d

*
Infix to postfix conversion
Stack

Infix Expression
(e+f)

Postfix Expression
ab+c–d*

-
Infix to postfix conversion
Stack

Infix Expression
e+f)

Postfix Expression
ab+c–d*

(
-
Infix to postfix conversion
Stack

Infix Expression
+f)

Postfix Expression
ab+c–d*e

(
-
Infix to postfix conversion
Stack

Infix Expression
f)

Postfix Expression

+ ab+c–d*e

(
-
Infix to postfix conversion
Stack

Infix Expression
)

Postfix Expression

+ ab+c–d*ef

(
-
Infix to postfix conversion
Stack

Infix Expression

Postfix Expression
ab+c–d*ef+

-
Infix to postfix conversion
Stack

Infix Expression

Postfix Expression
ab+c–d*ef+-
 Thank you!!!

See You Friday @ Sometime as Today