Scribd
Upload
71 views

Data Structures and Algorithms: (CS210/ESO207/ESO211)

This document discusses stacks as a new data structure and how they can be used to solve problems like mazes, the eight queens problem, and evaluating arithmetic expressions. It introduces stacks and their operations like push, pop, and peek. Stacks allow insertion and deletion only at one end, called the top. The document then explains how stacks can be used to efficiently evaluate arithmetic expressions by using operator precedence and stacks to remove the need for multiple expression scans. Finally, it previews that the next class will present a simple stack-based approach to expression evaluation.

Uploaded by

Moazzam Hussain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
71 views

Data Structures and Algorithms: (CS210/ESO207/ESO211)

This document discusses stacks as a new data structure and how they can be used to solve problems like mazes, the eight queens problem, and evaluating arithmetic expressions. It introduces stacks and their operations like push, pop, and peek. Stacks allow insertion and deletion only at one end, called the top. The document then explains how stacks can be used to efficiently evaluate arithmetic expressions by using operator precedence and stacks to remove the need for multiple expression scans. Finally, it previews that the next class will present a simple stack-based approach to expression evaluation.

Uploaded by

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

Data Structures and Algorithms

(CS210/ESO207/ESO211)
Lecture 9

Stack: A new data structure
1
Stack: a new data structure
2
Motivation

Maze problem: How to design an algorithm for finding a path in a maze ?

8 queens problem: How to efficiently find a way to place 8 queens on a
chess board so that no two of them attack each other ?

Did you even wonder how recursion is actually implemented during
execution of a program ?

How does a computer program evaluate arithmetic expression ?
x = 3+4*(5-6*(8+9^2)+3)
3
Stack: a new data structure
Data Structure Stack:

Mathematical Modeling of Stack

Implementation of Stack (will be left as an exercise)

4
5
Revisiting List
List is modeled as a sequence of elements.

L:
1
,
2
, ,
1
,

,
+1
, ,



ith element of list L
T
o
p
In a list, we can insert/delete/query
element at any arbitrary position in the list.
What if we restrict all these operations to
take place only at one end of the list ?
Stack: a new data structure
A special kind of list where all operations (insertion, deletion, query) take
place at one end only, called the top.
6

1

top
Operations on a Stack
Query Operations
IsEmpty(S): determine if S is an empty stack.
Top(S): returns the element at the top of the stack.
Example: If S is
1
,
2
, ,

, then Top(S) returns ?? .


Update Operations
CreateEmptyStack(S): Create an empty stack.
Push(x,S): push x at the top of the stack S.
Example: If S is
1
,
2
,,

, then after Push(x,S), stack S becomes


??
Pop(S): Delete element from top of the stack S.
Example: If S is
1
,
2
,,

, then after Pop(S), stack S becomes


??

7
,
1
,
2
,,

2
,,

1

8
An Important point about stack:
How to access ith element from the top ?








To access ith element, we must pop (hence delete) one by
one the top i-1 elements from the stack.

1

Evaluation of an arithmetic expression
How does a computer/calculator evaluate an arithmetic expression given in
the form of a string of symbols?


8 + 3 * 5 ^ 2 9


First it splits the string into tokens which are operators or operands
(numbers). This is not difficult. But how does it evaluates it finally ???

9
operands
operators
Precedence of operators
Precedence: priority among different operators

Operator + has same precedence as .
Operator * (as well as /) has higher precedence than +.
Operator * has same precedence as /.
Operator ^ has higher precedence than * and /.
10
A trivial way to evaluate an arithmetic
expression

First perform all ^ operations.
Then perform all * and / operations.
Then perform all + and - operations.

Disadvantages:
1. An ugly and case analysis based algorithm.
2. Multiple scans of the expression.
3. What about expressions involving parentheses : 3+4*(5-6*(8+9^2)+3)
4. What about associativity of the operators:
2^3^2 = 512 and not 64
16/4/2 = 2 and not 8.


11
8 + 5 3
*
^ 2 9 -

In the next class (27 August), we shall devise a very
simple, elegant, efficient and compact way to evaluate
an arithmetic expression based on stacks.
(Though it was briefly outlined in todays class, we shall do it all
over again.)

See you on 27 August at 9 AM.
12

You might also like