Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Like
12Likes
Dislike

Data Structures for Pre-College Programmers: Stacks and Queues

By frob | Published Apr 01 2013 03:51 PM in General Programming
Peer Reviewed by (Michael Tanczos, jbadams, Casey Hardman)

beginner stack queue data structure data

Introduction


Many of the beginners on the site are pre-college students. Often beginners will learn by reading tutorials on the Internet, copying code from books, and trying out things that they find interesting.

This article is part of a series that focuses on giving pre-college developers the basics they need to understand data structures.

The previous article was Arrays, Dynamic Arrays, and Linked Lists.

This article is about stacks and queues.

The Stack


Imagine you have a bunch of papers. You push one paper onto the stack. Now you can only easily access the top paper. You push another paper onto the stack. The earlier paper is now covered and inaccessible, and the new paper is available for use. When you are done with the top paper you can remove it from the stack, exposing the one beneath.

That is the idea of a stack.

A stack is a LIFO structure. That stands for Last In First Out. When you add and remove from a stack, the last one that you put in will be the first one you get out.

There are really only three operations needed for a stack: Push, Pop, and Top. Push will add an object to the stack. Pop will remove an object from the stack. Top will give you the last-most object on the stack.

These containers are part of the standard libraries of most languages. In C++ it is called a stack. In Java and C# it is a Stack. (Yes, the only difference is the capitalization of the first letter.)

Under the hood, a stack is often implemented as a dynamic array. If you recall from that data structure, the fastest operations on a dynamic array are to add and remove elements from the end. Since a stack is always adding and removing from the end, it is usually extremely fast to push and pop objects onto a stack.

The Queue


Imagine you are waiting in line for something. The first person in the line gets served, then leaves. The second person in line gets served, then leaves. More people walk over to the line and stand at the end of it.

That is the idea of a queue.

Attached Image: queue.PNG

A queue is a FIFO structure. That stands for First In First Out. When you add and remove from a queue, the first one you put in will be the first one you get out.

A queue only needs a few operations: Push_Back, Pop_Front, Front, and Back. Push_Back will add to the end of the queue. Pop_Front will remove from the front of the queue. Front and Back will let you examine the two ends of a queue.

Programmers will frequently need to add and remove from both ends of a queue. This is called a double ended queue, or deque. In this case they add two other operations, Push_Front and Pop_Back.

Again, these containers are included in most major languages. In C++ it is a queue and a deque. Java specifies interfaces for both queue and deque, then relies on a LinkedList for the implementation. C# provides a Queue class, but not a Deque class.

Internally, a queue and a double-ended queue can be somewhat complex. Since objects can come and go at either end, the internal container needs to be able to grow and shrink at the beginning and at the end.

Many implementations will rely on multiple pages of memory. When either end grows beyond the current page, an extra page is added. Similarly a page is removed when it is no longer needed. Java follows a different route; it requires a little additional memory using a linked list rather than pages of memory, but it works for the language.

Priority Queue


There is a very common variation on the queue. A priority queue is very similar to a basic queue. You push things on to the end, and you pop things off from the front.

The difference is that you can give priority to certain items in the queue. All of the most important items are processed in a FIFO order. Then the next priority items are processed in a FIFO order. Repeat until the lowest priority items are handled in FIFO order. If you add a new item that is higher priority than the rest of the queue, it will immediately jump to the head of the line.

In C++ this is called a priority_queue. In Java it is a PriorityQueue. C# does not include a priority queue in the standard library.

Priority queues are not just useful in getting yourself to the front of the line on the corporate printer. Priority queues can be used to easily implement algorithms like the A-star searching routine. The most likely results can be given a higher priority over the less likely results. You could choose to build your own system for sorting and organizing your A-star search, but it will be much easier to just use the built-in priority queue.

Conclusion


Stacks and queues and deques and priority queues can be implemented in terms of other data structures. They are not fundamental data structures, but they are frequently used.

They are very efficient when you need to work only with the endpoints of your data, and don’t really care what is in the middle.

NEXT: Trees and Heaps

Updates:
2013-04-01 Typo



License


GDOL (Gamedev.net Open License)




Comments

Just pointing a typo: "In C++ this is called a prioirty_queue."

 

The article itself seems reasonable, although I'm a bit mixed about the amount of depth even when considering the possible audience. A section for recommended reads at the bottom?

Some example situations to show why these structure are useful might be beneficial.

Just pointing a typo: "In C++ this is called a prioirty_queue."

 

Thanks, typo fixed.  Automatic spell checking does't work to well on names like that.  :-/

I liked the article, but I wanted to note on a minor mistake:


"Under the hood, a stack often implemented as a dynamic array."

 

should be:

 

"Under the hood, a stack is often implemented as a dynamic array."

I wouldn't say a stack is not a fundamental data structure since it's the basis for call and return of functions and recursion.

I wouldn't say a stack is not a fundamental data structure since it's the basis for call and return of functions and recursion.

Perhaps a different definition of fundamental.

That isn't the definition I meant.

Yes, it is frequently used. It is something that should be understood. In that definition of fundamental you are correct.

In science and mathematics, fundamental has another meaning. Something is fundamental when it cannot be reduced into simpler parts.

For example, a fundamental frequency is the lowest frequency that contains all the harmonic frequencies. In chemistry atoms are fundamental because they cannot be broken down; molecules are not fundamental because they can be broken down into two or more atoms. In particle physics an electron is a fundamental particle because it cannot be broken down, but neutrons and protons are not because they can be broken down into quarks. The major trig functions can all be broken down into variations on the sin function, which is fundamental.

A stack can be broken down: it is any linear structure that follows a specific access pattern.

Because it can be broken down, stack is not fundamental.

Hopefully that doesn't cause too much confusion. :-)
This article is very clear. Thank you so much for that. Words like stack and queue scared me. Now that I have the concept, I can talk with the pros. Haha. I do need to read it again to get it to soak in. Thanks!

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS