Data Structures and Algorithms 4/27/2026

Push
Procedure 7.1 : PUSH(STACK, TOP, LEN, ITEM)
Data Structures and Algorithms This procedure pushes an ITEM onto a stack.

1 If TOP = LEN, then:

Print: Stack is Full, and Return. [Stack already filled ?]
Stacks 2 Set TOP := TOP+1. [Increases TOP by 1.]
3 Set STACK[TOP] := ITEM. [Insert ITEM in new TOP position.]
4 Return.

Stacks 4

1 4

Stacks POP

⚫ Definition Procedure 7.2 : POP(STACK, TOP, ITEM)

This procedure deletes the top element of STACK
⚫ A stack is a container of objects that are
and assignees it to the variable ITEM.
inserted and removed according to the last-
in-first-out principle.
1 [ If Stack has no item to removed?]
⚫ A stack allows access to only one data item:
If TOP = 0, than:
the last item inserted. If you remove this Print: Stack is Empty, and Return.
item, then you can access the next-to-last 2 Set ITEM:= STACK[TOP]. [Assigns TOP element to ITEM.]
item inserted, and so on. This is a useful 3 Set TOP := TOP-1. [Decreases TOP by 1.]
capability in many programming situations. 4 Return.

Stacks 2 Stacks 5

2 5

Operations on Stack Peek

⚫ Placing a data item on the top of the ⚫ Push and pop are the two primary stack operations. However, it's
stack is called pushing it. sometimes useful to be able to read the value from the top of the
stack without removing it.
⚫ Removing it from the top of the ⚫ Notice that you can only peek at the top item. By design, all the
stack is called popping it. These are other items are invisible to the stack user.
the primary stack operations.
⚫ A stack is said to be a Last-In- Procedure 7.3 : PEEK(STACK, TOP, ITEM)
First-Out (LIFO) storage This procedure returns the top element of STACK wit out
mechanism, because the last item removing and assignees it to the variable ITEM.
inserted is the first one to be
removed. 1 [ If Stack is Empty?]
⚫ Examples If TOP = 0, than:
⚫ “back” in a web browser Print: Stack is Empty, and Return.
⚫ “undo” in Text editors 2 Set ITEM:= STACK[TOP]. [Assigns TOP element to ITEM.]
3 Return.

Stacks 3 Stacks 6

3 6

Balochistan University of Information

Technology & Management Sciences,
Quetta. 1
Data Structures and Algorithms 4/27/2026

Efficiency of Stacks Java Code for Reversing a Word (1)

class Reverse

⚫ Items can be both pushed and popped {

private String input;
from the stack in constant O(1) time.
public Reverse(String input)
⚫ That is, the time is not dependent on {
[Link] = new String(input);
how many items are in the stack, and is }

therefore very quick. No comparisons or public String doReverse()

moves are necessary. {
Stack stk = new Stack([Link]());
for(int i = 0; i<[Link](); i++)
{
[Link]([Link](i));
}

Stacks 7 Stacks 10

7 10

Reversing a Word Java Code for Reversing a Word (2)

String output= new String("");
⚫ For our first example of using a stack, we'll int k=0;
while(![Link]())
examine a very simple task: reversing a word. {
output+= [Link]();
When you run the program, it asks you to type k++;
in a word. When you press Enter, it displays }
return output;
the word with the letters in reverse order. }
}
⚫ A stack is used to reverse the letters. First the //===============================
characters are extracted one by one from the class TestReverse
{
input string and pushed onto the stack. Then public static void main(String args[])
they're popped off the stack and displayed. {
String input = new String("abcdefg");
Because of its last-in-first-out characteristic, Reverse revString = new Reverse(input);
String output= new String([Link]());
the stack reverses the order of the characters. [Link](output);
}
}
Stacks 8 Stacks 11

8 11

Algorithm for Reversing a Word Parsing Arithmetic Expressions

Procedure 7.3: REVERSWORD(INPUT, N, STACK, OUTPUT)
The Algorithm reverse a string INPUT of Length N ⚫ Another very important application of
word in
using a stack STACK and save the reverse
string OUTPUT.
stack is parsing (that is, analyzing)
arithmetic expressions like
Step 1 : Repeat for J=1 to N : 2+3
(a) push char INPUT[J] to STACK.
Step 2: Set K:=1; or
Step 3 : Repeat Step 4 and 5 while STACK is not empty: 2*(3+4)
Step 4 : pop from STACK and store at OUPUT[K].
Step 5: K := K+1. or
Step 5 : Return. ((2+4)*7)+3*(9–5)

Stacks 9 Stacks 12

9 12

Balochistan University of Information

Technology & Management Sciences,
Quetta. 2
Data Structures and Algorithms 4/27/2026

Parsing Arithmetic Expressions Reverse Polish Notation (Postfix Notation)

⚫ As it turns out, it's difficult, at least for a computer algorithm, to

evaluate an arithmetic expression directly. It's easier for the ⚫ In postfix notation (which is also called
algorithm to use a two-step process:
1. Transform the arithmetic expression into a different format, called Reverse Polish Notation, or RPN, the
postfix notation.
2. Evaluate the postfix expression. operator follows the two operands.
⚫ Step 1 is a bit involved, but step 2 is easy. In any case, this two- ⚫ For Example
step approach results in a simpler algorithm than trying to parse

⚫
the arithmetic expression directly.
Of course, for a human it's easier to parse the ordinary arithmetic
AB+ CD- EF* GH/
expression. We'll return to the difference between the human and
computer approaches in a moment. Before we explore into the
details of steps 1 and 2, we'll introduce postfix notation.

Stacks 13 Stacks 16

13 16

Infix Notation Infix and postfix expressions

⚫ Everyday arithmetic expressions are written with an Infix Postfix
operator ( +, –, *, or / ) placed between two operands
(numbers, or symbols that stand for numbers). This is A+B–C AB+C–
called infix notation, because the operator is written A*B/C AB*C/
inside the operands.
⚫ For Example A+B*C ABC*+
A+B C-D E*F G/H A*B+C AB*C+
⚫ In Infix Notation we must distinguish between
A*(B+C) ABC+*
(A+B)*C and A+(B*C)
⚫ The order of the operators and operands in arithmetic A*B+C*D AB*CD*+
expression doesn't uniquely determine the order in (A+B)*(C–D) AB+CD–*
which the operations are to be performed but by using
parenthesis and operator-precedence level we ((A+B)*C)–D AB+C*D–
determine the order evaluation.
Stacks 14 Stacks 17

14 17

Polish Notation (Prefix Notation) How Humans Evaluate Infix

⚫ Polish notation (Infix notation) named after the ⚫ How do you translate infix to postfix?
polish mathematician Jan Jukasiewicz, refers to the ⚫Let's examine a slightly easier question first:
notation in which the operator symbol is placed “how does a human evaluate a normal infix
before its two operands. expression”?
⚫ For Example ⚫ Although, this is difficult for a computer, we
+AB -CD *EF /GH humans do it fairly easily because of countless
hours in math class. It's not hard for us to find
⚫ The Fundamental Property of Polish notation is that the answer to 3+4+5, or 3*(4+5).
the order in which the operations are to be performed
is completely determined by the positions of the
⚫ By analyzing how we do this, we can achieve
some insight into the translation of such
operators and operands in expression. Accordingly, expressions into postfix.
we never need parenthesis when writing expression
in Polish notation
Stacks 15 Stacks 18

15 18

Balochistan University of Information

Technology & Management Sciences,
Quetta. 3
Data Structures and Algorithms 4/27/2026

How Humans Evaluate Infix Evaluation of Postfix Expression

⚫ Algorithms 7.4 This algorithm finds the VALUE of an
⚫ Roughly speaking, when you "solve" an arithmetic arithmetic expression P Written in Postfix notation
expression, you follow rules something like this: using a stack STACK to hold the operands.
1. You read from left to right. (At least we'll assume
this is true. Sometimes people skip ahead, but for 1. Add a right parenthesis “)” at the end of P. [this acts as a sentinel.]
purposes of this discussion, you should assume 2. Scan P from left to right and repeat step 3 and 4 for each element
you must read methodically, starting at the left.) of P until the sentinel “)” is encountered.
2. When you've read enough to evaluate two 3. If an operand is encountered push it on the STACK
operands and an operator, you do the calculation 4. If an operator  is encountered, then :
and substitute the answer for these two operands (a) Remove the two top elements of
and operator. (You may also need to solve other STACK, where A is the top element
pending operations on the left, as we'll see later.) and B is the next-to top element.
3. This process is continued—going from left to right (b) Set ANS := B  A
and evaluating when possible— until the end of the (C) Push ANS back to STACK
expression. 5. Set VALUE equal to the top element on STACK.
6. Exit
Stacks 19 Stacks 22

19 22

How Computer Evaluate Infix ? How Humans Translate Infix to Postfix

⚫ The Computer usually evaluates an arithmetic ⚫ To translate infix to postfix notation, you follow a
expression written in infix notation in two steps similar set of rules to those for evaluating infix.
⚫ First, it converts the expression to postfix notation, However, there are a few small changes. You don't do
and any arithmetic.
⚫ then it evaluates the postfix expression. ⚫ The idea is not to evaluate the infix expression, but to
⚫ In each step the stack is the main tool that is rearrange the operators and operands into a different
used to accomplish the given task. format: postfix notation. The resulting postfix
expression will be evaluated later.
⚫ First, we illustrate the second step that how
stacks are used to evaluate postfix ⚫ As before, you read the infix from left to right, looking
expressions and then we see how stacks are at each character in turn. As you go along, you copy
used to transform infix expressions into postfix these operands and operators to the postfix output
string. The trick is knowing when to copy what.
expressions.

Stacks 20 Stacks 23

20 23

Evaluating a postfix expression How Humans Translate Infix to Postfix (2)

⚫ We can use the following two rules shown in evaluate ⚫ If the character in the infix string is an operand, you
postfix expressions. copy it immediately to the postfix string. That is, if you
see an A in the infix, you write an A to the postfix.
Item Read from Postfix Expression Action There's never any delay: you copy the operands as
you get to them, no matter how long you must wait to
Operand Push it onto the stack. copy their associated operators.
Operator Pop the top two operands ⚫ Knowing when to copy an operator is more
from the stack, and apply complicated, but it's the same as the rule for
the operator to them. evaluating infix expressions. Whenever you could
Push the result into the stack. have used the operator to evaluate part of the infix
expression (if you were evaluating instead of
translating to postfix), you instead copy it to the postfix
⚫ When you're finished, pop the stack to obtain the answer. That's string.
all there is to it.
⚫ This process is the computer equivalent of the human approach.

Stacks 21 Stacks 24

21 24

Balochistan University of Information

Technology & Management Sciences,
Quetta. 4
Data Structures and Algorithms 4/27/2026

Translating A+B–C into postfix Saving Operators on a Stack

Character Read
from Infix
Infix Expression
Postfix
Expression Comments
⚫ You'll notice in both examples demonstrated in
Expression
parsed so Far
Written So Far last slides that the order of the operators is
A A A reversed going from infix to postfix. Because the
+ A+ A first operator can't be copied to the output until the
B A+B AB second one has been copied, the operators were
– A+B– AB+ When you see the –, output to the postfix string in the opposite order
you can copy the +
to the postfix string. they were read from the infix string. A longer
C A+B–C AB+C example may make this clearer.
End A+B–C AB+C– When you reach the ⚫ Next example shows the translation to postfix of
end of the expression,
you can copy the –.
the infix expression A+B*(C–D). We include a
column for stack contents, which we'll explain in a
moment.

Stacks 25 Stacks 28

25 28

Translating A+B*C to postfix Translating A+B*(C–D) to postfix

Character Read Infix Expression Postfix Expression Comments
from Parsed So Far Written So Far Character Read from Infix Expression Postfix Expression Stack Contents
Infix Expression Infix Expression Parsed So Far Written So Far
A A A
A A A
+ A+ A +
+ A+ A B A+B AB +
B A+B AB * A+B* AB +*
* A+B* AB Can't copy the +, ( A+B*( AB +*(
because * is higher C A+B*(C ABC +*(
precedence than +. – A+B*(C– ABC +*(–
C A+B*C ABC When you see the C, you D A+B*(C–D ABCD +*(–
can copy the *. ) A+B*(C–D) ABCD– +*(
A+B*C ABC* A+B*(C–D) ABCD– +*(
A+B*(C–D) ABCD– +*
End A+B*C ABC*+ When you see the end of
the expression, you can A+B*(C–D) ABCD–* +
copy the +. A+B*(C–D) ABCD–*+

Stacks 26 Stacks 29

26 29

Translating A*(B+C) into postfix Translation Rules

Character Read from Infix Expression Postfix Expression Comments

⚫ Let's make the rules for infix-to-postfix
Infix Expression Parsed So Far Written So Far translation more explicit. You read items from
A A A the infix input string and take the actions
* A* A shown in previous slides.
( A*( A
⚫ These actions are described in pseudo-code,
B A*(B AB Can't copy * because of
parenthesis. a blend of Java and English.
+ A*(B+ AB ⚫ In this table, the < and >= symbols refer to the
C A*(B+C ABC Can't copy the + yet.
operator precedence relationship, not
) A*(B+C) ABC+ When you see the ) you
Can copy the +.
numerical values. The opThis operator has
A*(B+C) ABC+* When you've copied the just been read from the infix input, while the
+, you can copy the*. opTop operator has just been popped off the
End A*(B+C) ABC+* Nothing left to copy stack.

Stacks 27 Stacks 30

27 30

Balochistan University of Information

Technology & Management Sciences,
Quetta. 5
Data Structures and Algorithms 4/27/2026

Translation rules
Item Read from Input(Infix) Action
Operand Write it to output (postfix)
Open parenthesis (
Close parenthesis )
Push it on stack
While stack not empty, repeat the following:
Pop an item,
The End
If item is not (, write it to output
Quit loop if item is (
Operator (opThis) If stack empty,
Push opThis
Otherwise,
While stack not empty, repeat:
Pop an item,
If item is (, push it, or
If item is an operator (opTop), and
If opTop < opThis, push opTop, or
If opTop >= opThis, output opTop
Quit loop if opTop < opThis or item is (
Push opThis

No more items While stack not empty,

Pop item, output it.

Stacks 31

31 34

Translating Infix Expressions (1)

Algorithm 7.5: POLISH(Q,P)
Suppose Q is an arithmetic expression written in infix notation.
This algorithm finds the equivalent postfix expression P.

1. Push “(“ onto STACK, and add “)” to the end of Q.

2. Scan Q from left to right and repeat Step3 to 6 for each element of Q until
the STACK is empty.
3. If an operand is encountered, add it to P.
4. If a left parenthesis is encountered, push it onto STACK.
5. If an operator  is encountered, then:
(a) Repeatedly pop from STACK and add to P each
operator ( on the top of the STACK) which has the
same precedence as or higher precedence than .
(b) Add  to STACK.
[End of if Structure]

Stacks 32

32

Translating Infix Expressions (2)

6. If a right parenthesis is encountered, than:
(a) Repeatedly pop from STACK and add to P each
operator ( on the top of STACK ) until a left parenthesis is
encountered.
(b) Remove the left parenthesis. [Do not the left parenthesis to P.]
[End of If structure.]
[End of Step 2 loop.]
7. Exit.

Stacks 33

33

Balochistan University of Information

Technology & Management Sciences,
Quetta. 6