Transcript COMP 121 Week 14

COMP 121
Week 14: Queues
Objectives
Learn how to represent a queue
 Learn how to use the methods in the
Queue interface
 Understand how to implement the Queue
interface

 Double-linked
list
 Single-linked list
 Circular array
Queue
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Queue Abstract Data Type
A First-In, First-Out (FIFO) data structure
 Can visualize a queue as a line of
customers waiting for service
 The next person to be served is the one
who has waited the longest
 New elements (people) are placed at the
end of the line

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
A Print Queue

Operating systems use queues to:
 Keep
track of tasks waiting for a scarce resource
 Ensure that the tasks are carried out in the order that
they were generated

Print queue
 Printing
is slower than the process of selecting pages
or documents to print
 Queue is used to store documents for printing
 Documents are printed in the order they were added
to the queue (unless a priority scheme is used)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
A Print Queue (continued)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Question: Why not use a Stack
to hold documents for printing?
Answer:
Stacks are last-in, first-out (LIFO)
 The most recently selected document
would be the next to print
 Unless the printer queue is empty, your
print job may never get executed if others
are issuing print jobs

Specification of a Queue
Interface
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Queue Methods

add and offer
 For
a queue of unlimited size, methods are logically
equivalent
 For a bounded queue, add will throw an exception if
the limit has been reached, but offer will return false

peek and element
 peek
will return null if the queue is empty, but element
will throw an exception

poll and remove
 poll
will return null if the queue is empty, but remove
will throw an exception
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
LinkedList Class and Queue
Interface
LinkedList class provides methods for
inserting and removing elements at either
end of a double-linked list
 The Java 5.0 LinkedList class implements
the Queue interface

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Queue Example

Queue<String> names = new
LinkedList<String>();
 Creates
a new Queue reference, names, that
stores references to String objects
 The actual object referenced by names is type
LinkedList<String>
 Because names is a type Queue<String>
reference, you can apply only the Queue
methods to it
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Using a LinkedList to Implement
the Queue Interface
Insertion and removal from either end of a
double-linked list is O(1) so either end can
be the front (or rear) of the queue
 In the Java 5.0 implementation, designers
decided to make the head of the linked list
the front of the queue and the tail the rear
of the queue

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Using a LinkedList to Implement
the Queue Interface (continued)

Because LinkedList implements Queue, it
is possible to apply other LinkedList
methods to a Queue (in addition to the
ones required by the Queue interface)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Question: What design pattern
could be used to create a better
design for a Queue?
Answer: Adapter Pattern

A better approach would be to create a
new class that wrappers a LinkedList and
implements the Queue interface
 Only
Queue methods would be available
 Queue methods would be implemented by
calling methods on the LinkedList
 Encapsulation would hide linked list
implementation from clients
Using a Single-Linked List to
Implement a Queue
Can implement a queue using a singlelinked list
 Class ListQueue contains a collection of
Node<E> objects
 Insertions are at the rear of a queue and
removals are from the front
 Need a reference to the last list node
 Number of elements in the queue is
changed by offer, poll, and remove

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Using a Single-Linked List to
Implement a Queue (continued)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Implementing a Queue Using a
Circular Array

Time efficiency of using a single- or
double-linked list to implement a queue is
acceptable


However there are some space inefficiencies
Storage space is increased when using a
linked list due to references stored at each
list node
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Implementing a Queue Using a
Circular Array (continued)

Array Implementation
 Insertion
at rear of array is constant time
 Removal from the front is linear time
 Removal from rear of array is constant time
 Insertion at the front is linear time

Circular Array Implementation
 Both
insertions and removals are constant
time
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Implementing a Queue Using a
Circular Array (continued)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Implementing a Queue Using a
Circular Array (continued)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Implementing a Queue Using a
Circular Array (continued)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Implementing a Queue Using a
Circular Array (continued)
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Comparing the Implementations

All three implementations are comparable
in terms of computation time
 All

operations are O(1)
Linked-list implementations require more
storage because of the extra space
required for the links
 Each
node for a single-linked list would store
a total of two references
 Each node for a double-linked list would store
a total of three references
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Comparing the Implementations
(continued)
A circular array that is filled to capacity
would require half the storage of a singlelinked list to store the same number of
elements
 A circular array that was just reallocated
would be half empty and require the same
amount of storage as a single-linked list

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Simulating Waiting Lines Using
Queues
Simulation is used to study the
performance of a physical system by using
a physical, mathematical, or computer
model of the system
 Simulation allows designers of a new
system to estimate the expected
performance before building it

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Simulating Waiting Lines Using
Queues (continued)
Simulation can lead to changes in the
design that will improve the expected
performance of the new system
 Useful when the real system would be too
expensive to build or too dangerous to
experiment with after its construction

Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Simulating Waiting Lines Using
Queues (continued)

System designers often use computer
models to simulate physical systems
 Airline

check-in counter for example
A special branch of mathematics called
queuing theory has been developed to
study such problems
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Summary



Queue is an abstract data type with a first-in,
first-out structure (FIFO)
The Queue interface declares methods offer,
remove, poll, peek, and element
Multiple ways to implement the Queue interface
 Double-linked

list, single-linked list, and circular array
Queues are often used in simulation
 To
avoid the cost of building a physical system or
running an actual experiment, computer simulation
can be used to evaluate the expected performance of
a system or operation strategy
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Any Questions?