2.5 Trees, Stacks, Queues and More!

A Data Structure is just like any type of Structure in reality which is modelled in a computer with applications of various Programming Paradigms to store data in an efficient manner.

That’s why we have data structures like Trees, Stacks and Queues.

Starting with Stacks,

Imagine a stack of trays, where you can easily take the top tray off or put another tray on top, but not much else. A data structure with this metaphor is also called a stack, and it has two operations, push and pop, that stores and removes items respectively.

The property we now get is that the last item we pushed, will be the first one we pop.

We could implement this ourselves:

typedef struct

{

    int *numbers;

    int size;

}

stack;

Now we have a struct stack, with an array of ints called numbers that we can allocate and resize as needed. And it also will have a property called size, since we won’t always have as many items in our stack as its capacity.

A queue would be the opposite of a stack. In a queue, the first item in will be the first item out, like a line of people. We’ll have operations enqueue, which places an element at the end of the list, and dequeue, which takes the first element from the beginning of the list.

With a queue, we need to keep track of a little more information:

typedef struct

{

    int front;

    int *numbers;

    int size;

}

queue;

Here we use an array to store our queue, but now we also need to keep track of where the front of the queue is. Each time we call dequeue, we’ll need to return the item at the index front and then increment it so we get the next item next time. Since we have an array, we can’t easily shift items down, so we’ll use front to keep track of where the front is.

Here’s a quick animation demonstrating Stacks and Queues: https://goo.gl/5nZ4AN .

           

Now You may think that how could these things possibly be of use while programming?

And your question is justifiable, but as we go through various Programming Tasks you’ll see that we would indeed need to use Stacks, Queues and a ton of other Data Structures which You might make up yourself.

Moving on to Trees,

We can have one node point to multiple other nodes, and in the case of this data structure, a tree, we have one node at the top, the root node, that points to other children nodes, like in a family tree. And nodes without children are called leaves.

NOTE: We refer to each point on that tree as a node!

This could be used in multiple ways as well, one of the possible ways is as what we call a Binary Search Tree, which is similar to the Binary Search and Merge Sort Algorithm.

And we can define each node as follows:

typedef struct node

{

    int n;

    struct node *left;

    struct node *right;

}

node;

Exercise

Try to figure out how a Tree represents Binary Search and Merge Sort!