Data Structures – Queues

Data structures is an important concept in Computer Science. In Computer Science, one of the fundamental structures is queues. Queues are an abstraction of a real life thing; the idea is that the first element is the first element out (FIFO). Every other element is added to the end of the queue. Now, let’s break down into the methods of the abstraction.

 

Queue Abstraction Implementation

The core methods of the abstract data structure are important. Let’s list them.

  • Enqueue – adds an element to the end of the queue
  • Dequeue – removes an element from the front of the queue
  • isEmpty – determines if the queue is empty
  • size – checks the size of the queue
  • peek – checks the top element at the front of the queue

Now, let’s break down the idea into code.

 

Queue Code Breakdown

Here’s the example code for the queue implementation.

Now, let’s break this down into pieces, starting with each method. The first method is the enqueue method; this method adds an element to the end of the queue. In our implementation, we use an array to represent the queue; doing this we can make use of the array methods. In our case, we use the push, pop, and reverse methods to emulate a queue.

During an enqueue, we are pushing into the array like we would a stack. The real difference that sets this implementation apart from a stack is the dequeue method. During dequeue we are reversing the array, making the front the back and removing the last element. This is because, stacks push all the elements on top of one another, in a queue the first element is the first out, so it would be at the bottom of the stack. By reversing it’s now at the top, allowing us to use pop and get the first element in the queue. This is why peek is very similar to dequeue.

The other methods in the queue implementation are there to check important information when we might use queues. But, when might we use queues in our application anyway?

 

Using Queues

Queues are useful when you need to provide that level of abstraction in your application. Many applications are built to emulate certain aspects of real life in some way. For example, if you need to introduce a ticketing system in your application, a queue is the best way. Why? Because the first person to order a ticket should obviously be the first one processed; a queue works best for this. Another example would be a notification system in your browser; as notifications come in the user should get the first notification in the set rather than most recent one first. These are somethings you might have to implement into your game as well. These are just some rudimentary examples, but there are more.

As you use queues and data structures in your applications more often, you’ll see more uses for them. Each new data structure adds another tool to your toolset, allowing you to create more applications and games that you want. There are even more types of queues that go beyond this basic implementation. Take some time to learn them and I hope this post encourages you to improve your development skills.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s