El tipo abstracto de datos de las pilas
1. El tipo abstracto de datos de las pilas
Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserción y extracción se realizan por el mismo extremo.
Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del tipo a) son las siguientes:
|
1 2 3 4 5 |
vacia :: Pila a apila :: a -> Pila a -> Pila a cima :: Pila a -> a desapila :: Pila a -> Pila a esVacia :: Pila a -> Bool |
tales que
- vacia es la pila vacía.
- (apila x p) es la pila obtenida añadiendo x al principio de p.
- (cima p) es la cima de la pila p.
- (desapila p) es la pila obtenida suprimiendo la cima de p.
- (esVacia p) se verifica si p es la pila vacía.
Las operaciones tienen que verificar las siguientes propiedades:
- cima(apila(x, p) == x
- desapila(apila(x, p)) == p
- esVacia(vacia)
- not esVacia(apila(x, p))
2. Las pilas en Haskell
2.1. El tipo abstracto de datos de las pilas en Haskell
El TAD de las pilas se encuentra en el módulo Pila.hs cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
module TAD.Pila (Pila, vacia, -- Pila a apila, -- a -> Pila a -> Pila a cima, -- Pila a -> a desapila, -- Pila a -> Pila a esVacia, -- Pila a -> Bool escribePila -- Show a => Pila a -> String ) where import TAD.PilaConListas -- import TAD.PilaConSucesiones |
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.
2.2. Implementación de las pilas mediante listas
La implementación se encuentra en el módulo PilaConListas.hs cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
module TAD.PilaConListas (Pila, vacia, -- Pila a apila, -- a -> Pila a -> Pila a cima, -- Pila a -> a desapila, -- Pila a -> Pila a esVacia, -- Pila a -> Bool escribePila -- Show a => Pila a -> String ) where import Test.QuickCheck -- Representación de las pilas mediante listas. newtype Pila a = P [a] deriving Eq -- (escribePila p) es la cadena correspondiente a la pila p. Por -- ejemplo, -- escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3" escribePila :: Show a => Pila a -> String escribePila (P []) = "-" escribePila (P [x]) = show x escribePila (P (x:xs)) = show x ++ " | " ++ escribePila (P xs) -- Procedimiento de escritura de pilas. instance Show a => Show (Pila a) where show = escribePila -- Ejemplo de pila: -- λ> apila 1 (apila 2 (apila 3 vacia)) -- 1 | 2 | 3 -- vacia es la pila vacía. Por ejemplo, -- λ> vacia -- - vacia :: Pila a vacia = P [] -- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por -- ejemplo, -- λ> apila 4 (apila 3 (apila 2 (apila 5 vacia))) -- 4 | 3 | 2 | 5 apila :: a -> Pila a -> Pila a apila x (P xs) = P (x:xs) -- (cima p) es la cima de la pila p. Por ejemplo, -- λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia)))) -- 4 cima :: Pila a -> a cima (P []) = error "cima de la pila vacia" cima (P (x:_)) = x -- (desapila p) es la pila obtenida suprimiendo la cima de la pila -- p. Por ejemplo, -- λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia)))) -- 3 | 2 | 5 desapila :: Pila a -> Pila a desapila (P []) = error "desapila la pila vacia" desapila (P (_:xs)) = P xs -- (esVacia p) se verifica si p es la pila vacía. Por ejemplo, -- esVacia (apila 1 (apila 2 (apila 3 vacia))) == False -- esVacia vacia == True esVacia :: Pila a -> Bool esVacia (P xs) = null xs -- Generador de pilas -- -- ================== -- genPila es un generador de pilas. Por ejemplo, -- λ> sample genPila -- - -- 0|0|- -- - -- -6|4|-3|3|0|- -- - -- 9|5|-1|-3|0|-8|-5|-7|2|- -- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|- -- 2|-14|-5|2|- -- 5|9|- -- -1|-14|5|- -- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|- genPila :: (Arbitrary a, Num a) => Gen (Pila a) genPila = do xs <- listOf arbitrary return (foldr apila vacia xs) -- El tipo pila es una instancia del arbitrario. instance (Arbitrary a, Num a) => Arbitrary (Pila a) where arbitrary = genPila -- Propiedades -- =========== -- Las propiedades son prop_pilas :: Int -> Pila Int -> Bool prop_pilas x p = cima (apila x p) == x && desapila (apila x p) == p && esVacia vacia && not (esVacia (apila x p)) -- La comprobación e: -- λ> quickCheck prop_pilas -- +++ OK, passed 100 tests. |
2.3. Implementación de las pilas mediante sucesiones
La implementación (que usa la librería Data.Sequence) se encuentra en el módulo PilaConSucesiones.hs cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
module TAD.PilaConSucesiones (Pila, vacia, -- Pila a apila, -- a -> Pila a -> Pila a cima, -- Pila a -> a desapila, -- Pila a -> Pila a esVacia, -- Pila a -> Bool escribePila -- Show a => Pila a -> String ) where import Data.Sequence as S import Test.QuickCheck -- Representación de las pilas mediante sucesiones. newtype Pila a = P (Seq a) deriving Eq -- (escribePila p) es la cadena correspondiente a la pila p. Por -- ejemplo, -- escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3" escribePila :: Show a => Pila a -> String escribePila (P xs) = case viewl xs of EmptyL -> "-" x :< xs' -> case viewl xs' of EmptyL -> show x _ -> show x ++ " | " ++ escribePila (P xs') -- Procedimiento de escritura de pilas. instance Show a => Show (Pila a) where show = escribePila -- Ejemplo de pila: -- λ> apila 1 (apila 2 (apila 3 vacia)) -- 1 | 2 | 3 -- vacia es la pila vacía. Por ejemplo, -- λ> vacia -- - vacia :: Pila a vacia = P empty -- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por -- ejemplo, -- λ> apila 4 (apila 3 (apila 2 (apila 5 vacia))) -- 5 | 2 | 3 | 4 apila :: a -> Pila a -> Pila a apila x (P xs) = P (x <| xs) -- (cima p) es la cima de la pila p. Por ejemplo, -- λ> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia)))) -- 4 cima :: Pila a -> a cima (P xs) = case viewl xs of EmptyL -> error "cima de la pila vacia" x :< _ -> x -- (desapila p) es la pila obtenida suprimiendo la cima de la pila -- p. Por ejemplo, -- λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia)))) -- 3 | 2 | 5 desapila :: Pila a -> Pila a desapila (P xs) = case viewl xs of EmptyL -> error "desapila la pila vacia" _ :< xs' -> P xs' -- (esVacia p) se verifica si p es la pila vacía. Por ejemplo, -- esVacia (apila 1 (apila 2 (apila 3 vacia))) == False -- esVacia vacia == True esVacia :: Pila a -> Bool esVacia (P xs) = S.null xs -- Generador de pilas -- -- ================== -- genPila es un generador de pilas. Por ejemplo, -- λ> sample genPila -- - -- 0|0|- -- - -- -6|4|-3|3|0|- -- - -- 9|5|-1|-3|0|-8|-5|-7|2|- -- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|- -- 2|-14|-5|2|- -- 5|9|- -- -1|-14|5|- -- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|- genPila :: (Arbitrary a, Num a) => Gen (Pila a) genPila = do xs <- listOf arbitrary return (foldr apila vacia xs) -- El tipo pila es una instancia del arbitrario. instance (Arbitrary a, Num a) => Arbitrary (Pila a) where arbitrary = genPila -- Propiedades -- =========== -- Las propiedades son prop_pilas :: Int -> Pila Int -> Bool prop_pilas x p = cima (apila x p) == x && desapila (apila x p) == p && esVacia vacia && not (esVacia (apila x p)) -- La comprobación e: -- λ> quickCheck prop_pilas -- +++ OK, passed 100 tests. |
3. Las pilas en Python
3.1. El tipo abstracto de las pilas en Python
La implementación se encuentra en el módulo pila.py cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
__all__ = [ 'Pila', 'vacia', 'apila', 'esVacia', 'cima', 'desapila', 'pilaAleatoria' ] from src.TAD.pilaConListas import (Pila, vacia, apila, esVacia, cima, desapila, pilaAleatoria) # from src.TAD.pilaConDeque import (Pila, vacia, apila, esVacia, cima, # desapila, pilaAleatoria) |
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.
3.2. Implementación de las pilas mediante listas
La implementación se encuentra en el módulo pilaConListas.py en el que se define la clase Pila con los siguientes métodos:
- apila(x) añade x al principio de la pila.
- cima() devuelve la cima de la pila.
- desapila() elimina la cima de la pila.
- esVacia() se verifica si la pila es vacía.
Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
>>> p = Pila() >>> p - >>> p.apila(5) >>> p.apila(2) >>> p.apila(3) >>> p.apila(4) >>> p 4 | 3 | 2 | 5 >>> p.cima() 4 >>> p.desapila() >>> p 3 | 2 | 5 >>> p.esVacia() False >>> p = Pila() >>> p.esVacia() True |
Además se definen las correspondientes funciones. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 |
>>> vacia() - >>> apila(4, apila(3, apila(2, apila(5, vacia())))) 4 | 3 | 2 | 5 >>> cima(apila(4, apila(3, apila(2, apila(5, vacia()))))) 4 >>> desapila(apila(4, apila(3, apila(2, apila(5, vacia()))))) 3 | 2 | 5 >>> esVacia(apila(4, apila(3, apila(2, apila(5, vacia()))))) False >>> esVacia(vacia()) True |
Finalmente, se define un generador aleatorio de pilas y se comprueba que las pilas cumplen las propiedades de su especificación.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
__all__ = [ 'Pila', 'vacia', 'apila', 'esVacia', 'cima', 'desapila', 'pilaAleatoria' ] from copy import deepcopy from dataclasses import dataclass, field from typing import Generic, TypeVar from hypothesis import given from hypothesis import strategies as st A = TypeVar('A') # Clase de las pilas mediante Listas # ================================== @dataclass class Pila(Generic[A]): _elementos: list[A] = field(default_factory=list) def __repr__(self) -> str: """ Devuelve una cadena con los elementos de la pila separados por " | ". Si la pila está vacía, devuelve "-". """ if len(self._elementos) == 0: return '-' return " | ".join(str(x) for x in self._elementos) def apila(self, x: A) -> None: """ Agrega el elemento x al inicio de la pila. """ self._elementos.insert(0, x) def esVacia(self) -> bool: """ Verifica si la pila está vacía. Devuelve True si la pila está vacía, False en caso contrario. """ return not self._elementos def cima(self) -> A: """ Devuelve el elemento en la cima de la pila. """ return self._elementos[0] def desapila(self) -> None: """ Elimina el elemento en la cima de la pila. """ self._elementos.pop(0) # Funciones del tipo de las listas # ================================ def vacia() -> Pila[A]: """ Crea y devuelve una pila vacía de tipo A. """ p: Pila[A] = Pila() return p def apila(x: A, p: Pila[A]) -> Pila[A]: """ Añade un elemento x al tope de la pila p y devuelve una copia de la pila modificada. """ aux = deepcopy(p) aux.apila(x) return aux def esVacia(p: Pila[A]) -> bool: """ Devuelve True si la pila está vacía, False si no lo está. """ return p.esVacia() def cima(p: Pila[A]) -> A: """ Devuelve el elemento en la cima de la pila p. """ return p.cima() def desapila(p: Pila[A]) -> Pila[A]: """ Elimina el elemento en la cima de la pilla p y devuelve una copia de la pila resultante. """ aux = deepcopy(p) aux.desapila() return aux # Generador de pilas # ================== def pilaAleatoria() -> st.SearchStrategy[Pila[int]]: """ Genera una estrategia de búsqueda para generar pilas de enteros de forma aleatoria. Utiliza la librería Hypothesis para generar una lista de enteros y luego se convierte en una instancia de la clase pila. """ return st.lists(st.integers()).map(Pila) # Comprobación de las propiedades de las pilas # ============================================ # Las propiedades son @given(p=pilaAleatoria(), x=st.integers()) def test_pila(p: Pila[int], x: int) -> None: assert cima(apila(x, p)) == x assert desapila(apila(x, p)) == p assert esVacia(vacia()) assert not esVacia(apila(x, p)) # La comprobación es # > poetry run pytest -q pilaConListas.py # 1 passed in 0.25s |
3.3. Implementación de las pilas mediante deque
La implementación (que usa la librería deque) se encuentra en el módulo pilaConDeque.py y su contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
__all__ = [ 'Pila', 'vacia', 'apila', 'esVacia', 'cima', 'desapila', 'pilaAleatoria' ] from collections import deque from copy import deepcopy from dataclasses import dataclass, field from typing import Generic, TypeVar from hypothesis import given from hypothesis import strategies as st A = TypeVar('A') # Clase de las pilas mediante listas # ================================== @dataclass class Pila(Generic[A]): _elementos: deque[A] = field(default_factory=deque) def __repr__(self) -> str: """ Devuelve una cadena con los elementos de la pila separados por " | ". Si la pila está vacía, devuelve "-". """ if len(self._elementos) == 0: return '-' return ' | '.join(str(x) for x in self._elementos) def apila(self, x: A) -> None: """ Agrega el elemento x al inicio de la pila. """ self._elementos.appendleft(x) def esVacia(self) -> bool: """ Verifica si la pila está vacía. Devuelve True si la pila está vacía, False en caso contrario. """ return len(self._elementos) == 0 def cima(self) -> A: """ Devuelve el elemento en la cima de la pila. """ return self._elementos[0] def desapila(self) -> None: """ Elimina el elemento en la cima de la pila. """ self._elementos.popleft() # Funciones del tipo de las listas # ================================ def vacia() -> Pila[A]: """ Crea y devuelve una pila vacía de tipo A. """ p: Pila[A] = Pila() return p def apila(x: A, p: Pila[A]) -> Pila[A]: """ Añade un elemento x al tope de la pila p y devuelve una copia de la pila modificada. """ _aux = deepcopy(p) _aux.apila(x) return _aux def esVacia(p: Pila[A]) -> bool: """ Devuelve True si la pila está vacía, False si no lo está. """ return p.esVacia() def cima(p: Pila[A]) -> A: """ Devuelve el elemento en la cima de la pila p. """ return p.cima() def desapila(p: Pila[A]) -> Pila[A]: """ Elimina el elemento en la cima de la pilla p y devuelve una copia de la pila resultante. """ _aux = deepcopy(p) _aux.desapila() return _aux # Generador de pilas # ================== def pilaAleatoria() -> st.SearchStrategy[Pila[int]]: """ Genera una estrategia de búsqueda para generar pilas de enteros de forma aleatoria. Utiliza la librería Hypothesis para generar una lista de enteros y luego se convierte en una instancia de la clase pila. """ def _creaPila(elementos: list[int]) -> Pila[int]: pila: Pila[int] = vacia() pila._elementos.extendleft(elementos) return pila return st.builds(_creaPila, st.lists(st.integers())) # Comprobación de las propiedades de las pilas # ============================================ # Las propiedades son @given(p=pilaAleatoria(), x=st.integers()) def test_pila(p: Pila[int], x: int) -> None: assert cima(apila(x, p)) == x assert desapila(apila(x, p)) == p assert esVacia(vacia()) assert not esVacia(apila(x, p)) # La comprobación es # > poetry run pytest -q pilaConQueue.py # 1 passed in 0.25s |