CS 103 1 Queues • Definition of a Queue • Examples of Queues

Download, print and study this document offline |

Page 1 CS 103 1 Queues • Definition of a Queue • Examples of Queues • Design of a Queue Class • Different Implementations of the Queue Class Page 2 CS 103 1 Queues • Definition of a Queue • Examples of Queues • Design of a Queue Class • Different Implementations of the Queue Class CS 103 2 Definition of a Queue • A queue is a data structure that models/enforces the first-come first-serve order, or equivalently the first-in first-out (FIFO) order. • That is, the element that is inserted first into the queue will be the element that will deleted first, and the element that is inserted last is deleted last. • A waiting line is a good real-life example of a queue. (In fact, the Britich word for “line” is “queue”.) Page 3 CS 103 1 Queues • Definition of a Queue • Examples of Queues • Design of a Queue Class • Different Implementations of the Queue Class CS 103 2 Definition of a Queue • A queue is a data structure that models/enforces the first-come first-serve order, or equivalently the first-in first-out (FIFO) order. • That is, the element that is inserted first into the queue will be the element that will deleted first, and the element that is inserted last is deleted last. • A waiting line is a good real-life example of a queue. (In fact, the Britich word for “line” is “queue”.) CS 103 3 A Graphic Model of a Queue Tail: All new items are added on this end Head: All items are deleted from this end Page 4 CS 103 1 Queues • Definition of a Queue • Examples of Queues • Design of a Queue Class • Different Implementations of the Queue Class CS 103 2 Definition of a Queue • A queue is a data structure that models/enforces the first-come first-serve order, or equivalently the first-in first-out (FIFO) order. • That is, the element that is inserted first into the queue will be the element that will deleted first, and the element that is inserted last is deleted last. • A waiting line is a good real-life example of a queue. (In fact, the Britich word for “line” is “queue”.) CS 103 3 A Graphic Model of a Queue Tail: All new items are added on this end Head: All items are deleted from this end CS 103 4 Operations on Queues • Insert(item): (also called enqueue) – It adds a new item to the tail of the queue • Remove( ): (also called delete or dequeue) – It deletes the head item of the queue, and returns to the caller. If the queue is already empty, this operation returns NULL • getHead( ): – Returns the value in the head element of the queue • getTail( ): – Returns the value in the tail element of the queue • isEmpty( ) – Returns true if the queue has no items • size( ) – Returns the number of items in the queue Page 5 CS 103 1 Queues • Definition of a Queue • Examples of Queues • Design of a Queue Class • Different Implementations of the Queue Class CS 103 2 Definition of a Queue • A queue is a data structure that models/enforces the first-come first-serve order, or equivalently the first-in first-out (FIFO) order. • That is, the element that is inserted first into the queue will be the element that will deleted first, and the element that is inserted last is deleted last. • A waiting line is a good real-life example of a queue. (In fact, the Britich word for “line” is “queue”.) CS 103 3 A Graphic Model of a Queue Tail: All new items are added on this end Head: All items are deleted from this end CS 103 4 Operations on Queues • Insert(item): (also called enqueue) – It adds a new item to the tail of the queue • Remove( ): (also called delete or dequeue) – It deletes the head item of the queue, and returns to the caller. If the queue is already empty, this operation returns NULL • getHead( ): – Returns the value in the head element of the queue • getTail( ): – Returns the value in the tail element of the queue • isEmpty( ) – Returns true if the queue has no items • size( ) – Returns the number of items in the queue CS 103 5 Examples of Queues • An electronic mailbox is a queue – The ordering is chronological (by arrival time) • A waiting line in a store, at a service counter, on a one-lane road • Equal-priority processes waiting to run on a processor in a computer systemRead More

Download as PDF