What are stacks and how to use them (Stack)

STACK, or Stack, is a collection of elements that is used to organize and manipulate elements in a specific order.

A STACK is also called Last-In, First-Out (LIFO) structure, because it follows the principle that the last element to be inserted (Last-In) is the first to be removed (First-Out).

Every time a new element is inserted into the STACK, it is placed on top. When an element is removed, the last added element is taken off.

This is achieved through two main operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes and returns the element from the top of the stack.

In addition to these basic operations, other operations can also be performed on a STACK, such as checking if it is empty or accessing the top element without removing it.

There are multiple ways to implement a STACK. Generally, a simple Array is used, as it is very efficient at adding and removing the last element.

Properties

When to Use a Stack

It makes sense to use a STACK when storing elements during a process that we will later need to reverse, so it is predictable that we will need the elements in reverse order.

A STACK is similar to a stack of physical objects, such as a stack of plates, where only the top element can be accessed. For example, you take clothes out of the washing machine and stack them. When you pick them up again, you take them in reverse order.

I like to illustrate the use of a stack when disassembling a machine. You remove screws and keep them organized. When you put it back together, you will need the first screw you removed. That’s the purpose of a stack.

In computer science, for example, we have the case of the memory stack. Every time a function calls another, it passes parameters in a Stack. When the functions end, the parameters are needed in reverse order to the one they were put in.

But that’s not the only example. Whenever you have to save elements throughout a process, which you later need to traverse in reverse, a Stack may be the right fit.

Stack Example in Different Programming Languages

Below are examples of how a stack can be implemented in different programming languages:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        Stack<int> stack = new Stack<int>();

        stack.Push(5);
        stack.Push(10);
        stack.Push(15);

        int topElement = stack.Pop(); // Returns 15
        Console.WriteLine(topElement);
    }
}

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> stack;

    stack.push(5);
    stack.push(10);
    stack.push(15);

    int topElement = stack.top(); // Returns 15
    stack.pop();

    cout << topElement << endl;
    return 0;
}

class Stack {
    constructor() {
        this.stack = [];
    }

    push(element) {
        this.stack.push(element);
    }

    pop() {
        return this.stack.pop();
    }

    peek() {
        return this.stack[this.stack.length - 1];
    }

    isEmpty() {
        return this.stack.length === 0;
    }
}

const stack = new Stack();
stack.push(5);
stack.push(10);
stack.push(15);

const topElement = stack.pop(); // Returns 15
console.log(topElement);

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, element):
        self.stack.append(element)

    def pop(self):
        return self.stack.pop()

    def peek(self):
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0

stack = Stack()
stack.push(5)
stack.push(10)
stack.push(15)

top_element = stack.pop() # Returns 15
print(top_element)

In the above examples, it is shown how to create a stack using the data structures provided by each programming language. Insertion, deletion, and access to the top element of the stack are performed. Conclusions

Efficiency

The efficiency of a STACK will depend on how it has been implemented internally. But, let’s consider that it has been implemented “well”.

Reading and removing elements in a STACK are done in constant time O(1), as the last added element is accessed.

Insertion in a STACK is also efficient, as it is added to the end of the stack in constant time O(1).

The rest of the operations do not make sense since you can only access the element at the top of the STACK. You cannot access elements at intermediate positions without popping all the elements above.