Scribd
Upload
74 views

CC103 - Data Structure and Algorithm

This document provides an overview of stacks as a data structure. It discusses stack representation using arrays or linked lists, common stack operations like push and pop, and examples of stacks in evaluating function calls by keeping track of the call stack and evaluating mathematical expressions in postfix notation by processing operands and operators in order. The objectives are to practice using stacks, understand their representation, apply stack operations like push and pop, and identify stacks in examples.

Uploaded by

Mary Ann Magleo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPSX, PDF, TXT or read online on Scribd
74 views

CC103 - Data Structure and Algorithm

This document provides an overview of stacks as a data structure. It discusses stack representation using arrays or linked lists, common stack operations like push and pop, and examples of stacks in evaluating function calls by keeping track of the call stack and evaluating mathematical expressions in postfix notation by processing operands and operators in order. The objectives are to practice using stacks, understand their representation, apply stack operations like push and pop, and identify stacks in examples.

Uploaded by

Mary Ann Magleo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPSX, PDF, TXT or read online on Scribd
You are on page 1/ 28

CC103 - Data Structure and Algorithm

Week 5:
Stacks

CC103 - Data Structure and Algorithm


LESSON 5: Stacks

OBJECTIVES:
At the end of the topic session the students are
expected to:

1. Practice the use of stack.


2. Use the representation of stack.
3. Apply the stack operations.
4. Pop an element from a stack.
5. Identify stack though the given examples.

CC103 - Data Structure and Algorithm


3
LESSON 5: Stacks

Stack

cafeteria-tray holder

CC103 - Data Structure and Algorithm


4
LESSON 5: Stacks

Stack Representation
 Two ways to represent a stack
 insertion, deletion, and retrieval are done from the last element in the array
(Arr[n]).
 used when the maximum size of the stack is known.

1. Doubly-Linked List Representation

CC103 - Data Structure and Algorithm


5
LESSON 5: Stacks

Stack Operations

CC103 - Data Structure and Algorithm


6
LESSON 5: Stacks

Pushing an Element into a Stack

CC103 - Data Structure and Algorithm


7
LESSON 5: Stacks

Popping an Element from a Stack

8
CC103 - Data Structure and Algorithm
LESSON 5: Stacks

Example 1: Function calls


Stacks: used by computers to process function calls and their returns

CC103 - Data Structure and Algorithm


9
LESSON 5: Stacks

Function Calls
When PROC1 begins executing, the stack will contain:

When FUNC1 is invoked by PROC1:

CC103 - Data Structure and Algorithm


10
LESSON 5: Stacks

Function Calls
 When FUNC1 will reference FUNC2, the stack will contain the following
information:

CC103 - Data Structure and Algorithm


11
LESSON 5: Stacks

Function Calls
The stack will now contain:

The stack will now have the following information:

Ø Once FUNC1 has completed, the same


procedure will be performed by the system to
return processing to PROC1.

CC103 - Data Structure and Algorithm


12
LESSON 5: Stacks

Example 2: Evaluation of Expressions


 An expression is made up of operands and operators.
 The operations to be performed on the operands are described by the
associated operator.

This expression has 5 operands: A,B,C,D and E and uses 3 operators: *, +, and /.

Four basic operators

CC103 - Data Structure and Algorithm


13
LESSON 5: Stacks

Evaluation of Expressions
* and / - have equal precedence
- have a higher precedence than + and -
+ and - - have equal precedence

In evaluating any given expression, operators with a higher precedence are


processed first. When two adjacent operators in an expression have the same
precedence, evaluation is performed from left-to-right.

CC103 - Data Structure and Algorithm


14
LESSON 5: Stacks

Evaluation of Expressions
Any expression within a pair of parentheses will have the highest precedence and
will be evaluated first.

CC103 - Data Structure and Algorithm


15
LESSON 5: Stacks

Evaluation of Expressions

CC103 - Data Structure and Algorithm


16
LESSON 5: Stacks

POSTFIX Notation

CC103 - Data Structure and Algorithm


17
LESSON 5: Stacks

POSTFIX Notation

CC103 - Data Structure and Algorithm


18
LESSON 5: Stacks

POSTFIX Notation

CC103 - Data Structure and Algorithm


19
LESSON 5: Stacks

PSEUDOCODE
Representation

CC103 - Data Structure and Algorithm


20
LESSON 5: Stacks

PSEUDOCODE
Representation

CC103 - Data Structure and Algorithm


21
LESSON 5: Stacks

PSEUDOCODE
Representation

CC103 - Data Structure and Algorithm


22
LESSON 5: Stacks

PSEUDOCODE
Representation

CC103 - Data Structure and Algorithm


23
LESSON 5: Stacks

PSEUDOCODE
Representation

CC103 - Data Structure and Algorithm


24
LESSON 5: Stacks

PSEUDOCODE
Representation

CC103 - Data Structure and Algorithm


25
LESSON 5: Stacks

PSEUDOCODE
Representation

CC103 - Data Structure and Algorithm


26
LESSON 5: Stacks

CLASSWORK
Determine the output of the Postfix algorithm when the following expressions
are used as input.

CC103 - Data Structure and Algorithm


27
LESSON 1: Orientation and Course Introduction

THE END

CC103 - Data Structure and Algorithm

You might also like