Dungeon Coder

 

Queue is for Queueen

Introducing Queues by Way of Linked Lists

As if grasping linked lists wasn't enough, now we've got to take what we've learned about linked lists and fit them into another data structure called a Queue (pronounced "q").

A queue is often an implementation of a linked list with one very important restriction: it is designed as a First In, First Out structure. That is, the first node in a queue will be treated like the first person waiting in line at the entrance to the most popular dungeon. If you were the first person to arrive, you'd be the first person to get in. That's exactly how queues work.

Take a look at the following code, run it, and try and make sense of it. We'll resume discussion afterward.

The main difference you'll notice between regular linked lists and queues is the way nodes are removed. Strictly speaking, a linked list could be designed to remove nodes from any location in the list. A queue, however, must always remove (deQueue) the first node in the list. When nodes are added, they are added to the end (enQueued). Also note that we end up returning the deQueued node. The return keyword just enables us to take the returned thing and do something with it. In our case, we took the returned (deQueued) node, stored it as a new node, and then enQueued it back into our Queue. Notice that it was not placed back into the front of the list, but rather to the back of the list. "Move your feet, lose your seat", as they say. If you get out of line, you have to go all the way to the back of the line.

Assignment:

  1. enQueue at least 3 more nodes.
  2. Call the printQueue function to verify that your nodes have been enQueued.
  3. deQueue at least 3 nodes.
  4. Construct a new Queue object called newQueue.
  5. Write a loop that asks a user to enter 5 numbers. Your loop should ask them to enter a number, enQueue that number into the newQueue object, and repeat 4 more times. Call printQueue on newQueue to verify that your loop works.

Join the Dungeon Crawl: A place for programmers to ponder, partake, and peruse postulations pertaining to programming, politics, potions, and pizza.

If you subscribe on Patreon, you will be granted access to the Dojo, a growing collection of quality computer science classes created and actively mantained and frequented by the Dungeon Master!

Become a Patron!

Glossary

Contact: dungeon_master@dungeoncoder.com