CS1020 Week 9 Content Overview
CS1020
Week 9: 19
th
March 2015
Contents
Practice Exercise 33
Practice Exercise 34
Take-home Lab #4
Week 9
2
Practice Exercise #33
QuickEat – Queue Implementation
Week 9
3
QuickEat (1/3)
Week 9
Problem:
The food is to be served to customers on first-come-first-
serve basis
The dishes are served only when ready
There are a limited amount of dishes
Dishes Ready but No Order
Throw Away !!
4
QuickEat (2/3)
Week 9
Each Dish Has Own Queue
Maintain
ArrayList Of
Dish Queues
Add More Dishes
5
QuickEat (3/3)
Week 9
Solution :
For Each Dish – maintain a queue for the Orders
P
r
o
c
e
s
s
t
h
e
I
n
p
u
t
c
o
r
r
e
c
t
l
y
:
O
r
d
e
r
(
#
T
a
g
)
(
#
D
i
s
h
O
r
d
e
r
e
d
)
(
#
D
i
s
h
I
d
)
…
.
.
R
e
a
d
y
(
#
D
i
s
h
I
d
)
For every order operation add to queue
For every ready operation process the queue and serve to
customer
6
Understand Question
Week 9
Things to take note:
Queue is an interface, not a class
cannot be instantiated
Maintain an arraylist for queue of all dishes
Use LinkedList class which has implementation of methods in
Queue interface
dishQueues.add(new LinkedList<Integer>());
Queue Operation
Use only methods in LinkedList class
that are legal for Queue
Eg – isEmpty(), offer(), poll()
7
Practice Exercise #34
WebBrowser – Stack Implementation
Week 9
8
WebBrowser (1/4)
Week 9
Problem:
Maintain the browsing history of User
User can move through the list websites viewed by
“BACKWRD” and “FORWARD” commands
Store every new website visited in the browsing history
Print the final browsing history
earliest
latest page as well as the current page
9
WebBrowser (2/4)
Week 9
Backward Stack
Forward Stack
Current Page
Current Page changes
to recently visited
URL
Back Operation – Pop
back stack – modify
current
Forward Operation –
Pop forward stack –
modify current
10
WebBrowser (3/4)
Week 9
Solution :
Maintain two separate stacks – Back And Forward
Check for corner case – when first page loads
Empty Forward Stack for each new page load
“BACKWARD” – Pop from back stack
move current
forward
“FORWARD” – Pop from forward stack
move current
backward
Print – Earliest to Latest page history
Also print the current page
11
WebBrowser (4/4)
Week 9
Things to take note:
Make use of Java Stack API
Alternatively, solution can be achieved using LinkedList ADT
Can try it to have practice on LinkedList
Familiarize with Stack API to prepare better for SitIn Lab 3
12
Take-home Lab #4
Exercise 1 – Cargo Optimization
Week 9
13
Cargo Optimization (1/3)
Week 9
Problem:
Containers arrives at the terminal in a random order,
addressed to different destination ships (A-Z)
They need to be stacked at the terminal
The destination ships arrives at the terminal in a fixed
sequence (A-Z)
14
Terminal
Cargo Optimization (2/3)
Week 9
Random
order
To: C
To: A
To: D
To: B
15
Cargo Optimization (3/3)
Week 9
Terminal
Fixed
order
16
Required Solution
Week 9
Minimally, how many stacks are needed, such that
destination ship has all its cargo is at the top when it
arrives?
Hint:
You should stack container #1 on top of another container #2
only if Container #1’s ship arrive
before or at the same time
as
container #2
You should always choose the stack whose
top container’s
ship’s arrival time is closest with the new container’s ship’s
arrival time
17
Take-home Lab #4
Exercise 2 – Queue Simulation
Week 9
18
Objective is to find the final queue resulting from
VIP customers and Regular Customers in
Queue and find the number of customers before
the specified customer
Solution
Always insert a VIP customer before a regular
customer in the queue
Redirect the links during insertion is a pre-requisite
Queue is always first come first serve. This
questions requires a modified priority queue.
Queue Simulation
Queue
Simulation
Week 9
19
Queue Visualization (VIP customer
enters the Queue) (1/4)
Queue
Simulation
VIP 1
Reg 2
Reg 3
Reg 1
head
First VIP Customer Arrived:
Week 9
20
Queue Visualization (VIP customer
enters the Queue) (2/4)
Queue
Simulation
VIP 1
Reg 2
Reg 3
Reg 1
head
Week 9
21
Queue Visualization (VIP customer
enters the Queue) (3/4)
Queue
Simulation
VIP 1
Reg 2
Reg 3
Reg 1
head
VIP 2
VIP 2 customers arrived:
Week 9
22
Queue Visualization (VIP customer
enters the Queue) (4/4)
Queue
Simulation
VIP 1
Reg 2
Reg 3
Reg 1
head
VIP 2
Week 9
23
Recap
Take Home Lab 4
Due: 10pm - 20
th
March
Familiarize with Stack and Queue API
Question??
Week 9
24
END OF FILE
Week 9
25
practice exercises and take-home lab for CS1020 Week 9, focusing on implementing queues and stacks for food serving and web browsing. Learn to handle operations efficiently using Java LinkedList class. Dive into solving problems related to maintaining browsing history and serving dishes to customers. Get a clear understanding of the concepts through detailed images and instructions."
Uploaded on Feb 20, 2025 | 1 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CS1020 Week 9: 19thMarch 2015
Contents Practice Exercise 33 Practice Exercise 34 Take-home Lab #4 2 Week 9
Practice Exercise #33 QuickEat Queue Implementation 3 Week 9
QuickEat (1/3) Problem: The food is to be served to customers on first-come-first- serve basis The dishes are served only when ready There are a limited amount of dishes Dishes Ready but No Order Throw Away !! 4 Week 9
QuickEat (2/3) Each Dish Has Own Queue Tag Tag Tag Tag Tag Tag Dish1 Maintain ArrayList Of Dish Queues Dish 2 Dish 3 Add More Dishes 5 Week 9
QuickEat (3/3) Solution : For Each Dish maintain a queue for the Orders Process the Input correctly : Order (#Tag) (#DishOrdered) (#DishId) .. Ready (#DishId) For every order operation add to queue For every ready operation process the queue and serve to customer 6 Week 9
Understand Question Things to take note: Queue is an interface, not a class cannot be instantiated Maintain an arraylist for queue of all dishes Use LinkedList class which has implementation of methods in Queue interface dishQueues.add(new LinkedList<Integer>()); Queue Operation Use only methods in LinkedList class that are legal for Queue Eg isEmpty(), offer(), poll() 7 Week 9
Practice Exercise #34 WebBrowser Stack Implementation 8 Week 9
WebBrowser (1/4) Problem: Maintain the browsing history of User User can move through the list websites viewed by BACKWRD and FORWARD commands Store every new website visited in the browsing history Print the final browsing history earliest latest page as well as the current page 9 Week 9
WebBrowser (2/4) Forward Operation Pop forward stack modify current Back Operation Pop back stack modify current Current Page Page Page Current Page changes to recently visited URL Page Page Page Page Backward Stack Forward Stack 10 Week 9
WebBrowser (3/4) Solution : Maintain two separate stacks Back And Forward Check for corner case when first page loads Empty Forward Stack for each new page load BACKWARD Pop from back stack move current forward FORWARD Pop from forward stack move current backward Print Earliest to Latest page history Also print the current page 11 Week 9
WebBrowser (4/4) Things to take note: Make use of Java Stack API Alternatively, solution can be achieved using LinkedList ADT Can try it to have practice on LinkedList Familiarize with Stack API to prepare better for SitIn Lab 3 12 Week 9
Take-home Lab #4 Exercise 1 Cargo Optimization 13 Week 9
Cargo Optimization (1/3) Problem: Containers arrives at the terminal in a random order, addressed to different destination ships (A-Z) They need to be stacked at the terminal The destination ships arrives at the terminal in a fixed sequence (A-Z) 14 Week 9
Cargo Optimization (2/3) To: B Random order To: D To: A Terminal To: C 15 Week 9
Cargo Optimization (3/3) D Fixed order C Terminal B A 16 Week 9
Required Solution Minimally, how many stacks are needed, such that destination ship has all its cargo is at the top when it arrives? Hint: You should stack container #1 on top of another container #2 only if Container #1 s ship arrive before or at the same time as container #2 You should always choose the stack whose top container s ship s arrival time is closest with the new container s ship s arrival time 17 Week 9
Take-home Lab #4 Exercise 2 Queue Simulation 18 Week 9
Simulation Queue Queue Simulation Objective is to find the final queue resulting from VIP customers and Regular Customers in Queue and find the number of customers before the specified customer Solution Always insert a VIP customer before a regular customer in the queue Redirect the links during insertion is a pre-requisite Queue is always first come first serve. This questions requires a modified priority queue. 19 Week 9
Queue Visualization (VIP customer enters the Queue) (1/4) Simulation Queue Reg 1 Reg 2 Reg 3 head VIP 1 First VIP Customer Arrived: 20 Week 9
Queue Visualization (VIP customer enters the Queue) (2/4) Simulation Queue Reg 1 Reg 2 Reg 3 head VIP 1 21 Week 9
Queue Visualization (VIP customer enters the Queue) (3/4) Simulation Queue Reg 1 Reg 2 Reg 3 head VIP 1 VIP 2 customers arrived: VIP 2 22 Week 9
Queue Visualization (VIP customer enters the Queue) (4/4) Simulation Queue Reg 1 Reg 2 Reg 3 head VIP 1 VIP 2 23 Week 9
Recap Take Home Lab 4 Due: 10pm - 20th March Familiarize with Stack and Queue API Question?? 24 Week 9
END OF FILE 25 Week 9
