Data

Structures�Course
Chapter 3: Stack
Code: CSE 220

Real Life Examples of Stack

LIFO (Last In First Out)

2

Stack Operations: Push and Pop Explained

Stack Basic Operations: Push and Pop

Three basic stack operations.

● push(obj)
● pop ()
● peek()

Stack Push Operation Explained!

Stack Pop Operation Explained!

Stack Peek Operation Explained!

Makes Sense! Now, How to Code

a Stack? 😒

The underlying structure for a

stack can be:
● Linked List
● Array
● ArrayList

10

Linked List-Based Implementation of Stack

Linked List-based implementation provides the best (from the

efficiency point of view) dynamic stack implementation.
11

Linked List Based Implementation - Node Creation (Continued)

● First, we have to create a Class Node.

Java Python 12

Linked List Based Implementation - Push (Continued)

● Adding a new node in the Stack is termed a push operation.

Pseudocode
13

Linked List Based Implementation - Push (Continued)

Java Python

14

Linked List Based Implementation - Pop (Continued)

● Deleting a node from the Stack is known as a pop operation.

Pseudocode
15

Linked List Based Implementation - Pop (Continued)

Java Python
16

Linked List Based Implementation - Peek (Continued)

● In the peek operation, we simply return the data stored in the head/top of the
Linked List based Stack.

Pseudocode
17

Linked List Based Implementation - Peek (Continued)

Java Python
18

Array-Based Implementation of Stack

19

Stack Application - Call Stacks

Whenever your program calls a function, the compiler creates a so-called stack record that contains
important information about that function, such as storage for its parameters, its return value, and
its local variables. The compiler pushes this stack record onto something called a call stack. 20

Stack Application - Reverse

21

Stack Application - Undo/Redo

22

Stack Application - Postfix Notation

3 + 5 * 9

3 5 9 * +

23

Stack Application - Postfix Notation (Continued)

((3 + 2) * 4) / (5 - 1)

3 2 + 4 * 5 1 - /

24

Stack Application - Expression Evaluation

32+4*51-/

25

Stack Application - Expression Evaluation Notation (Continued)

Pseudocode
26

Stack Application - Parenthesis Matching

(a (b + c) + d) (a (b + c) + d
[ (a b) (c d) ] [ (a b] (c d) )
( [a {x y} b] ) ( [a {x y) b] )

Correct Incorrect

27

Stack Application - Parenthesis Matching (Continued)

28

Stack Application - Parenthesis Matching (Continued)

29

Stack Application - BackTracking (Maze) (Continued)

30

Stack Application - BackTracking (Continued)

31

Practise Problem

Count the Elements of a Stack

32

Practise Problem

Reverse a Number using Stack

33

Practise Problem

Delete the Third Element from the Stack

34

Practise Problem

Mid Reversal of Stack

6 3

5 2

4 1

3 6

2 5

1 4 35

Practise Problem

36

Practise
Problem

37

Practise Problem

38

More More Practise Problem 🙂

Solve all the exercise

problems from the book
�+�Practise Sheet

39