Sharing a Printer

In an office or a computer lab, many computers often share a single printer. The printer can only print one document at a time, but several people might click “print” within a few seconds of each other. The documents cannot all print at once, so some of them have to wait. In what order should they be printed?

The fair answer is the order in which they arrived. To implement this, we need to keep track of the print jobs in the order they were submitted. We can use a data structure like ArrayList or LinkedList to store these jobs. Each time a job arrives, we add it to the end of the list. When the printer becomes free, we remove the job at the front of the list, the one that has been waiting the longest, and print it.

Notice the access pattern: we only ever add at one end and remove at the other. We never look up a job in the middle of the list, and we never remove one out of order. So, as with the stack, it makes sense to restrict the data structure, this time to allow adding only at one end and removing only at the other. That restriction also protects the order of the jobs.

The shared printer is just one example. Your operating system does the same with keystrokes: when you type faster than a program can react, the keystrokes wait in a buffer and are processed in the order you typed them. A web server does something similar: if it receives requests faster than it can handle them, it buffers the requests and serves them in the order they came in. Many applications and algorithms need a structure like this.

In this chapter, we will study a data structure called a queue, which does that. The name comes from the everyday meaning of the word: a queue is a line of people waiting for their turn, where you join at the back and are served from the front.