Algorithms C++ Edition (2015)

Part 2: Switching List Types

If you switch to the other list type (array or linked list), you should have the same results. Try it out, and note the differences between the two data structures.

Chapter 2a: Abstract Data Types: The Queue

The Queue

A Queue is also a list or sequence of items. Each item awaits for its turn to be processed - as if it were a person lining up for something.

The data objects in a queue would be inserted and retrieved in a First-In-First-Out process.

A Queue will usually have two main functions defined along with it: enqueue (insert to the lineup, at the back) and dequeue (remove from the lineup).

How the Queue Works

Think of a queue as a lineup. For anything. It could be the lineup at your bank, at your favourite fast food restaurant, the nightclub, anything that resembles a lineup.

And in a lineup, someone enters the line at the back. As the lineup grows, more people enter the line at the back. Whoever is at the front of the line is serviced - they deal with customer service, have their order taken, get in the nightclub, anything the lineup does. And whenever someone is serviced, the lineup becomes smaller.

A queue works essentially the same way. You input data items into a lineup, with the most recent data items at the back of the line. When data items are retrieved, the oldest item is retrieved first.

When to Use the Queue

Whenever you have a list of data items and they must be processed in a ‘lineup matter’, use the Queue. Once you notice it uses a First-In-First-Out process for any objects it takes in, use a queue.

Online Video Games are a great example. If you had to log into any game server to play, your login request would be sent to a “lineup” of login requests from everyone else who wants to play too. The most recent request is always at the end of that lineup. The game server processes each login request to have its player log into the server - one by one, starting with the front of the lineup.

Also, recall that queues normally use lists - either arrays or linked lists. Again, which one do you choose?

By default, use Linked Lists for queues - as queueing and dequeueing are computed in constant time ( O(1) ) - the quickest tier for algorithm speed.

On the other hand, use Arrays for queues if any data items within that queue need to be accessed often. For Array Queues, you’ll use Circular Arrays - an array with the starting index (0) right after the ending index (the array size - 1). This is so that data items are added and removed without having to shift EVERY data item left or right all the time(which would really strain your program and computer effort).

And Circular Array Queues can be just as fast - queueing and dequeueing can also be in constant time. You just have the extra flexibility to edit the lineup as you please.

So depending on which data structure you use, the next chapters show you how you implement a stack.