What are stacks and how to use them (Stack)

A STACK is a collection of elements used to organize and manipulate items in a specific order.

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

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 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 often used, as it is very efficient for 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 reverse, so it is foreseeable that we will need the elements in reverse order.

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

I like to illustrate the use of a stack with the example of disassembling a machine. You remove screws and store them in order. When you reassemble it, you will need the first screw you removed first. That shows the purpose of a stack.

In computing, for example, we have the case of the memory STACK. Each time one function calls another, it passes parameters on a Stack. When the functions finish, the parameters are needed in the reverse order they were placed.

Stack example

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> pila = new Stack<int>();

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

        int elementoSuperior = pila.Pop(); // Returns 15
        Console.WriteLine(elementoSuperior);
    }
}

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

int main()
{
    stack<int> pila;

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

    int elementoSuperior = pila.top(); // Returns 15
    pila.pop();

    cout << elementoSuperior << endl;
    return 0;
}

class Pila {
    constructor() {
        this.pila = [];
    }

    push(elemento) {
        this.pila.push(elemento);
    }

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

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

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

const pila = new Pila();
pila.push(5);
pila.push(10);
pila.push(15);

const elementoSuperior = pila.pop(); // Returns 15
console.log(elementoSuperior);

class Pila:
    def __init__(self):
        self.pila = []

    def push(self, elemento):
        self.pila.append(elemento)

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

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

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

pila = Pila()
pila.push(5)
pila.push(10)
pila.push(15)

elemento_superior = pila.pop() # Returns 15
print(elemento_superior)

Efficiency

The efficiency of a STACK will depend on how it is implemented internally (but let’s assume it’s implemented “well”).

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

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

The rest of the operations don’t make sense since you can only access the element at the top of the STACK. You cannot access elements in intermediate positions without popping all the elements above them.