[DATA STRUCTURE & Other Objects Using JAVA] Chapter 7 Queue

stack vs. queue

7.1 Introduction to Queues

  • A queue is a data structure of ordered items such that items can be inserted only at one end (called the rear) and removed at the other end (called the front). The item at the from end of the queue is called the first item.
  • Because items must be removed in exactly the same order as they were added to the queue, a queue is call a first in/first out data structure (FIFO).
  • The only difference between stack and queue is the rule that determines which item is removed first.

7.1.1 The Queue Class

  • The method for adding an item to the queue is often called an insert or enqueue operation.
  • The method for removing an item from the queue is often called a getFront of dequeue operation.
  • If a program attempts to remove an item from an empty queue, that is a kind of error called queue underflow.
  • Java’s queue also provides two alternative methods, offer() and poll(), that a queue can use instead of add and remove.

7.1.2 Uses for Queues

  • Because queues occur in real-life situations, they are frequently used in simulation programs.
  • Queues also appear in computer system software, such as the operating system that runs on Pc.
  • Buffering data in a queue is often used when one computer component is receiving data from another faster computer component.

7.2 Queue Applications

7.2.1 Java Queues

  • Java does not actually have a separate Queue class.
  • Java has a Queu interface.
  • But there are several other Java classes that implement the Queue interface.
  • If you want a simple Java queue, consider using the Queue interface and the LinkedList class.

7.2.2 Palindromes

  • A palindrome is a string that reads the same forward and backward.
  • We treat both the uppercase and lowercase versions of a letter as being the same character.
  • The program only accepts alphabetic letters.

7.2.3 Car Wash Simulation (Skipped)

7.3 Implementations of the Queue Class

7.3.1 Array Implementation of a Queue

  • When a class requires some small computation that is likely to be used several times, consider implementing the computation with a helper method (that is, a private method).

Invariant of the ArrayQueue Class

  1. The number of items in the queue is stored in the instance variable manyItems.
  2. For a non-empty queue, the items are stored in a circular array beginning at data[front] and continuing through data[rear].
  3. For an empty queue, manyItems is zero and data is a reference to an array, but we are not using any of the array, and we don’t care about front and rear.

Specification

Implementation

7.3.2 Linked List Implementation of a Queue

Invariant of the LinkedQueue Class

  1. The number of items in the queue is stored in the instance variable manyNodes.
  2. The items in the queue are stored in a linked list, with the front of the queue stored at the head node and the rear of the queue stored at the final node.
  3. For a non-empty queue, the instance variable front is the head reference of the linked list of items, and the instance variable rear is the tail reference of the linked list.

Implementation

7.4 Deques and Priority Queues

7.4.1 Double-Ended Queues

  • Entries can be quickly inserted and removed at both ends.
  • The ends of the deque are called front and back, but these designations are arbitrary since the same operations can occur at both ends.
  • In Java, deques are an interface, java.util.Deque, that includes all of the queue interface plus additional methods such as addFirst and removeLast.

7.4.2 Priority Queues

  1. A priority queue is a data structure that stores items along with a priority for each item.
  2. Items are removed in order of priority.
  3. The highest-priority item is removed first.
  4. If several items have equally high priorities, then the one that was placed in the priority queue first is the one removed first.

7.4.3 Priority Queue ADT — Specification

7.4.4 Priority Queue Class — An Implementation That Uses an Ordinary Queue