Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserci\u00f3n y extracci\u00f3n se realizan por el mismo extremo.<\/p>\n
Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del tipo a) son las siguientes:<\/p>\n
\n vacia :: Pila a\n apila :: a -> Pila a -> Pila a\n cima :: Pila a -> a\n desapila :: Pila a -> Pila a\n esVacia :: Pila a -> Bool\n<\/pre>\ntales que<\/p>\n
Las operaciones tienen que verificar las siguientes propiedades:<\/p>\n
El TAD de las pilas se encuentra en el m\u00f3dulo Pila.hs<\/a> cuyo contenido es el siguiente:<\/p>\n Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descoment\u00e1ndola y comentando las otras.<\/p>\n La implementaci\u00f3n se encuentra en el m\u00f3dulo PilaConListas.hs<\/a> cuyo contenido es el siguiente:<\/p>\n La implementaci\u00f3n (que usa la librer\u00eda Data.Sequence<\/a>) se encuentra en el m\u00f3dulo PilaConSucesiones.hs<\/a> cuyo contenido es el siguiente:<\/p>\n La implementaci\u00f3n se encuentra en el m\u00f3dulo pila.py<\/a> cuyo contenido es el siguiente:<\/p>\n Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descoment\u00e1ndola y comentando las otras.<\/p>\n La implementaci\u00f3n se encuentra en el m\u00f3dulo pilaConListas.py<\/a> en el que se define la clase Pila con los siguientes m\u00e9todos:<\/p>\n Por ejemplo,<\/p>\n Adem\u00e1s se definen las correspondientes funciones. Por ejemplo,<\/p>\n Finalmente, se define un generador aleatorio de pilas y se comprueba que las pilas cumplen las propiedades de su especificaci\u00f3n.<\/p>\n La implementaci\u00f3n (que usa la librer\u00eda deque<\/a>) se encuentra en el m\u00f3dulo pilaConDeque.py<\/a> y su contenido es el siguiente:<\/p>\n 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\u00f3n y extracci\u00f3n se realizan por el mismo extremo. Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[586,585],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7841"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7841"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7841\/revisions"}],"predecessor-version":[{"id":7924,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7841\/revisions\/7924"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7841"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7841"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7841"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\nmodule TAD.Pila\n (Pila,\n vacia, -- Pila a\n apila, -- a -> Pila a -> Pila a\n cima, -- Pila a -> a\n desapila, -- Pila a -> Pila a\n esVacia, -- Pila a -> Bool\n escribePila -- Show a => Pila a -> String\n ) where\n\nimport TAD.PilaConListas\n-- import TAD.PilaConSucesiones\n<\/pre>\n
2.2. Implementaci\u00f3n de las pilas mediante listas<\/h4>\n
\nmodule TAD.PilaConListas\n (Pila,\n vacia, -- Pila a\n apila, -- a -> Pila a -> Pila a\n cima, -- Pila a -> a\n desapila, -- Pila a -> Pila a\n esVacia, -- Pila a -> Bool\n escribePila -- Show a => Pila a -> String\n ) where\n\nimport Test.QuickCheck\n\n-- Representaci\u00f3n de las pilas mediante listas.\nnewtype Pila a = P [a]\n deriving Eq\n\n-- (escribePila p) es la cadena correspondiente a la pila p. Por\n-- ejemplo,\n-- escribePila (apila 5 (apila 2 (apila 3 vacia))) == \"5 | 2 | 3\"\nescribePila :: Show a => Pila a -> String\nescribePila (P []) = \"-\"\nescribePila (P [x]) = show x\nescribePila (P (x:xs)) = show x ++ \" | \" ++ escribePila (P xs)\n\n-- Procedimiento de escritura de pilas.\ninstance Show a => Show (Pila a) where\n show = escribePila\n\n-- Ejemplo de pila:\n-- \u03bb> apila 1 (apila 2 (apila 3 vacia))\n-- 1 | 2 | 3\n\n-- vacia es la pila vac\u00eda. Por ejemplo,\n-- \u03bb> vacia\n-- -\nvacia :: Pila a\nvacia = P []\n\n-- (apila x p) es la pila obtenida a\u00f1adiendo x encima de la pila p. Por\n-- ejemplo,\n-- \u03bb> apila 4 (apila 3 (apila 2 (apila 5 vacia)))\n-- 4 | 3 | 2 | 5\napila :: a -> Pila a -> Pila a\napila x (P xs) = P (x:xs)\n\n-- (cima p) es la cima de la pila p. Por ejemplo,\n-- \u03bb> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))\n-- 4\ncima :: Pila a -> a\ncima (P []) = error \"cima de la pila vacia\"\ncima (P (x:_)) = x\n\n-- (desapila p) es la pila obtenida suprimiendo la cima de la pila\n-- p. Por ejemplo,\n-- \u03bb> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))\n-- 3 | 2 | 5\ndesapila :: Pila a -> Pila a\ndesapila (P []) = error \"desapila la pila vacia\"\ndesapila (P (_:xs)) = P xs\n\n-- (esVacia p) se verifica si p es la pila vac\u00eda. Por ejemplo,\n-- esVacia (apila 1 (apila 2 (apila 3 vacia))) == False\n-- esVacia vacia == True\nesVacia :: Pila a -> Bool\nesVacia (P xs) = null xs\n\n-- Generador de pilas --\n-- ==================\n\n-- genPila es un generador de pilas. Por ejemplo,\n-- \u03bb> sample genPila\n-- -\n-- 0|0|-\n-- -\n-- -6|4|-3|3|0|-\n-- -\n-- 9|5|-1|-3|0|-8|-5|-7|2|-\n-- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-\n-- 2|-14|-5|2|-\n-- 5|9|-\n-- -1|-14|5|-\n-- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-\ngenPila :: (Arbitrary a, Num a) => Gen (Pila a)\ngenPila = do\n xs <- listOf arbitrary\n return (foldr apila vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Pila a) where\n arbitrary = genPila\n\n-- Propiedades\n-- ===========\n\n-- Las propiedades son\nprop_pilas :: Int -> Pila Int -> Bool\nprop_pilas x p =\n cima (apila x p) == x &&\n desapila (apila x p) == p &&\n esVacia vacia &&\n not (esVacia (apila x p))\n\n-- La comprobaci\u00f3n e:\n-- \u03bb> quickCheck prop_pilas\n-- +++ OK, passed 100 tests.\n<\/pre>\n
2.3. Implementaci\u00f3n de las pilas mediante sucesiones<\/h4>\n
\nmodule TAD.PilaConSucesiones\n (Pila,\n vacia, -- Pila a\n apila, -- a -> Pila a -> Pila a\n cima, -- Pila a -> a\n desapila, -- Pila a -> Pila a\n esVacia, -- Pila a -> Bool\n escribePila -- Show a => Pila a -> String\n ) where\n\nimport Data.Sequence as S\nimport Test.QuickCheck\n\n-- Representaci\u00f3n de las pilas mediante sucesiones.\nnewtype Pila a = P (Seq a)\n deriving Eq\n\n-- (escribePila p) es la cadena correspondiente a la pila p. Por\n-- ejemplo,\n-- escribePila (apila 5 (apila 2 (apila 3 vacia))) == \"5 | 2 | 3\"\nescribePila :: Show a => Pila a -> String\nescribePila (P xs) = case viewl xs of\n EmptyL -> \"-\"\n x :< xs' -> case viewl xs' of\n EmptyL -> show x\n _ -> show x ++ \" | \" ++ escribePila (P xs')\n\n-- Procedimiento de escritura de pilas.\ninstance Show a => Show (Pila a) where\n show = escribePila\n\n-- Ejemplo de pila:\n-- \u03bb> apila 1 (apila 2 (apila 3 vacia))\n-- 1 | 2 | 3\n\n-- vacia es la pila vac\u00eda. Por ejemplo,\n-- \u03bb> vacia\n-- -\nvacia :: Pila a\nvacia = P empty\n\n-- (apila x p) es la pila obtenida a\u00f1adiendo x encima de la pila p. Por\n-- ejemplo,\n-- \u03bb> apila 4 (apila 3 (apila 2 (apila 5 vacia)))\n-- 5 | 2 | 3 | 4\napila :: a -> Pila a -> Pila a\napila x (P xs) = P (x <| xs)\n\n-- (cima p) es la cima de la pila p. Por ejemplo,\n-- \u03bb> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))\n-- 4\ncima :: Pila a -> a\ncima (P xs) = case viewl xs of\n EmptyL -> error \"cima de la pila vacia\"\n x :< _ -> x\n\n-- (desapila p) es la pila obtenida suprimiendo la cima de la pila\n-- p. Por ejemplo,\n-- \u03bb> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))\n-- 3 | 2 | 5\ndesapila :: Pila a -> Pila a\ndesapila (P xs) = case viewl xs of\n EmptyL -> error \"desapila la pila vacia\"\n _ :< xs' -> P xs'\n\n-- (esVacia p) se verifica si p es la pila vac\u00eda. Por ejemplo,\n-- esVacia (apila 1 (apila 2 (apila 3 vacia))) == False\n-- esVacia vacia == True\nesVacia :: Pila a -> Bool\nesVacia (P xs) = S.null xs\n\n-- Generador de pilas --\n-- ==================\n\n-- genPila es un generador de pilas. Por ejemplo,\n-- \u03bb> sample genPila\n-- -\n-- 0|0|-\n-- -\n-- -6|4|-3|3|0|-\n-- -\n-- 9|5|-1|-3|0|-8|-5|-7|2|-\n-- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-\n-- 2|-14|-5|2|-\n-- 5|9|-\n-- -1|-14|5|-\n-- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-\ngenPila :: (Arbitrary a, Num a) => Gen (Pila a)\ngenPila = do\n xs <- listOf arbitrary\n return (foldr apila vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Pila a) where\n arbitrary = genPila\n\n-- Propiedades\n-- ===========\n\n-- Las propiedades son\nprop_pilas :: Int -> Pila Int -> Bool\nprop_pilas x p =\n cima (apila x p) == x &&\n desapila (apila x p) == p &&\n esVacia vacia &&\n not (esVacia (apila x p))\n\n-- La comprobaci\u00f3n e:\n-- \u03bb> quickCheck prop_pilas\n-- +++ OK, passed 100 tests.\n<\/pre>\n
3. Las pilas en Python<\/h3>\n
3.1. El tipo abstracto de las pilas en Python<\/h4>\n
\n__all__ = [\n 'Pila',\n 'vacia',\n 'apila',\n 'esVacia',\n 'cima',\n 'desapila',\n 'pilaAleatoria'\n]\nfrom src.TAD.pilaConListas import (Pila, vacia, apila, esVacia, cima,\n desapila, pilaAleatoria)\n# from src.TAD.pilaConDeque import (Pila, vacia, apila, esVacia, cima,\n# desapila, pilaAleatoria)\n<\/pre>\n
3.2. Implementaci\u00f3n de las pilas mediante listas<\/h4>\n
\n
\n >>> p = Pila()\n >>> p\n -\n >>> p.apila(5)\n >>> p.apila(2)\n >>> p.apila(3)\n >>> p.apila(4)\n >>> p\n 4 | 3 | 2 | 5\n >>> p.cima()\n 4\n >>> p.desapila()\n >>> p\n 3 | 2 | 5\n >>> p.esVacia()\n False\n >>> p = Pila()\n >>> p.esVacia()\n True\n<\/pre>\n
\n >>> vacia()\n -\n >>> apila(4, apila(3, apila(2, apila(5, vacia()))))\n 4 | 3 | 2 | 5\n >>> cima(apila(4, apila(3, apila(2, apila(5, vacia())))))\n 4\n >>> desapila(apila(4, apila(3, apila(2, apila(5, vacia())))))\n 3 | 2 | 5\n >>> esVacia(apila(4, apila(3, apila(2, apila(5, vacia())))))\n False\n >>> esVacia(vacia())\n True\n<\/pre>\n
\n__all__ = [\n 'Pila',\n 'vacia',\n 'apila',\n 'esVacia',\n 'cima',\n 'desapila',\n 'pilaAleatoria'\n]\n\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# Clase de las pilas mediante Listas\n# ==================================\n\n@dataclass\nclass Pila(Generic[A]):\n _elementos: list[A] = field(default_factory=list)\n\n def __repr__(self) -> str:\n \"\"\"\n Devuelve una cadena con los elementos de la pila separados por \" | \".\n Si la pila est\u00e1 vac\u00eda, devuelve \"-\".\n \"\"\"\n if len(self._elementos) == 0:\n return '-'\n return \" | \".join(str(x) for x in self._elementos)\n\n def apila(self, x: A) -> None:\n \"\"\"\n Agrega el elemento x al inicio de la pila.\n \"\"\"\n self._elementos.insert(0, x)\n\n def esVacia(self) -> bool:\n \"\"\"\n Verifica si la pila est\u00e1 vac\u00eda.\n\n Devuelve True si la pila est\u00e1 vac\u00eda, False en caso contrario.\n \"\"\"\n return not self._elementos\n\n def cima(self) -> A:\n \"\"\"\n Devuelve el elemento en la cima de la pila.\n \"\"\"\n return self._elementos[0]\n\n def desapila(self) -> None:\n \"\"\"\n Elimina el elemento en la cima de la pila.\n \"\"\"\n self._elementos.pop(0)\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Pila[A]:\n \"\"\"\n Crea y devuelve una pila vac\u00eda de tipo A.\n \"\"\"\n p: Pila[A] = Pila()\n return p\n\ndef apila(x: A, p: Pila[A]) -> Pila[A]:\n \"\"\"\n A\u00f1ade un elemento x al tope de la pila p y devuelve una copia de la\n pila modificada.\n \"\"\"\n aux = deepcopy(p)\n aux.apila(x)\n return aux\n\ndef esVacia(p: Pila[A]) -> bool:\n \"\"\"\n Devuelve True si la pila est\u00e1 vac\u00eda, False si no lo est\u00e1.\n \"\"\"\n return p.esVacia()\n\ndef cima(p: Pila[A]) -> A:\n \"\"\"\n Devuelve el elemento en la cima de la pila p.\n \"\"\"\n return p.cima()\n\ndef desapila(p: Pila[A]) -> Pila[A]:\n \"\"\"\n Elimina el elemento en la cima de la pilla p y devuelve una copia de la\n pila resultante.\n \"\"\"\n aux = deepcopy(p)\n aux.desapila()\n return aux\n\n# Generador de pilas\n# ==================\n\ndef pilaAleatoria() -> st.SearchStrategy[Pila[int]]:\n \"\"\"\n Genera una estrategia de b\u00fasqueda para generar pilas de enteros de\n forma aleatoria.\n\n Utiliza la librer\u00eda Hypothesis para generar una lista de enteros y\n luego se convierte en una instancia de la clase pila.\n \"\"\"\n return st.lists(st.integers()).map(Pila)\n\n# Comprobaci\u00f3n de las propiedades de las pilas\n# ============================================\n\n# Las propiedades son\n@given(p=pilaAleatoria(), x=st.integers())\ndef test_pila(p: Pila[int], x: int) -> None:\n assert cima(apila(x, p)) == x\n assert desapila(apila(x, p)) == p\n assert esVacia(vacia())\n assert not esVacia(apila(x, p))\n\n# La comprobaci\u00f3n es\n# > poetry run pytest -q pilaConListas.py\n# 1 passed in 0.25s\n<\/pre>\n3.3. Implementaci\u00f3n de las pilas mediante deque<\/h4>\n
\n__all__ = [\n 'Pila',\n 'vacia',\n 'apila',\n 'esVacia',\n 'cima',\n 'desapila',\n 'pilaAleatoria'\n]\n\nfrom collections import deque\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# Clase de las pilas mediante listas\n# ==================================\n\n@dataclass\nclass Pila(Generic[A]):\n _elementos: deque[A] = field(default_factory=deque)\n\n def __repr__(self) -> str:\n \"\"\"\n Devuelve una cadena con los elementos de la pila separados por \" | \".\n Si la pila est\u00e1 vac\u00eda, devuelve \"-\".\n \"\"\"\n if len(self._elementos) == 0:\n return '-'\n return ' | '.join(str(x) for x in self._elementos)\n\n def apila(self, x: A) -> None:\n \"\"\"\n Agrega el elemento x al inicio de la pila.\n \"\"\"\n self._elementos.appendleft(x)\n\n def esVacia(self) -> bool:\n \"\"\"\n Verifica si la pila est\u00e1 vac\u00eda.\n\n Devuelve True si la pila est\u00e1 vac\u00eda, False en caso contrario.\n \"\"\"\n return len(self._elementos) == 0\n\n def cima(self) -> A:\n \"\"\"\n Devuelve el elemento en la cima de la pila.\n \"\"\"\n return self._elementos[0]\n\n def desapila(self) -> None:\n \"\"\"\n Elimina el elemento en la cima de la pila.\n \"\"\"\n self._elementos.popleft()\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Pila[A]:\n \"\"\"\n Crea y devuelve una pila vac\u00eda de tipo A.\n \"\"\"\n p: Pila[A] = Pila()\n return p\n\ndef apila(x: A, p: Pila[A]) -> Pila[A]:\n \"\"\"\n A\u00f1ade un elemento x al tope de la pila p y devuelve una copia de la\n pila modificada.\n \"\"\"\n _aux = deepcopy(p)\n _aux.apila(x)\n return _aux\n\ndef esVacia(p: Pila[A]) -> bool:\n \"\"\"\n Devuelve True si la pila est\u00e1 vac\u00eda, False si no lo est\u00e1.\n \"\"\"\n return p.esVacia()\n\ndef cima(p: Pila[A]) -> A:\n \"\"\"\n Devuelve el elemento en la cima de la pila p.\n \"\"\"\n return p.cima()\n\ndef desapila(p: Pila[A]) -> Pila[A]:\n \"\"\"\n Elimina el elemento en la cima de la pilla p y devuelve una copia de la\n pila resultante.\n \"\"\"\n _aux = deepcopy(p)\n _aux.desapila()\n return _aux\n\n# Generador de pilas\n# ==================\n\ndef pilaAleatoria() -> st.SearchStrategy[Pila[int]]:\n \"\"\"\n Genera una estrategia de b\u00fasqueda para generar pilas de enteros de\n forma aleatoria.\n\n Utiliza la librer\u00eda Hypothesis para generar una lista de enteros y\n luego se convierte en una instancia de la clase pila.\n \"\"\"\n def _creaPila(elementos: list[int]) -> Pila[int]:\n pila: Pila[int] = vacia()\n pila._elementos.extendleft(elementos)\n return pila\n return st.builds(_creaPila, st.lists(st.integers()))\n\n# Comprobaci\u00f3n de las propiedades de las pilas\n# ============================================\n\n# Las propiedades son\n@given(p=pilaAleatoria(), x=st.integers())\ndef test_pila(p: Pila[int], x: int) -> None:\n assert cima(apila(x, p)) == x\n assert desapila(apila(x, p)) == p\n assert esVacia(vacia())\n assert not esVacia(apila(x, p))\n\n# La comprobaci\u00f3n es\n# > poetry run pytest -q pilaConQueue.py\n# 1 passed in 0.25s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"