Estructuras de datos: pila

En programación, tenemos que trabajar con montones, montones de datos. Por lo tanto, necesitamos almacenar y organizar los datos de manera eficiente. Aquí es cuando las estructuras de datos son útiles. Podemos utilizar estructuras de datos para almacenar, organizar, procesar y recuperar datos. Las estructuras de datos se pueden dividir en 2 categorías dependiendo de cómo se organicen los datos.

En este artículo, voy a hablar sobre estructuras lineales ( pilas ). En comparación con las estructuras no lineales, los conceptos detrás de las estructuras lineales son relativamente más fáciles de comprender. Algunos ejemplos de tales estructuras lineales son Stack, Queues, Deques y Lists. Revisaremos cada una de estas estructuras de datos una por una. Se puede pensar que estas estructuras lineales tienen 2 extremos. (frontal y posterior | izquierda y derecha | superior e inferior) Algunas estructuras lineales permiten la inserción o extracción de elementos en un solo extremo, mientras que algunas estructuras lo permiten en cualquier extremo.

1. pilas

• Básicamente, una pila es una colección ordenada de elementos donde la inserción y la eliminación de elementos se realizan en el mismo extremo. Este extremo se conoce comúnmente como el “Top”. Además, el extremo, opuesto a la parte superior, se conoce como "Inferior".
• Además, los elementos más nuevos están cerca de la parte superior, mientras que los más antiguos están cerca de la parte inferior. Por lo tanto, el orden de eliminación de elementos de la pila será el inverso al orden de inserción de elementos en la pila.
• Ahora que tenemos una buena comprensión del comportamiento de una pila, echemos un vistazo a algunas operaciones importantes relacionadas con la estructura de datos de la pila.
• push (elemento): el método push se utiliza para insertar un elemento en la parte superior de la pila.
• pop (): el método pop se usa para eliminar la parte superior: la mayoría de los elementos de la pila
• peek () — El método Peek se utiliza para ver el elemento superior actual de la pila.
• tamaño () — Devuelve el número de elementos que están presentes en la pila
• is_empty () — Este método es útil para verificar si la pila está vacía o no
• Tenga en cuenta que aquí, el final de la lista se considera la parte superior de la pila. (Complejidad de tiempo — O(1)) Podemos considerar que el comienzo de la lista es la parte superior de la pila, sin embargo, no sería muy eficiente ya que la complejidad de tiempo sería O(n) cuando presionamos o extraemos elementos.
• Cuando consideramos que el final de la lista es la parte superior de la pila


• Ahora que sabemos cómo implementar una pila, echemos un vistazo a algunos escenarios donde el uso de la estructura de datos de la pila se vuelve vital.
• Conversiones del sistema numérico
• Antes que nada, veamos cómo podemos convertir un número decimal a binario usando una pila.

• Ahora ampliemos el algoritmo anterior para convertir un número decimal a cualquier sistema numérico entre 2 y 16.


Casi todos los lenguajes de programación utilizan paréntesis en su sintaxis. Por lo tanto, si no usamos los paréntesis de manera equilibrada, podría ocurrir un error de sintaxis.

• En la primera etapa de este problema, solo consideraré un tipo de paréntesis, digamos (). Lo que tenemos que comprobar es si el conjunto de paréntesis está equilibrado o no. Si está equilibrado, deberíamos devolver verdadero, de lo contrario, falso.
• ( ) — equilibrado | ( ( ) ) — equilibrado | ( ( ( )( ) ) ) — equilibrado
• ( ( ) no equilibrado | ( ) ( ) ( — no equilibrado | ( ( ( ) ) ( ) — no equilibrado

• ( [ ] ) — equilibrado | ( ( ) { } ) — equilibrado | ( ( [ { } [ ] ] ) ) — equilibrado
• ( ( ) no equilibrado | ( ) { } ]— no equilibrado | ( ( { } [ [ ) — no equilibrado


3. Invierta una cadena usando una pila



4. Infijo | Notación de postfijo y prefijo

En informática, tenemos que lidiar con muchas expresiones aritméticas. Una expresión consta de operadores (+, -, *, / etc.), operandos (A, B, c, d, 1, 2,… ) y símbolos como paréntesis.

• Notación infija: en esta notación, el operador se coloca entre los operandos. (<operando> <operador> <operando>)
• Si la expresión consta de un solo operador (ej: 2 + 3, 4 * 6) podemos resolver la expresión directamente. Sin embargo, si la expresión tiene más de un operador, no podemos resolverla directamente debido a la ambigüedad de la expresión. Considere esta expresión 1 + 4 * 5. Si primero hacemos la suma obtenemos la respuesta como [ ( 1 + 4 ) * 5 ] = 25 y si hacemos primero la multiplicación obtenemos la respuesta como [1 + (4 * 5 )] = 21. Como puede ver, hay cierta ambigüedad en esta notación. Por lo tanto, para resolver esto usamos algo llamado "precedencia de operadores". De acuerdo con la precedencia del operador, la multiplicación debe hacerse antes de la suma. Entonces la respuesta correcta debería ser 21, no 25.
• Básicamente, para resolver una expresión que está escrita en notación infija, debemos seguir un conjunto de reglas, así como también debemos agregar paréntesis. Entonces, esta notación podría tomar más memoria mientras se resuelve. Entonces, para superar estos desafíos, los científicos han ideado otras dos notaciones, prefijo y posfijo.
• En la notación de prefijos, el operador se coloca antes de los operandos (<operador><operando> <operando>) , mientras que en la notación de sufijos el operador se coloca después de los operandos. (<operando> <operando><operador>)
• En comparación con la notación infija, las otras dos notaciones son bastante difíciles de leer y comprender para un ser humano. Sin embargo, dado que estas dos notaciones no tienen símbolos adicionales, como corchetes, y no contienen ninguna ambigüedad, las computadoras pueden leer fácilmente las expresiones escritas en estos 2 formatos.


• Evaluación de una expresión con sufijo: Cuando tenemos que evaluar una expresión con sufijo, debemos comenzar a escanear desde la izquierda hasta que encontremos un operador. Una vez que encontramos un operador, tenemos que realizar la operación algebraica relevante en los primeros 2 operandos a la izquierda del operador.

• En primer lugar, debemos eliminar todos los espacios en nuestra entrada. Por lo tanto, necesitamos usar el método de división. Luego necesitamos escanear nuestra expresión de izquierda a derecha. Si encontramos un número, tenemos que empujarlo a la pila. Si encontramos un operador, tenemos que sacar 2 de los elementos superiores de nuestra pila. Luego tenemos que llamar a nuestra función auxiliar para hacer la operación aritmética. Después de eso, empujaremos el resultado a la pila. Una vez que hayamos terminado con el escaneo, devolveremos lo que queda en nuestra pila, que es la respuesta para la expresión postfija evaluada.


• Ahora veamos cómo podemos convertir una expresión en formato infijo a postfijo usando Python.