The Self-Taught Computer Scientist

first- out data structure, the first item to enter the data structure is the first to come out of it. Queues, 
like stacks, are limited access data structures.
Queues have two primary operations: enqueueing and dequeueing (Figure 12.2). Enqueueing means 
adding an item to a queue, whereas dequeueing means removing an item. You enqueue elements to 
the rear of a queue and dequeue them from the front.
Remove
Add
Rear
Front
A
B
C
D
Figure 12.1: In a queue, you add items to the rear and remove them from the front.
40
5
Front
Dequeue
Enqueue
Rear
76
19
30
20
10
Figure 12.2: The primary operations of queues are enqueueing and dequeueing.

---

Data Structures
128
There are several different ways to implement the queue abstract data type as a data structure. For 
example, like with stacks, you can implement a queue data structure using an array or a linked list. 
Also, like stacks, queues can be bounded or unbounded. A bounded queue is one that limits how 
many items you can add to it, while an unbounded queue is one that does not limit how many items 
you can add to it. You can create a bounded queue using an array or an unbounded one using a linked 
list (you can also implement a bounded queue using a linked list if you keep track of the number of 
items you’ve stored in the queue).
When to Use Queues
Like stacks, queues are efficient for adding or removing data (Figure 12.3). Enqueueing and dequeue-
ing are both O(1) regardless of the queue’s size. Like stacks, queues are not efficient for accessing 
individual pieces of data because you have to iterate through a queue’s elements to find an item. That 
means accessing an item in a queue and searching a queue are both O(
n).
As a programmer, you will frequently use queues. Queues are an ideal data structure when you are 
programming anything that relates to first come, first served. For example, a queue is helpful for 
programming an automated phone system that puts a caller in line when all the available operators 
are busy and then connects the earliest caller first, followed by callers who dialed in later. Operating 
systems use queues to handle requests to write data to a hard disk drive, stream audio and video, and 
send and receive network packets. Web servers, on the other hand, use queues to handle 
incoming requests.
Whenever you see a “buffering” message, it means the software system you are using is probably 
waiting for incoming data to add to its queue for processing. For example, to ensure smooth stream-
ing, audio and video streaming systems often set up a queue for incoming data. Say you are watching 
a movie on Netflix. The software on your TV responsible for showing you the movie might wait a 
Data 
Structure
Time Complexity
Average
Worst
Access
Search
Insertion Deletion
Access
Search
Insertion Deletion
Array
O(1)
O(n)
O(n)
O(n)
O(1)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Queue
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Linked 
List
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Hash 
Table
N/A
O(1)
O(1)
O(1)
N/A
O(n)
O(n)
O(n)
Binary 
Search 
Tree
O(log n)
O(log n)
O(log n)
O(log n)
O(n)
O(n)
O(n)
O(n)