IU-VNU-HCM
LOGO
Data Structures and Algorithms
Robert Lafore, Data structures and Algorithms in Java, Waite Group Press, 2002
Lecture 4. Stack & Queue
Trong Hai Duong, PhD
Email:
[email protected]Mobile phone: 0945090908
Homepage: http://co-intelligence.vn
Outline
Stacks
Queues
Priority Queues
Parsing Arithmetic Expressions
STACK
Introduction
Accessible item ?
Last inserted item
Last in, first out (LIFO)
Operations
Push ?
Pop ?
Peek ?
Properties
Stack Overflow (Full)
Stack Underflow (Empty)
4
Stack info
Info must be managed?
Stack size (is full?)
Number of element (is empty?)
Top item (accessible item)
Company Logo
Application
Reversing an array/ a word
100
120
150
200
Delimiter Matching
100 * (100 50) Correct
[100 * (100 50)] /2 Correct
[100 * (100 50)} /2 Incorrect, error on }
[100 * (100 50) /2 Incorrect, error on [
(100 * (100 50))) /2 Incorrect, error on )
250
How would you do it?
Reversing a array
100
120
150
200
250
250
200
150
120
250
100
200
150
120
100
How would you do it?
Delimiter Matching
(a * [b c]) / d
Character
Read
Stack
contents
([
([
([
([
)
/
d
9
Implementation
See code in page
10
Efficiency of Stacks
Complexity of
Push
Pop
Peek
All of them are O(1)
11
QUEUE
12
Introduction
Accessible item ?
First inserted item
First in, first out (FIFO)
Tail / Head of
queue
Operations
Insert / Enqueue
Remove / Dequeue
Properties
Full
Empty
13
Queue info
Info must be managed?
Queue size (is full?)
Number of element (is empty?)
Head / tail item (accessible item)
14
Company Logo
r
t
g
g
y
m
r
t
g
g
y
m
r
t
g
g
y
Before
Enqueue
Dequeue
m
r
t
g
g
After
y
Company Logo
Application
Printer queue
File queue
Request queue
17
Look at some code
Textbox p.137
18
Efficiency of queue
Enqueue?
Dequeue?
O(1)
19
Question
Which of the following is true?
a. The pop operation on a stack is considerably
simpler than the remove operation on a queue.
b. The contents of a queue can wrap around, while
those of a stack cannot.
c. The top of a stack corresponds to the front of a
queue.
d. In both the stack and the queue, items removed
in sequence are taken from increasingly high
index cells in the array.
20
Priority queue
Head / tail
Enqueue /
Dequeue with
criteria
E.g, dequeue
Highest value, or
Most severe patient,
Ascendingpriority /
descendingpriority queue
21
Efficiency of Priority queue
Insertion ?
If use ARRAY: O(N)
Deletion ?
O(1)
22
Operation
Enqueue
23
Operation
Dequeue
24
Question
One difference between a priority
queue and an ordered array is that
a. the lowest-priority item cannot be
extracted easily from the array as it
can from the priority queue.
b. the array must be ordered while the
priority queue need not be.
c. the highest priority item can be
extracted easily from the priority
queue but not from the array.
d. All of the above.
25
PARSING ARITHMETIC
EXPRESSION
26
Introduction
How would you evaluate an
expression?
3+4-5
Or (10-5)*2 + (6+4)*3
27
Evaluate 3 + 4 -5
28
Evaluate 3 + 4 -5
29
Algorithm
For computer algorithms:
difficult to evaluate arithmetic
expression directly
Solution
Transform arithmetic expression into
a different format POSTFIX
Evaluation the postfix expression
30
Postfix Notation
To develop a string where the
operators (*, -, +,) appear last
(hence the term: postfix).
e.g. ab+.
Also known as Reverse Polish Notation
Normally use infix notation
a+b.
Most of the operators we use are binary.
There is also a prefix notation, which
has more limited applications.
Infix and postfix notations
In postfix notation, an operator
operates on the two previous
operands. That is the rule.
Table: infix to postfix notations
Parentheses override normal
hierarchical evaluation
Infix
Postfix
a+b-c
ab+c-
a*b/c
ab*c/
a+b*c
abc*+
a*b+c
ab*c+
a*(b+c)
abc+*
a*b+c*d
ab*cd*+
((a+b)*c)-d
ab+c*d-
a+b*(c-d/(e+f))
abcdef+/-*+
How Humans Translate Infix
into Postfix
- has the same priority
with +
How about * or / ?
How Humans Translate Infix
into Postfix
How Humans Translate Infix
into Postfix
How Humans Translate Infix into Postfix
Saving
Operators on
a Stack
Redundancy?
See Algorithms
& Next
Examples
38
Example
39
Example
40
Click icon to add
picture
Example
41
