[ Data structures - Part 2 ] Stack

Stacks

---

Last time, we learnt about vectors. This time we're gonna learn about stacks. Stacks are extremely important in understanding how your code runs. hIt's used both for storing y our local variables and for making sure your functions run in the right order. Recursive method heavily rely on stacks.

The stack ADT

---

Stacks asr ad ADTs this basically says it's a data type with certain operations you can perform on it. But ADTs does not have any specific implementation, you can implement it any way you like.

Supported operations

---

The following operations are typical for stacks

• Push
• Pushes and element on the top of a stack
• Pop
• Removes the top element of the stack
• Note that this doesn't return the top element.
• Top
• Returns the top element of the stack.

An example

---

Imagine you have a stack of plates. The plates are all of the same plates, but some have different motives. It is your jobs to sort them into new stacks where depending on the motives of the plates. So you look at the top plate ( top() ) and decide which of the sorted stacks it belongs onto. When you have decided it belongs in stack 1 ( as an example ), you remove it from the stack ( pop() ) and put it onto stack 1 ( push() ). You look at the next one ( top() ) it belongs in stack 2 so you remove it ( pop() ) from the unsorted stack and place it on stack 2 ( push() ).

This goes on and on. Always looking ( top() ) and remove ( pop() ) the top element and placing it ( push() ) on the top of the correct stack. You can't look at or remove any of the elements below the top one, so you're always working with the top one. This is how a stack works. Always insert and remove at the top. The elements below the top are irrelevant until they are the top elements themselves.

Usage

---

Stacks have a lot of usage in the world of computers. Every time you write a function, you are dealing with stack. Every time you do an if or loop ( for, while ) you are dealing with a stack. So let's take a look at how that works.


void Function()
{
    int value = 5;
    int someValue = 19375;


    if ( value == 5 )
    {
        int otherValue = 3;]
    }

    while ( value !=10 )
    {
        int someValue = value;

        int something1 = 0;
        int something2 = 0;

       value = someValue + 1;
    }
}


Here's what happen when you enter Function().

Step 1:

---

The variable value and someValue will be added to the stack.

The stack is now

• someValue
• value

Step 2:

---

We enter a new block { so we add a mark to show this

The stack is now

• {
• someValue
• value

Step 3:

---

We find a new variable, otherValue, and add it t the stack

The stack is now

• otherValue
• { 
• someValue
• value

Step 4:

---

So now we are leaving the current block. The current block was the one that started in step 2.
So now we need to delete the variables we added in the current block ( they are now out of scope )

We do this by doing the following look at the top element :

• The element is not a {
• Pop it and go check all the next element.
• If the element is a {
• We have deleted ( popped ) all elements that belonged to this scope so we pop the { and return. Now we have deleted all the elements and can continue.

 So let's do this step by step

• } - The end of the scope, pop it and continue
  
• otherValue1 - A variable in the scope. Pop it and continue
  
• { - The { signaling the beginning of the scope. Pop it and return
  
• someValue
• value

 In the end, our stack looks like this :

• someValue
• value

Step 5:

---

Now we have come to the loop in our function. Here we declare the variable someValue. Wait? Isn't that what the other variable is called? Yes, it is. But it's in a different scope so the compiler knows that when you someValue within this scope, you are referring to the variable declared in this scope. Let's add the { and someValue to the stack.

This is what we end up with :

• }
• something2 
• something1
• someValue - The one in the loop, value is same as value
• {
• someValue - The original one, declared at the top. Its value is 19375
• value

Step 6:

---

The loop goes out of scope, and someValue is deleted. Only to be recreated as we re-enter the loop. This time value is one more than last time.

The order in which the items will be deleted is the opposite of the order they were inserted. So : something2, then something1 and finally someValue.

Next we go to 5, value will be one more, but otherwise exactly the same will happen all the way until value is 10, in which case we continue to the last step.

Step 7:

---

Now the entire function is done. All that is left of the stack is

• someValue
• value

So we pop of the top variable, someValue. Now we're left with the first variable we created, value. We pop that of too. Now the entire stack is empty and we return from the function.

Conclusion

---

Stacks are limited in what they can do. But they are also very easy to implement and understand. They are also extremely useful in some cases ( as we have just seen. )

I hope to update this post soon with more information about the implementation of the object in STL, std::stack.

---

Feel free to comment if you have anything to say or ask questions if anything is unclear. I always appreciate getting comments.

For a full list of my tutorials / posts, click here.