Data Structures and Algorithms Using Java

Debasis Samanta
Department of Computer Science & Engineering, IIT Kharagpur

Module 06: Stack

Lecture 21 : Stack Data Structures
 Introduction to Stack
 Representation of Stacks
 Array representation
 Linked list representation  Applications of Stack
 Operations on Stack  Arithmetic expression evaluation
 push(), pop()  Recursion implementation
 Status: isEmpty(); size(), peep()  Factorial calculation
Introduction to Stack
The concept

CARGO

Goods in a cargo

out
in

Trains in a Railyard Plates on a tray

 Definition of stack

• A stack is an ordered collection of homogeneous data element where

the insertion and deletion operations take place at one end only.

PUSH
POP

IT E M 1 TO P
IT E M 2
IT E M 3
IT E M 4

.
.
. Stack follows LIFO (Last In First Out) property
.
B ottom
Representations of Stack
 Memory representations

Array representation Linked list representation

Index 1D A rray
S T A C K _H E A D
l B ottom
IT E M 1

l+1 IT E M 2
IT E M i .. . ... ....
l+2 .
. .
. . TOP

l+i-1 IT E M i TOP IT E M 2

. .
. .
. .

u IT E M 1
S IZ E = u+l-1
Operations on Stack
Operations on stack

Push To insert an item into the stack

Pop To remove an item from a stack

Status To know the present

state of a stack
o if stack is empty,
o size of the stack,
o the element at top
Stack with Array Representation
 Operation: Push with array
We have assumed that the array index varies from 1 to SIZE and TOP points the location of the
current top-most item in the stack. The following algorithm defines the insertion of an item into a
stack represented using an array A.
1

Input: The new item ITEM to be pushed onto it. 3

Push operation is failed
Output: A stack with a newly pushed ITEM at the TOP position.
Data structure: An array A with TOP as the pointer.
N-1
Steps: N TOP

1. If TOP ≥ SIZE then

2. Print 1 1
“Stack is full” 2 2

3. Else 3 3

4. TOP = i TOP i
i+1 TOP
TOP + 1
5. A[TOP] = N-1 N-1

ITEM N N

6. EndIf Before push() After push()

7. Stop
 Operation: Pop with array
The following algorithm defines the deletion of an item from a stack represented using an array A.
TOP
1
Input: A stack with elements. 2
Output: Removes an ITEM from the top of the stack if it is not empty. 3

Data structure: An array A with TOP as the pointer. i Pop operation is failed
Steps: i+1

1. If TOP < 1 then N-1

2. Print “Stack N

is empty”
3. Else 1 1

4. ITEM = 2 2

A[TOP]
3 3

i-1 i-1 TOP

5. TOP = TOP – i TOP i

1
6. EndIf N-1 N-1

7. Stop N N

Before Pop() After Pop()

 Operation: Status with array
The following algorithm tests the various states of a stack such as whether it is full or empty, how
many items are right now in it, and read the current element at the top without removing it, etc.
Steps:
1. If TOP < 1 then
2. Print “Stack is empty”
3. Else
4. If (TOP ≥ SIZE) then
5. Print “Stack is full”
6. Else
7. Print “The element at
TOP is”, A[TOP]
8. free = (SIZE – TOP)/SIZE
* 100
9. Print “Percentage of free
stack is”, free
10. EndIf
11. EndIf
12. Stop
Stack with Linked List
 Operation: Push with linked list
Input: ITEM is the item to be inserted.
Output: A single linked list with a newly inserted node with data content ITEM.
Data structure: A single linked list structure whose pointer to the header is known from STACK_H and TOP is the pointer to the first
node.

TOP

Header
Steps:
1. new =
Before push()
GetNode(NODE)
/* Insert at front */
2. new®DATA = ITEM Header

3. new®LINK = TOP
4. TOP = new TOP

5. STACK_H®LINK =
TOP
6. Stop
After push()
 Operation: Pop with linked list
Input: A stack with elements.
Output: The removed item is stored in ITEM.
Data structure: A single linked list structure whose pointer to the header is known from STACK_H and TOP is the pointer to the first
node.
TOP
Steps: Header

1. If TOP = NULL
2. Print “Stack is Before Pop()
empty”
3. Exit TOP

4. Else Header

5. ptr =
TOP®LINK
6. ITEM = After Pop()
TOP®DATA
7. TOP

STACK_H®LINK = ptr Header

8. TOP = ptr NULL Failed Pop()

9. EndIf
10. Stop
 Operation: Status with linked list
Input: A stack with elements.
Output: Status information such as its state (empty or full), number of items, item at the TOP.
Steps:
Data structure: A single linked list structure whose pointer to the header is known from STACK_H and TOP is the pointer to the
first node.1. ptr = STACK_H®LINK
2. If (ptr = NULL) then
3. Print “Stack is
empty”
4. Else
5. nodeCount = 0
6. While (ptr ¹ NULL)
do
7.
nodeCount = nodeCount + 1
8. ptr =
ptr®LINK
9. EndWhile
10. Print “Top item:”,
TOP®DATA,
“Size = ”, nodeCount
11. EndIf
12. Stop
Applications of Stack
 Some common applications

• Stack is extensively used in system programming

3. Scope rule implementation

1. Evaluation of arithmetic expression • Static and dynamic scope rule
• Conversion an expression to postfix management
notation • Activation record management
• Evaluation for the value
• Machine code generation 4. Memory management
• Run-time memory management
2. Execution of recursive call of a function • Code generation
• Factorial calculation • Syntax parsing
• Tower of Hanoi
• Quick sort
• Merge sort
 Some common applications

3. Scope rule implementation

1. Evaluation of arithmetic expression • Static and dynamic scope rule
• Conversion an expression to postfix management
notation • Activation record management
• Evaluation for the value
• Machine code generation 4. Memory management
• Run-time memory management
2. Execution of recursive call of a function • Code generation
• Factorial calculation • Syntax parsing
• Tower of Hanoi
• Quick sort
• Merge sort
Arithmetic Expression Evaluation
Application: An arithmetic expression

A+B*C/D–E^F*G

Precedence and associativity of operators

Operators Precedence Associativity

– (unary), +(unary), NOT 6 –

^ (exponentiation) 6 Right to left
* (multiplication), / (division) 5 Left to right
+ (addition), – (subtraction) 4 Left to right
<, <=, +, < >, >= 3 Left to right
AND 2 Left to right
OR, XOR 1 Left to right
Application: An arithmetic expression evaluation
Precedence and associativity of operators

Operators Precedence Associativity

– (unary), +(unary), NOT 6 –
A+B*C/D–E^F*G ^ (exponentiation) 6 Right to left
* (multiplication), / (division) 5 Left to right
+ (addition), – (subtraction) 4 Left to right
<, <=, +, < >, >= 3 Left to right
AND 2 Left to right
OR, XOR 1 Left to right
Application: An arithmetic expression in parenthesized form
Precedence and associativity of operators

Operators Precedence Associativity

– (unary), +(unary), NOT 6 –
A+B*C/D–E^F*G ^ (exponentiation) 6 Right to left
* (multiplication), / (division) 5 Left to right
+ (addition), – (subtraction) 4 Left to right
<, <=, +, < >, >= 3 Left to right
AND 2 Left to right
OR, XOR 1 Left to right
Application: An arithmetic expression in FORCED parenthesized form

((A + B) * ((C/D) – (E ^ (F * G))))

Application: Postfix notation of an arithmetic expression

A+B*C/D–E^F*G
Application: Postfix notation of an arithmetic expression

((A + ((B ^ C) – D)) * (E – (A/C)))

ABC^D – +EAC/– *
Application: Conversion of an infix expression to postfix expression

In-stack and in-coming priorities of symbols

Symbol In-stack priority value In-coming priority value

+– 2 1
*/ 4 3
^ 5 6
operand 8 7
( 0 9
) – 0
Application: Conversion of an infix expression to postfix expression

Procedure to perform expression conversion

Function Description
ReadSymbol( ) From a given infix expression, this will read the next symbol.
ISP(X) Returns the in-stack priority value for a symbol X.
ICP(X) This function returns the in-coming priority value for a symbol X.
Output(X) Append the symbol X into the resultant expression.
 Application: Conversion of an infix expression to postfix expression
Input: E, simple arithmetic expression in infix notation delimited at the end by the right parenthesis ‘)’, incoming and in-
stack priority values for all possible symbols in an arithmetic expression.
Steps:
Output: An arithmetic expression in postfix notation.
1.
Data structure: TOP = 0, PUSH(‘(‘)
Array representation of a stack with TOP// Initialize thetostack
as the pointer the top-most element.
2. While (TOP > 0) do
3. item = E.ReadSymbol( ) // Scan the next symbol in
infix expression
4. x = POP( ) // Get the next item from
the stack
5. Case: item = operand // If the symbol is an operand
6. PUSH(x) // The stack will remain
same
7. Output(item) // Add the symbol into
the output expression
8. Case: item = ‘)’, // Scan reaches to its end
9. While x ¹ ‘(’ do // Till the left match is
not found
10. Output(x)
11. x = POP( )
12. EndWhile
 Application: Conversion of an infix expression to postfix expression
13. Case: ISP(x) ³ ICP(item)
14. While (ISP(x) ³ ICP(item)) do
15. Output(x)
16. x = POP( )
17. EndWhile
Note: This18. is a procedure irrespectivePUSH(x)
of the type of memory representation of the stack to convert an infix
expression to 19.
its postfix form using the basic
PUSHoperations
(item) of the stack, namely PUSH and POP. These operations
can be replaced
20. with their respective versions
Case: ISP(x) and hence implementable to stack with any type of memory
< ICP(item)
representation.21. PUSH(x)
22. PUSH (item)
23. Otherwise:
Print “Invalid expression”
24. EndWhile
25. Stop
 Application: Evaluation of a postfix expression
Input: E, an expression in postfix notation, with values of the operands appearing in the expression.
Output: Value of the expression.
Data structure: Array representation of a stack with TOP as the pointer to the top-most element.
 Application: Evaluation of a postfix expression
Steps:
1. Append a special delimiter ‘#’ at the end of the expression
2. item = E.ReadSymbol( ) // Read the first symbol from E
3. While (item ¹ ‘#’) do
4. If (item = operand) then
5. PUSH(item) // Operand is the first push
into the stack
6. Else
7. op = item // The item is an operator
8. y = POP( ) // The right-most operand of
the current operator
9. x = POP( ) // The left-most operand of
the current operator
10. t = x op y // Perform the operation with
operator ‘op’ and operands x, y
11. PUSH(t) // Push the result into stack
12. EndIf
13. item = E.ReadSymbol( ) // Read the next item from E
14. EndWhile
15. value = POP( ) // Get the value of the expression
16. Return(value)
17. Stop
Recursion Implementation
 Application: Recursive function call
N! = 1× 2 × 3 × … ×(N-2) × (N-1) ×N
Input: An integer number N. = N ×(N-1) ×(N-2) ×… ×3 ×2 ×1
Output: The factoral value of N, that is N!.
Remark: Code using the recursive definition of factorial. 0! = 1

Steps:
1. If (N = 0) then // Termination condition of repetition
2. fact = 1
3. Else
4. fact = N * Factorial_R(N – 1)
5. EndIf
6. Return(fact) // Return the result
7. Stop
 Application: Recursive function call
Steps:
1. If (N = 0) then // Termination condition of repetition
2. fact = 1
3. Else
4. fact = N * Factorial_R(N – 1)
5. EndIf
6. Return(fact) // Return the result
7. Stop

5!
Steps:
1. 5! = 5*4!
2. 4! = 4*3!
3. 3! = 3*2!
4. 2! = 2*1!
5. 1! = 1*0!
6. 0! = 1
7. 1! = 1
8. 2! = 2
9. 3! = 6
10. 4! = 24
11. 5! = 120
For more discussion on stack
applications see the book
Classic Data Structures
Chapter 4
Prentice Hall of India, 2nd Ed.