How different data structures can be used in game coding: List, Queue, and Stack

I'm sure most game creators are familiar with an array to store data, the problem with an array is once the size is set, it becomes much more difficult to manage. There are times when you want to sort, add, or remove data. The best way to do this is using different types of Data Structures. I'm going to focus on Lists, Queues, and Stacks though there are several others.
*This article assumes you have a basic understanding of Generic types.

Some sample code to learn and play around with. hopefully the comments are useful:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class DataStructuresScript : MonoBehaviour
{
    string[] arrayString = new string[] { "Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten" };
    List<string> listString = new List<string>();
    Queue<string> queueString = new Queue<string>();
    Stack<string> stackString = new Stack<string>();

    string trueTestString = "Zero";
    string falseTestString = "zero";                    // Note data must be exact to mach

    // Use this for initialization
    void Start ()
    {
        LoadData();
        TheList();
        TheQueue();
        TheStack();
    }
 
    void LoadData()
    {
        for (int i = 0; i < arrayString.Length; i++)
        {
            listString.Add(arrayString[i]);
            queueString.Enqueue(arrayString[i]);
            stackString.Push(arrayString[i]);
        }
    }

    void TheList()
    {
        print("List:");
        // Different ways to add data
        listString.Add("Eleven");
        listString.Insert(12, "Twelve");
        // Different ways to see/retreave data
        print(listString[1]);                           // Can be indexed like an array
        print(listString.Contains(trueTestString));
        print(listString.Contains(falseTestString));
        // Different ways to remove data
        listString.Remove("One");
        listString.RemoveAt(1);                         // position 1 is now 'two' meaning 'two' is now removed. (This is like indexing in an array)
        //
        foreach (string item in listString)
        {
            print(item);
        }
        // A list can also be returned like an array
        for (int i = 0; i < listString.Count; i++)
        {
            print(listString[i]);
        }
    }

    void TheQueue()
    {
        print("Queue:");
        // Different ways to add data
        queueString.Enqueue("Eleven");
        // Different ways to see/retreave data
        print(queueString.Contains(trueTestString));
        print(queueString.Contains(falseTestString));
        print(queueString.Peek());                      // Returns the first item enqueued, 'Zero'
        // Different ways to remove data
        queueString.Dequeue();                          // Removes the first item enqueued, 'Zero'
        //
        foreach (string item in queueString)
        {
            print(item);
        }
    }

    void TheStack()
    {
        print("Stack:");
        // Different ways to add data
        stackString.Push("Eleven");
        // Different ways to see/retreave data
        print(stackString.Contains(trueTestString));
        print(stackString.Contains(falseTestString));
        print(stackString.Peek());                      // Returns the last item pushed onto the stack, 'Eleven'
        // Different ways to remove data
        print(stackString.Pop());                       // Returns AND Removes the last item pushed onto the stack, 'Eleven'
        //
        foreach (string item in stackString)
        {
            print(item);
        }
    }
}

The List:
Think of a List like a grocery list on a piece of paper, you can add things anywhere on that page and cross/check things off regardless of where they are on the page.
A List is useful when dealing with things like an inventory or keeping track of enemies or something that is being changed all the time and when order does not matter. This is my go to data structure; easy to manage and easy to return information. More Info

The Queue:
Think of a Queue like a waiting line, in fact many countries often refer to "waiting in a line" as "waiting in a queue". This means it's first come, fist served. Or better known as First In, First Out.
This is great for puzzle games or code commands where things need to be checked/done in an order before the rest of the things in the queue are checked/done.  More Info

The Stack:
Think of a Stack like a stack of books on a desk. You can only take/use the top book and additional books are placed on top of the top book. This is known as Last In, First Out.
The idea of using a stack is that you only care about the last item pushed on the stack or the top book. Once the top book is dealt with then the next top is dealt with and so on. This is great for puzzle games that have the player repeat things back. More Info

Bonus info:
A really useful feature of a List, Queue, and Stack is an array can be easily created from them using myQueue.ToArray(). I use this when I want a save game data or create a snapshot to use later.

More robust data structures can be created and used such as a LinkedList or Hashtable or Dictionary  but more code maintenance is usually needed and at that point it is better to use the Unity asset store because developers have made some really awesome data structures. ...not that you shouldn't try if you want to though! Even More Info

Comments

Post a Comment

Popular posts from this blog

How to create slowly revealed text in a Unity 3d game

Adding randomness to your game through code using Unity 3d