Stack data structure

Stack is the most popular and historical data structure. A list of items arranged one on top of others. Stack data structure popularly used to maintain program memory stack. It follows the last-in-first-out order. Let’s consider a stack of discs as shown in the below picture.

As shown in this diagram, only the top node can be removed at once.

Stack of items on a rod.

In programming, We can implement stacks using either arrays or linked lists data structures. First of all, let’s try to take an example of stack and understand its implementation using arrays.

Example:
Input = {5, 10, 8, 3, 2, 9}
Top: 9

Stacks supports basic operations, those are push and pop. Let’s see these operations using arrays.

Push Operation

Initially top starts with index 0, If an element with value ‘5’ wants to push into an array it inserts at the top position then top moves to its next index, as shown in the picture.

Insert 5 at top and move top to next index.

After pushing 10 into the stack as shown in the picture top moves to its next position.

Push 10 at top and move top to next index.

Now it pushes ‘8’ to the stack as shown in the picture. Here top moves to position 3.

Push 8 at top and move top to next index.

Similarly, element 3 pushed into the stack and top moves to 4.

Push 3 at top and move top to next index.

Value 2 pushes into stack and top is now at index 5 as shown in the picture.

Push 2 at top and move top to its next index.

Finally push 9 at top and move top to its next index as shown in the picture.

Stack cannot go beyond its capacity, as here its capacity is 6.

Push 9 at top and move top to its next index.
// Simple snippet to push logic.
if(top < capacity)
{
    stack_arr[top] = input;
    top++
}

Pop, In contrast while popping an element from the stack it first top moves to its previous position. Check below two-line snippet for how pop works.

// Simple snippet for pop logic
if(top > 0)
{
    top_elm = stack_arr[top];
    top--;
}
return top_elm;

Both these operations are of O(1) time complexity. The final code is as shown below.

Complexity:
Push: O(1),
Pop: O(1)

You can find some interesting problems at http://rjp.b44.myftpupload.com/tag/stack/

This is all about stack and its operations. If you have any approach which helps readers to understand better please write it in the comments below. Cheers!.

Advertisements