Why I made a stack and queue plugin

3
skymen's avatar
skymen
  • 16 May, 2018
  • 1,233 words
  • ~5-8 mins
  • 1,602 visits
  • 1 favourites

A few months ago, I created two plugins: Stack and Queue.

I published them on the new addon exchange platform published by Scirra at about the same time as when I had finished them.

Now why did I do this?

The short answer

Because it's cool and I was bored. I was in the middle of a 3h math class and I really had nothing else to do.

The Long (and slightly more interesting) answer

Because Construct 2 lacks data structures.

Data structures is an object type for storing and managing data. Yes the name was pretty self explanatory. The most common data structures are lists. Basically store every bit of data next to each other and access them using an ID.

In Javascript, another very used data structure is dictionnaries. Instead of linking data to IDs you link them to words.

As you may know, these are the two data structures that we can use inside Construct 2

JSON isn't a data structure. JSON is a string representation of a Javascript Object. JSON format is really useful because it allows one to store complex data trees inside a single string and decode it when needed. But at it's core, when decoded, it's just arrays in dictionnaries and dictionnaries in arrays.

Let's talk about C#

C# is another language that is very commonly used in lots of domains in the industry. As game developers you may know that it's used as Unity's main programming language.

C# is similar to javascript because it shares some similarities in its syntax and in its execution. It's, like Javascript and Python, an interpreted language.

The main difference between C# and Javascript is that C# is strongly typed while Javascript is not.

What this means basically is that in C# each variable needs to hold a specific type, and if compared to or operated with another type of variable, it needs to be casted to the right type (basically translated for the purpose of said comparison or operation)

Concrete example

In Javascript, I can write:

	if(1 == '1'){
		var a = 1;
		var b = 2;
		console.log(a/b);
	}

And it will print '0.5' in the console

In C# however, I cannot do this.

1 is of type int and '1' is of type string. So the operator == would just throw an error, telling me that I cannot compare the two.

a is of type int and b is of type int. So C# assumes that any operation that uses a and b will be of type int. So it would print '0' instead of '0.5'.

If I wanted to have a float result, I'd need to cast one of the vars to the float type by doing (float)a/b.

Why does this even matter?

Well as you can see C# gives a lot more importance to variable types than Javascript. JS allows you to store an array on a variable that was storing a float. That would never ever happen in C#.

What that means is that C# also gives access to a lot of different data structures, you saw it coming, including Stacks and Queues.

Ok, so what are they?

A stack is a data structure of type LIFO (Last In First Out).

You can litterally figure it by a physical stack. The last element you added to the structure is the first one that you'll be able to access.

As a comparison, lists aren't of any type. In a list, you can usually access any element of the list at any point. In a stack you can only access the one at the top. If you want to access the remaining elements, you need to remove the first element.

Not necessarily, I'll talk about that in a bit.

A queue is very similar. It's a FIFO data structure (First In First Out)

Again, like a queue, when you add an element to a queue, you need to remove every element you added before it before being able to access that element. Like a regular queue (understand a waiting line by that).

What are they useful for?

Stacks and queues have lots of applications, but all of them revolve around a common aspect: They don't need more than what these structures offer.

For exemple, an Undo Redo system would use two stacks. One for Undo and one for Redo, as I showed in this video:

Subscribe to Construct videos now

Another application of stacks would be in interpretation algorithm. If I want to make a program that reads a mathematical string and computes it, I need a stack to store the parenthesis to know the depth in the calculus I am in.

Queues also have some great applications, but the most common one is actually queueing actions. If you've got an AI and you want that AI to do a set of actions, you're gonna add them to a queue, and do each action one by one, and remove them from the queue when they're finished and do the next one.

Yes. You can. That's why Javascript has no reason to support them by default. In fact my implementation of both Queue and Stack are just lists but with less features.

As I said. Sometimes you just need the few features stacks offer. Why bother using a structure that allows for much more when you'll never need most of it.

In those cases, you end up writing things like "Get element at position 0 and remove element at position 0" when with a queue, you'd write "Dequeue an element". Having a simpler structure that meets your exact needs as pretty neat to work with. That's why having lots of data structures is great.

Other data structures that may be useful

Stacks and queues are really simple, but they're far from being the only data structures! Another extremely useful structure is the binary tree.

I'm not gonna explain what it is in detail what that it, a quick research should be enough to get what it looks like.

Again, it's techincally possible to store a binary tree inside a list, but it's a lot less practical that with an actual binary tree object.

End card

Anyway. I said that Construct 2 lacked data structures. This is not particularly a bad thing. That's equivalent to saying that Javascript lacks data structures. You can always simulate them using lists and dictionnaries. The difference is that Construct 2 is not as open as Javascript. You can simulate a stack or a queue using the array plugin, but it's boring. It's a pain to work with. Even more than with actual Javascript.

Construct 2 is made to offer a simple and easy to understand workflow. Overcrowding your actions with weird operations on arrays makes it harder to understand at first glance.

So having a plugin where you replace the whole process of "Get element at 0 and remove at 0" by a single "Dequeue" makes the whole event sheet feel a lot nicer to read.

In the end it doesn't change anything, it's all about User Experience.

The plugins

If you want to take a look at the plugins I made, here they are.

For Construct 2

Stack:

construct.net/construct-2/addons/79/stack

Queue:

construct.net/construct-2/addons/3/queue

For Construct 3

Stack:

construct.net/make-games/addons/80/stack

Queue:

construct.net/make-games/addons/29/queue

Subscribe

Get emailed when there are new posts!

  • 4 Comments

  • Order by
Want to leave a comment? Login or Register an account!
  • Awesome, the AI example for queue is pretty neat, thanks for the plugins.

  • Arrays have a "Push back/front" and "Pop back/front" action that allows to handle LIFO/FIFO in a quick way too (unless I'm missing something).

    Nevertheless, making stuff when you're bored is always nice and writing an article about it gives even more insight, thanks for both.