3 Estructuras lineales
¿Qué son estructuras lineales en Python?
Comenzaremos nuestro estudio de las estructuras de datos considerando cuatro conceptos sencillos pero muy poderosos.
Las pilas, las colas, las colas dobles y las listas son ejemplos de colecciones de datos cuyos ítems se ordenan dependiendo de cómo se agregan o eliminan. Una vez se agrega un ítem, éste se mantiene en la misma posición relativa respecto a los otros ítems previos y posteriores a él. Colecciones como éstas se denominan a menudo estructuras de datos lineales.
Se puede pensar que las estructuras lineales tienen dos extremos. A veces, estos extremos se denominan “izquierda” y “derecha” o en algunos casos “frente” y “final”. También se les puede llamar “tope” y “fondo”. Los nombres dados a los extremos no son significativos. Lo que distingue una estructura lineal de otra es la forma en que los ítems se agregan y eliminan, en particular el lugar donde se producen estas adiciones y remociones. Por ejemplo, una estructura podría permitir que se agreguen nuevos ítems en un solo extremo. Algunas estructuras podrían permitir que los elementos se eliminen de cualquiera de los extremos.
Estas variaciones dan lugar a algunas de las estructuras de datos más útiles en ciencias de la computación. Aparecen en muchos algoritmos y pueden ser utilizadas para resolver una variedad de problemas importantes.
¿Qué es una pila?
Una pila (a veces llamada una “pila push-down”) es una colección ordenada de ítems donde la adición de nuevos ítems y la eliminación de ítems existentes siempre tienen lugar en el mismo extremo. Tal extremo se denomina el “tope”. El extremo opuesto se denomina la “base”.
La base de la pila es significativa ya que los ítems almacenados en la pila que están más cerca de la base representan aquellos que han permanecido más tiempo en la pila. El ítem más recientemente agregado es el que está en la posición que será eliminada primero. Este principio de ordenamiento a veces se denomina LIFO: último en entrar, primero en salir (last-in, first-out). Éste brinda un ordenamiento basado en el tiempo de permanencia en la colección. Los ítems más nuevos están cerca al tope y los más viejos están más cerca de la base.
Muchos ejemplos de pilas se producen en situaciones cotidianas. Casi cualquier cafetería tiene una pila de bandejas o platos donde usted toma la o él que esté en el tope, descubriendo una nueva bandeja o plato para el próximo cliente en la línea. Imagine una pila de libros sobre un escritorio (Figura 1). El único libro cuya cubierta es visible es el de arriba. Para acceder a otros en la pila, necesitamos eliminar los que están puestos encima de ellos. La Figura 2 muestra otra pila. Ésta contiene una serie de objetos de datos primitivos de Python.
Una de las ideas más útiles relacionadas con las pilas proviene de la simple observación de los ítems a medida que se agregan y se eliminan. Suponga que usted comienza con un escritorio limpio. Ahora coloque los libros, uno a la vez, encima de otro. Usted está construyendo una pila. Considere lo que sucede cuando comienza a quitar libros. El orden en que se eliminan es exactamente el orden inverso en que fueron colocados. Las pilas tienen una importancia fundamental puesto que pueden usarse para invertir el orden de los ítems. El orden de inserción es el inverso del orden de eliminación. La Figura 3 muestra el objeto pila tal como fue creado y luego, de nuevo, a medida que los ítems son eliminados. Observe el orden de los objetos.
Considerando esta propiedad de orden inverso, tal vez usted pueda pensar en ejemplos de pilas que se producen cuando utiliza su computadora. Por ejemplo, todo navegador web tiene un botón Atrás. A medida que usted navega de una página web a otra, esas páginas se ubican en una pila (en realidad, son las URL las que van en la pila). La página que usted está viendo actualmente está en el tope y la primera página que usted miró está en la base. Si usted hace clic en el botón Atrás, comienza a moverse en orden inverso a través de las páginas.
El tipo abstracto de datos Pila
El tipo abstracto de datos Pila se define mediante las siguientes estructura y operaciones. Una pila está estructurada, como se ha descrito anteriormente, como una colección ordenada de ítems en la cual los ítems se pueden agregar y eliminar en el extremo llamado “tope”. Las pilas tienen un ordenamiento LIFO. A continuación se describen las operaciones de la pila.
Pila() crea una nueva pila que está vacía. No necesita parámetros y devuelve una pila vacía.
incluir(item) agrega un nuevo ítem en el tope de la pila. Requiere el ítem y no devuelve valor.
extraer() elimina el ítem en el tope de la pila. No requiere parámetros y devuelve el ítem. La pila se modifica.
inspeccionar() devuelve el ítem en el tope de la pila pero no lo elimina. No requiere parámetros. La pila no se modifica.
estaVacia() comprueba si la pila está vacía. No requiere parámetros y devuelve un valor booleano.
tamano() devuelve el número de ítems en la pila. No requiere parámetros y devuelve un entero.
Por ejemplo, si p es una pila que se ha creado y comienza vacía, entonces la Tabla 1 muestra los resultados de una secuencia de operaciones de pila. En el contenido de la pila, el ítem del tope aparece en el extremo derecho.
Implementación de una pila en Python
Ahora que hemos definido claramente la pila como un tipo abstracto de datos, centraremos nuestra atención en usar Python para implementar la pila. Recuerde que cuando a un tipo abstracto de datos se le da una implementación física, dicha implementación se denomina una estructura de datos.
Como hemos descrito en el Capítulo 1, en Python, como en cualquier lenguaje de programación orientado a objetos, la implementación elegida para un tipo abstracto de datos como por ejemplo una pila es la creación de una nueva clase. Las operaciones de la pila se implementarán como métodos de la clase. Además, para implementar una pila, que es una colección de elementos, tiene sentido usar el poder y la simplicidad de las colecciones primitivas suministradas por Python. Nosotros usaremos una lista.
Recuerde que la clase List en Python proporciona un mecanismo de colección ordenada y un conjunto de métodos. Por ejemplo, si tenemos la lista [2,5,3,6,7,4], sólo tenemos que decidir qué extremo de la lista se considerará el tope de la pila y cuál será la base. Una vez que se toma esa decisión, las operaciones se pueden implementar usando los métodos de listas como append y pop.
En la siguiente implementación de la pila (ActiveCode 1) se asume que el final de la lista contendrá el elemento del tope de la pila. A medida que la pila crece (cuando se producen operaciones incluir), se añadirán nuevos elementos al final de la lista. Las operaciones extraer manipularán ese mismo extremo.
© 2019 Dance School. All Rights Reserved | Design by
W3layouts