CP164 Final: Queue ADT
Notes - The Queue ADT
A Simple Queue
The queue ADT represents a First-In-First-Out (FIFO) data structure. Data items are added
to the rear of the queue and removed from the front of the queue meaning that the first
item added to the queue is always the first item removed from the queue. (Think of a queue
as a line-up at a cinema or for OSAP.)
Queue Methods
The basic queue methods are:
• initialize: create an empty queue
• insert: adds a new value to the rear of the queue
• remove: removes and returns the value in the front of the queue, if one exists
• peek: return a copy of the value at the front of the queue without removing it, if one exists
• is empty: returns True if the queue is empty, False otherwise
• is full: returns True if the queue is full, False otherwise
• length: returns the number of items in the queue
Any implementation of a queue must define these methods.
Uses for a Queue
Simulation
Queues are often used to simulate real-life situations that involve some kind of line-
ups such as crowd control, materials processing, and instruction processing.
Searching and Traversing
Like stacks, we can use queues to search another data structure. However, a queue
performs a Breadth-First Search, rather than the Depth-First search performed by a
stack.
The following sample maze is the same one seen when we looked at the Stack ADT. Solving
a maze using a queue uses the Breadth-First Search algorithm.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
The queue adt represents a first-in-first-out (fifo) data structure. Any implementation of a queue must define these methods. Queues are often used to simulate real-life situations that involve some kind of line- ups such as crowd control, materials processing, and instruction processing. Like stacks, we can use queues to search another data structure. However, a queue performs a breadth-first search, rather than the depth-first search performed by a stack. The following sample maze is the same one seen when we looked at the stack adt. Solving a maze using a queue uses the breadth-first search algorithm. In this sample maze, the circles represent a decision point, and the letters represent one of the paths that can be taken at the decision point. The rules to follow when solving the maze are: move to an intersection and add all the choices at that intersection onto the queue.
