Note 3.10.1. Nomenclature.
There are many ways to refer to the removal and addition points of a queue: “front and rear”; “front and back”; and “head and tail”. The Java documentation uses the latter notation, and so will we.
Section 3.10 Queues
A queue is an ordered collection of items where the addition of new items happens at one end, called the tail, and the removal of existing items occurs at the other end, commonly called the head. As an element enters the queue it starts at the tail and makes its way toward the head, waiting until that time when it is the next element to be removed.
The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the head. This ordering principle is sometimes called FIFO, first in, first out. It is also known as first come, first served.
The simplest example of a queue is the typical line that we all participate in from time to time. We wait in a line for a movie, we wait in the checkout line at a grocery store, and we wait in the cafeteria line (so that we can pop the tray stack). Well-behaved lines, or queues, are very restrictive in that they have only one way in and only one way out. There is no jumping in the middle and no leaving before you have waited the necessary amount of time to get to the front.
Computer science also has common examples of queues. Figure 3.10.2 shows a queue of Java Strings.
Another example of a queue is a computer laboratory of 30 computers networked with a single printer. When students want to print, their print tasks “get in line” with all the other printing tasks that are waiting. The first task in is the next to be completed. If you are last in line, you must wait for all the other tasks ahead of you to print. We will explore this interesting example in more detail later.
In addition to printing queues, operating systems use a number of different queues to control processes within a computer. The scheduling of what gets done next is typically based on a queuing algorithm that tries to execute programs as quickly as possible and serve as many users as it can. Also, as we type, sometimes keystrokes get ahead of the characters that appear on the screen. This is due to the computer doing other work at that moment. The keystrokes are being placed in a queue-like buffer so that they can eventually be displayed on the screen in the proper order.
You have attempted of activities on this page.
