¿Cuál es la eficiencia de tiempo de las operaciones push(), pop(), isEmpty() y peek() de Stacks?

Stack es una estructura de datos lineal que sigue el orden LIFO (último en entrar, primero en salir), es decir, los datos se ingresan desde un extremo y mientras se eliminan, se eliminarán del mismo extremo. 

Las pocas operaciones más realizadas en una pila son:

1. empujar()
2. estallido()
3. esta vacio()
4. ojeada()

Ahora comprobemos la eficiencia temporal de las operaciones:

1. empujar():

Esta función se llama para insertar un nuevo elemento en la pila.

Sintaxis:

stack.push(valor)

Complejidad de tiempo: O(1)

Motivo: cuando se llama a la función, se ingresa un nuevo elemento en la pila y la parte superior se cambia para apuntar al elemento recién ingresado. Además, se crea un vínculo entre el puntero superior nuevo y el anterior. Estas son operaciones de tiempo constante.

2. tirar()

Esta función se llama para eliminar el elemento superior de la pila.

Sintaxis:

pila.pop() 

Complejidad de tiempo: O(1)

Motivo: en esta operación, el elemento superior se elimina y el puntero que apuntaba al elemento superior ahora apunta al que está justo debajo. Las operaciones realizadas en este caso se realizan todas en tiempo constante. 

3. estáVacío():

Esta función se llama para verificar si la pila está vacía o no.

Sintaxis:

pila.estáVacío() 

Complejidad de tiempo: O(1)

4. mirar():

Esta función se llama para obtener el valor del elemento superior de la pila.

Sintaxis:

pila.mirar()

Complejidad de tiempo: O(1)

Motivo: esta función solo accede al puntero que apunta al elemento superior y obtiene el valor almacenado allí.

Para más detalles, consulte:
Diseño y Análisis de Algoritmos .