Anyone who doesn't live in a town of two to three people has waited in a line before. Sure, nobody likes it, but at the same time it feels much more fair than other forms of deciding who goes first at the deli counter line. Maybe people have been talking about creating a FIFA-style shoot-out match in the can aisle to resolve any claims of cutting, but that sounds like a lot of

• time.
• energy.
• dented Campbell's.

As fun as it sounds to accidentally topple over a stack of tomato soup cans and start a stock avalanche in aisle three, waiting in line's probably better for both you and the store. Cutting in line can be annoying, but as long as you don't shop for cured meats on Black Friday, you probably won't see any fist fights.

If you're waiting in line (on line?), you're actually standing in a queue. Try not to freak out. Queues are an abstract data type (ADT) where the first element in is also the first element out, making them First In, First Out (FIFO) and Last In, Last Out (LILO) structures. This is in an idealized world where every line has those stretchy tape poles that keep people from trying to jump into the line wherever they want.

Whenever you add something to a queue, you're enqueuing it, which adds it to the back of the line. When you take something out, you're dequeuing it, which takes out the first element. Just like with stacks, you can only see one end of the queue, but this time that end's the beginning. You can't just jump around anywhere you want in the queue, otherwise…you shouldn't be using a queue.

You can create a queue using either a linked list or an array, but most people go with arrays because queues are just ordered like that. If you create a queue using an array, the front is assumed to be at the index 0 (queue_name[0]), at least to start. If the final position for an element is at index n, then you'll add a new element to the index n + 1.

 

Queues as arrays get tricky the minute you try to remove an element. Because queue[0] is assumed to be the front, you'll need to do something to fill the space when you take the front element out, making that first value null.

You have two choices. You can either shift the whole array down by one slot (queue[1] moves to queue[0], queue[2] moves to queue[1], and so on) or just use a pointer to keep track of where the front of the queue now is. Shifting the whole array could take way too much time and energy, depending on how large your queue is, since you'll have to move every single element any time you want to take something out. It's a simpler and faster solution to just update your front pointer to reference each time and be done with it.

Using an array means you could look anywhere in the queue if you really wanted to, but…don't. If you promise in your code that you're using a queue, you can't just jump around anywhere you want in the array, because other coders won't be able to understand your work. Just like in real life, if you make a promise that you're going to do something, you better be ready to follow through.

(Either that or refactor like mad.)

If you decide to implement a queue using a linked list, you'll want to use a singly-linked list, where each node connects to the next node in the list. Unlike arrays, linked lists let you spread the elements throughout your computer's memory, making them more flexible for adding and removing elements. Plus, linked lists already have a front and a back built-in, making the "never access the middle" honor code easy to enforce because…it's hard to reach the middle elements.

 

Deques

Sometimes you can mix your queues if you really need to be able to add and remove elements from both the beginning and the end of the list. When that happens, computer scientists say, "Tough," and make you implement both a stack and a queue on the exact same data.

…You didn't believe us, did you? Good, because that's a waste of space. Instead, you can just implement the computer science equivalent of an accordion: a double ended queue (shortened to deque). Now you can do everything except access those middle elements whenever you want.

Eh, what can you do?

Deques can be queues, stacks, or some mix of both depending on how you use them. If you limit the deque to only insert/delete from the top (front), you've got a stack on your hands. If the deque inserts at the front but deletes at the back, you have a queue.

If the deque inserts at the back and deletes in the front, you have…a very confused programmer trying to implement a queue (probably while sleep deprived).

(Source 1, Source 2)