Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operaci\u00f3n de inserci\u00f3n se realiza por un extremo (el posterior o final) y la operaci\u00f3n de extracci\u00f3n por el otro (el anterior o frente).<\/p>\n
Las operaciones que definen a tipo abstracto de datos (TAD) de las colas (cuyos elementos son del tipo a) son las siguientes:<\/p>\n
\n vacia :: Cola a\n inserta :: a -> Cola a -> Cola a\n primero :: Cola a -> a\n resto :: Cola a -> Cola a\n esVacia :: Cola a -> Bool\n<\/pre>\ntales que<\/p>\n
Las operaciones tienen que verificar las siguientes propiedades:<\/p>\n
El TAD de las colas se encuentra en el m\u00f3dulo Cola.hs<\/a> cuyo contenido es el siguiente:<\/p>\n Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos tres: una usando listas, otra usando pares de 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 ColaConListas.hs<\/a> cuyo contenido es el siguiente:<\/p>\n En esta implementaci\u00f3n, una cola c se representa mediante un par de listas (xs,ys) de modo que los elementos de c son, en ese orden, los elementos de la lista xs++(reverse ys).<\/p>\n Al dividir la lista en dos parte e invertir la segunda de ellas, esperamos hacer m\u00e1s eficiente las operaciones sobre las colas.<\/p>\n Impondremos tambi\u00e9n una restricci\u00f3n adicional sobre la representaci\u00f3n: las colas ser\u00e1n representadas mediante pares (xs,ys) tales que si xs es vac\u00eda, entonces ys ser\u00e1 tambi\u00e9n vac\u00eda. Esta restricci\u00f3n ha de ser conservada por los programas que crean colas.<\/p>\n La implementaci\u00f3n se encuentra en el m\u00f3dulo ColaConDosListas.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 ColaConSucesiones.hs<\/a> cuyo contenido es el siguiente:<\/p>\n La implementaci\u00f3n se encuentra en el m\u00f3dulo cola.py<\/a> cuyo contenido es el siguiente:<\/p>\n Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos tres: una usando listas, otra usando pares de listas y otra usando deques. 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 colaConListas.py<\/a> en el que se define la clase Cola 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 colas y se comprueba que las colas cumplen las propiedades de su especificaci\u00f3n.<\/p>\n La implementaci\u00f3n se encuentra en el m\u00f3dulo colaConDosListas.py<\/a> cuyo contenido es<\/p>\n La implementaci\u00f3n (que usa la librer\u00eda deque<\/a>) se encuentra en el m\u00f3dulo colaConDeque.py<\/a> y su contenido es el siguiente:<\/p>\n 1. El tipo abstracto de datos de las colas Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operaci\u00f3n de inserci\u00f3n se realiza por un extremo (el posterior o final) y la operaci\u00f3n de extracci\u00f3n por el otro (el anterior o frente). Las operaciones que definen…<\/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":[515,585],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7860"}],"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=7860"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7860\/revisions"}],"predecessor-version":[{"id":7925,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7860\/revisions\/7925"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7860"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7860"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7860"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\nmodule TAD.Cola\n (Cola,\n vacia, -- Cola a\n inserta, -- a -> Cola a -> Cola a\n primero, -- Cola a -> a\n resto, -- Cola a -> Cola a\n esVacia, -- Cola a -> Bool\n ) where\n\nimport TAD.ColaConListas\n-- import TAD.ColaConDosListas\n-- import TAD.ColaConSucesiones\n<\/pre>\n
2.2. Implementaci\u00f3n de las colas mediante listas<\/h4>\n
\n{-# LANGUAGE FlexibleInstances #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.ColaConListas\n (Cola,\n vacia, -- Cola a\n inserta, -- a -> Cola a -> Cola a\n primero, -- Cola a -> a\n resto, -- Cola a -> Cola a\n esVacia, -- Cola a -> Bool\n ) where\n\nimport Test.QuickCheck\n\n-- Colas como listas:\nnewtype Cola a = C [a]\n deriving Eq\n\n-- (escribeCola c) es la cadena correspondiente a la cola c. Por\n-- ejemplo,\n-- escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == \"3 | 2 | 5\"\nescribeCola :: Show a => Cola a -> String\nescribeCola (C []) = \"-\"\nescribeCola (C [x]) = show x\nescribeCola (C (x:xs)) = show x ++ \" | \" ++ escribeCola (C xs)\n\n-- Procedimiento de escritura de colas.\ninstance Show a => Show (Cola a) where\n show = escribeCola\n\n-- Ejemplo de cola:\n-- \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n-- 3 | 2 | 5\n\n-- vacia es la cola vac\u00eda. Por ejemplo,\n-- \u03bb> vacia\n-- -\nvacia :: Cola a\nvacia = C []\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo x al final de la cola\n-- c. Por ejemplo,\n-- \u03bb> ej = inserta 2 (inserta 3 vacia)\n-- \u03bb> ej\n-- 3 | 2\n-- \u03bb> inserta 5 ej\n-- 3 | 2 | 5\ninserta :: a -> Cola a -> Cola a\ninserta x (C c) = C (c ++ [x])\n\n-- (primero c) es el primer elemento de la cola c. Por ejemplo,\n-- \u03bb> primero (inserta 5 (inserta 2 (inserta 3 vacia)))\n-- 3\nprimero :: Cola a -> a\nprimero (C []) = error \"primero: cola vacia\"\nprimero (C (x:_)) = x\n\n-- (resto c) es la cola obtenida eliminando el primer elemento de la\n-- cola c. Por ejemplo,\n-- \u03bb> resto (inserta 5 (inserta 2 (inserta 3 vacia)))\n-- 2 | 5\nresto :: Cola a -> Cola a\nresto (C (_:xs)) = C xs\nresto (C []) = error \"resto: cola vacia\"\n\n-- (esVacia c) se verifica si c es la cola vac\u00eda. Por ejemplo,\n-- esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False\n-- esVacia vacia == True\nesVacia :: Cola a -> Bool\nesVacia (C xs) = null xs\n\n-- Generador de colas --\n-- ==================\n\n-- genCola es un generador de colas de enteros. Por ejemplo,\n-- \u03bb> sample genCola\n-- -\n-- -\n-- -3 | 2\n-- 6 | 0 | 1\n-- -5 | 0 | -5 | 0 | -4\n-- 2 | 9 | -6 | 9 | 0 | -1\n-- -\n-- 11 | -5 | 5\n-- -\n-- 16 | 6 | 15 | -3 | -9\n-- 11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13\ngenCola :: (Arbitrary a, Num a) => Gen (Cola a)\ngenCola = do\n xs <- listOf arbitrary\n return (foldr inserta vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Cola a) where\n arbitrary = genCola\n\n-- Propiedades de las colas\n-- ========================\n\n-- Las propiedades son\nprop_colas1 :: Int -> Cola Int -> Bool\nprop_colas1 x c =\n primero (inserta x vacia) == x &&\n resto (inserta x vacia) == vacia &&\n esVacia vacia &&\n not (esVacia (inserta x c))\n\nprop_colas2 :: Int -> Cola Int -> Property\nprop_colas2 x c =\n not (esVacia c) ==>\n primero (inserta x c) == primero c &&\n resto (inserta x c) == inserta x (resto c)\n\n-- La comprobaci\u00f3n es:\n-- \u03bb> quickCheck prop_colas1\n-- +++ OK, passed 100 tests.\n-- \u03bb> quickCheck prop_colas2\n-- +++ OK, passed 100 tests; 3 discarded.\n<\/pre>\n2.3. Implementaci\u00f3n de las colas mediante pares de listas<\/h4>\n
\nmodule TAD.ColaConDosListas\n (Cola,\n vacia, -- Cola a\n inserta, -- a -> Cola a -> Cola a\n primero, -- Cola a -> a\n resto, -- Cola a -> Cola a\n esVacia, -- Cola a -> Bool\n ) where\n\nimport Test.QuickCheck\n\n-- Las colas como pares listas.\nnewtype Cola a = C ([a],[a])\n\n-- (escribeCola p) es la cadena correspondiente a la cola p. Por\n-- ejemplo,\n-- \u03bb> escribeCola (inserta 5 (inserta 2 (inserta 3 vacia)))\n-- \"3 | 2 | 5\"\nescribeCola :: Show a => Cola a -> String\nescribeCola (C (xs,ys)) = aux (xs ++ reverse ys)\n where aux [] = \"-\"\n aux [z] = show z\n aux (z:zs) = show z ++ \" | \" ++ aux zs\n\n-- Procedimiento de escritura de colas.\ninstance Show a => Show (Cola a) where\n show = escribeCola\n\n-- Ejemplo de cola:\n-- \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n-- 3 | 2 | 5\n\n-- vacia es la cola vac\u00eda. Por ejemplo,\n-- \u03bb> vacia\n-- -\nvacia :: Cola a\nvacia = C ([],[])\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo x al final de la cola\n-- c. Por ejemplo,\n-- \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n-- 3 | 2 | 5\ninserta :: a -> Cola a -> Cola a\ninserta y (C (xs,ys)) = C (normaliza (xs,y:ys))\n\n-- (normaliza p) es la cola obtenida al normalizar el par de listas\n-- p. Por ejemplo,\n-- normaliza ([],[2,5,3]) == ([3,5,2],[])\n-- normaliza ([4],[2,5,3]) == ([4],[2,5,3])\nnormaliza :: ([a],[a]) -> ([a],[a])\nnormaliza ([], ys) = (reverse ys, [])\nnormaliza p = p\n\n-- (primero c) es el primer elemento de la cola c. Por ejemplo,\n-- \u03bb> primero (inserta 5 (inserta 2 (inserta 3 vacia)))\n-- 3\nprimero :: Cola a -> a\nprimero (C (x:_,_)) = x\nprimero _ = error \"primero: cola vacia\"\n\n-- (resto c) es la cola obtenida eliminando el primer elemento de la\n-- cola c. Por ejemplo,\n-- \u03bb> resto (inserta 5 (inserta 2 (inserta 3 vacia)))\n-- 2 | 5\nresto :: Cola a -> Cola a\nresto (C ([],[])) = error \"resto: cola vacia\"\nresto (C (_:xs,ys)) = C (normaliza (xs,ys))\nresto (C ([],_:_)) = error \"Imposible\"\n\n-- (esVacia c) se verifica si c es la cola vac\u00eda. Por ejemplo,\n-- esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False\n-- esVacia vacia == True\nesVacia :: Cola a -> Bool\nesVacia (C (xs,_)) = null xs\n\n-- (valida c) se verifica si la cola c es v\u00e1lida; es decir, si\n-- su primer elemento es vac\u00edo entonces tambi\u00e9n lo es el segundo. Por\n-- ejemplo,\n-- valida (C ([2],[5])) == True\n-- valida (C ([2],[])) == True\n-- valida (C ([],[5])) == False\nvalida :: Cola a -> Bool\nvalida (C (xs,ys)) = not (null xs) || null ys\n\n-- ---------------------------------------------------------------------\n-- Igualdad de colas --\n-- ---------------------------------------------------------------------\n\n-- (elementos c) es la lista de los elementos de la cola c en el orden de\n-- la cola. Por ejemplo,\n-- \u03bb> elementos (inserta 5 (inserta 2 (inserta 3 vacia)))\n-- [3,2,5]\nelementos :: Cola a -> [a]\nelementos (C (xs,ys)) = xs ++ reverse ys\n\n-- (igualColas c1 c2) se verifica si las colas c1 y c2 son iguales. Por\n-- ejemplo,\n-- igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2])) == True\n-- igualColas (C ([3,2],[5,4,7])) (C ([],[5,4,7,2,3])) == False\nigualColas :: Eq a => Cola a -> Cola a -> Bool\nigualColas c1 c2 =\n valida c1 &&\n valida c2 &&\n elementos c1 == elementos c2\n\ninstance Eq a => Eq (Cola a) where\n (==) = igualColas\n\n-- Generador de colas --\n-- ==================\n\n-- genCola es un generador de colas de enteros. Por ejemplo,\n-- \u03bb> sample genCola\n-- -\n-- -\n-- -3 | 2\n-- 6 | 0 | 1\n-- -5 | 0 | -5 | 0 | -4\n-- 2 | 9 | -6 | 9 | 0 | -1\n-- -\n-- 11 | -5 | 5\n-- -\n-- 16 | 6 | 15 | -3 | -9\n-- 11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13\ngenCola :: (Arbitrary a, Num a) => Gen (Cola a)\ngenCola = do\n xs <- listOf arbitrary\n return (foldr inserta vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Cola a) where\n arbitrary = genCola\n\n-- Propiedades de las colas\n-- ========================\n\n-- Las propiedades son\nprop_colas1 :: Int -> Cola Int -> Bool\nprop_colas1 x c =\n primero (inserta x vacia) == x &&\n resto (inserta x vacia) == vacia &&\n esVacia vacia &&\n not (esVacia (inserta x c))\n\nprop_colas2 :: Int -> Cola Int -> Property\nprop_colas2 x c =\n not (esVacia c) ==>\n primero (inserta x c) == primero c &&\n resto (inserta x c) == inserta x (resto c)\n\n-- La comprobaci\u00f3n es:\n-- \u03bb> quickCheck prop_colas1\n-- +++ OK, passed 100 tests.\n-- \u03bb> quickCheck prop_colas2\n-- +++ OK, passed 100 tests; 3 discarded.\n<\/pre>\n
2.4. Implementaci\u00f3n de las colas mediante sucesiones<\/h4>\n
\n{-# LANGUAGE FlexibleInstances #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.ColaConSucesiones\n (Cola,\n vacia, -- Cola a\n inserta, -- a -> Cola a -> Cola a\n primero, -- Cola a -> a\n resto, -- Cola a -> Cola a\n esVacia, -- Cola a -> Bool\n ) where\n\nimport Data.Sequence as S\nimport Test.QuickCheck\n\n-- Colas como sucesiones:\nnewtype Cola a = C (Seq a)\n deriving Eq\n\n-- (escribeCola c) es la cadena correspondiente a la cola c. Por\n-- ejemplo,\n-- escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == \"3 | 2 | 5\"\nescribeCola :: Show a => Cola a -> String\nescribeCola (C xs) = case viewl xs of\n EmptyL -> \"-\"\n x :< xs' -> case viewl xs' of\n EmptyL -> show x\n _ -> show x ++ \" | \" ++ escribeCola (C xs')\n\n-- Procedimiento de escritura de colas.\ninstance Show a => Show (Cola a) where\n show = escribeCola\n\n-- Ejemplo de cola:\n-- \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n-- 3 | 2 | 5\n\n-- vacia es la cola vac\u00eda. Por ejemplo,\n-- \u03bb> vacia\n-- C []\nvacia :: Cola a\nvacia = C empty\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo x al final de la cola\n-- c. Por ejemplo,\n-- \u03bb> ej = inserta 2 (inserta 3 vacia)\n-- \u03bb> ej\n-- 3 | 2\n-- \u03bb> inserta 5 ej\n-- 3 | 2 | 5\ninserta :: a -> Cola a -> Cola a\ninserta x (C xs) = C (xs |> x )\n\n-- (primero c) es el primer elemento de la cola c. Por ejemplo,\n-- \u03bb> primero (inserta 5 (inserta 2 (inserta 3 vacia)))\n-- 3\nprimero :: Cola a -> a\nprimero (C xs) = case viewl xs of\n EmptyL -> error \"primero de la pila vacia\"\n x :< _ -> x\n\n-- (resto c) es la cola obtenida eliminando el primer elemento de la\n-- cola c. Por ejemplo,\n-- \u03bb> resto (inserta 5 (inserta 2 (inserta 3 vacia)))\n-- 2 | 5\nresto :: Cola a -> Cola a\nresto (C xs) = case viewl xs of\n EmptyL -> error \"resto la pila vacia\"\n _ :< xs' -> C xs'\n\n-- (esVacia c) se verifica si c es la cola vac\u00eda. Por ejemplo,\n-- esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False\n-- esVacia vacia == True\nesVacia :: Cola a -> Bool\nesVacia (C xs) = S.null xs\n\n-- Generador de colas --\n-- ==================\n\n-- genCola es un generador de colas de enteros. Por ejemplo,\n-- \u03bb> sample genCola\n-- -\n-- 2 | -2\n-- 0 | 0 | 0 | 4\n-- -\n-- 2\n-- -1 | -6 | 9\n-- 12 | -12 | -12 | 7 | -2 | -3 | 5 | -8 | -3 | -9 | -6\n-- -11 | -5 | -7 | -8 | -10 | 8 | -9 | -7 | 6 | -12 | 8 | -9 | -1\n-- -16 | -12\n-- -17 | -17 | 1 | 2 | -15 | -15 | -13 | 8 | 13 | -12 | 15\n-- -16 | -18\ngenCola :: (Arbitrary a, Num a) => Gen (Cola a)\ngenCola = do\n xs <- listOf arbitrary\n return (foldr inserta vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Cola a) where\n arbitrary = genCola\n\n-- Propiedades de las colas\n-- ========================\n\n-- Las propiedades son\nprop_colas1 :: Int -> Cola Int -> Bool\nprop_colas1 x c =\n primero (inserta x vacia) == x &&\n resto (inserta x vacia) == vacia &&\n esVacia vacia &&\n not (esVacia (inserta x c))\n\nprop_colas2 :: Int -> Cola Int -> Property\nprop_colas2 x c =\n not (esVacia c) ==>\n primero (inserta x c) == primero c &&\n resto (inserta x c) == inserta x (resto c)\n\n-- La comprobaci\u00f3n es:\n-- \u03bb> quickCheck prop_colas1\n-- +++ OK, passed 100 tests.\n-- \u03bb> quickCheck prop_colas2\n-- +++ OK, passed 100 tests; 9 discarded.\n<\/pre>\n3. Las colas en Python<\/h3>\n
3.1. El tipo abstracto de las colas en Python<\/h4>\n
\n__all__ = [\n 'Cola',\n 'vacia',\n 'inserta',\n 'primero',\n 'resto',\n 'esVacia',\n 'colaAleatoria'\n]\nfrom src.TAD.colaConListas import (Cola, colaAleatoria, esVacia, inserta,\n primero, resto, vacia)\n# from src.TAD.colaConDosListas import (Cola, colaAleatoria, esVacia, inserta,\n# primero, resto, vacia)\n# from src.TAD.colaConDeque import (Cola, vacia, inserta, primero, resto,\n# esVacia, colaAleatoria)\n<\/pre>\n
3.2. Implementaci\u00f3n de las colas mediante listas<\/h4>\n
\n
\n >>> c = Cola()\n >>> c\n -\n >>> c.inserta(5)\n >>> c.inserta(2)\n >>> c.inserta(3)\n >>> c.inserta(4)\n >>> c\n 5 | 2 | 3 | 4\n >>> c.primero()\n 5\n >>> c.resto()\n >>> c\n 2 | 3 | 4\n >>> c.esVacia()\n False\n >>> c = Cola()\n >>> c.esVacia()\n True\n<\/pre>\n
\n >>> vacia()\n -\n >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))\n 5 | 2 | 3 | 4\n >>> primero(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n 5\n >>> resto(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n 2 | 3 | 4\n >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n False\n >>> esVacia(vacia())\n True\n<\/pre>\n
\n__all__ = [\n 'Cola',\n 'vacia',\n 'inserta',\n 'primero',\n 'resto',\n 'esVacia',\n 'colaAleatoria'\n]\n\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import assume, given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# Clase de las colas mediante listas\n# ==================================\n\n@dataclass\nclass Cola(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 cola separados por \" | \".\n Si la cola est\u00e1 vac\u00eda, devuelve \"-\".\n \"\"\"\n if not self._elementos:\n return '-'\n return ' | '.join(str(x) for x in self._elementos)\n\n def inserta(self, x: A) -> None:\n \"\"\"\n Inserta el elemento x al final de la cola.\n \"\"\"\n self._elementos.append(x)\n\n def esVacia(self) -> bool:\n \"\"\"\n Comprueba si la cola est\u00e1 vac\u00eda.\n\n Devuelve True si la cola est\u00e1 vac\u00eda, False en caso contrario.\n \"\"\"\n return not self._elementos\n\n def primero(self) -> A:\n \"\"\"\n Devuelve el primer elemento de la cola.\n \"\"\"\n return self._elementos[0]\n\n def resto(self) -> None:\n \"\"\"\n Elimina el primer elemento de la cola\n \"\"\"\n self._elementos.pop(0)\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Cola[A]:\n \"\"\"\n Crea y devuelve una cola vac\u00eda de tipo A.\n \"\"\"\n c: Cola[A] = Cola()\n return c\n\ndef inserta(x: A, c: Cola[A]) -> Cola[A]:\n \"\"\"\n Inserta un elemento x en la cola c y devuelve una nueva cola con\n el elemento insertado.\n \"\"\"\n _aux = deepcopy(c)\n _aux.inserta(x)\n return _aux\n\ndef esVacia(c: Cola[A]) -> bool:\n \"\"\"\n Devuelve True si la cola est\u00e1 vac\u00eda, False si no lo est\u00e1.\n \"\"\"\n return c.esVacia()\n\ndef primero(c: Cola[A]) -> A:\n \"\"\"\n Devuelve el primer elemento de la cola c.\n \"\"\"\n return c.primero()\n\ndef resto(c: Cola[A]) -> Cola[A]:\n \"\"\"\n Elimina el primer elemento de la cola c y devuelve una copia de la\n cola resultante.\n \"\"\"\n _aux = deepcopy(c)\n _aux.resto()\n return _aux\n\n# Generador de colas\n# ==================\n\ndef colaAleatoria() -> st.SearchStrategy[Cola[int]]:\n \"\"\"\n Genera una estrategia de b\u00fasqueda para generar colas 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 cola.\n \"\"\"\n return st.lists(st.integers()).map(Cola)\n\n# Comprobaci\u00f3n de las propiedades de las colas\n# ============================================\n\n# Las propiedades son\n@given(c=colaAleatoria(), x=st.integers())\ndef test_cola1(c: Cola[int], x: int) -> None:\n assert primero(inserta(x, vacia())) == x\n assert resto(inserta(x, vacia())) == vacia()\n assert esVacia(vacia())\n assert not esVacia(inserta(x, c))\n\n@given(c=colaAleatoria(), x=st.integers())\ndef test_cola2(c: Cola[int], x: int) -> None:\n assume(not esVacia(c))\n assert primero(inserta(x, c)) == primero(c)\n assert resto(inserta(x, c)) == inserta(x, resto(c))\n\n# La comprobaci\u00f3n es\n# > poetry run pytest -q colaConListas.py\n# 1 passed in 0.24s\n<\/pre>\n3.3. Implementaci\u00f3n de las colas mediante pares de listas<\/h4>\n
\n__all__ = [\n 'Cola',\n 'vacia',\n 'inserta',\n 'primero',\n 'resto',\n 'esVacia',\n 'colaAleatoria'\n]\n\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import assume, given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# Clase de las colas mediante listas\n# ==================================\n\n@dataclass\nclass Cola(Generic[A]):\n _primera: list[A] = field(default_factory=list)\n _segunda: list[A] = field(default_factory=list)\n\n def _elementos(self) -> list[A]:\n \"\"\"\n Devuelve una lista con los elementos de la cola en orden.\n \"\"\"\n return self._primera + self._segunda[::-1]\n\n def __repr__(self) -> str:\n \"\"\"\n Devuelve una cadena con los elementos de la cola separados por \" | \".\n Si la cola est\u00e1 vac\u00eda, devuelve \"-\".\n \"\"\"\n elementos = self._elementos()\n if not elementos:\n return \"-\"\n return \" | \".join(map(str, elementos))\n\n def __eq__(self, c) -> bool:\n \"\"\"\n Comprueba si la cola actual es igual a otra cola.\n Se considera que dos colas son iguales si tienen los mismos\n elementos en el mismo orden.\n\n Par\u00e1metro:\n - c (Cola): La cola con la que se va a comparar.\n\n Devuelve True si las dos colas son iguales, False en caso\n contrario.\n \"\"\"\n return self._elementos() == c._elementos()\n\n def inserta(self, y: A) -> None:\n \"\"\"\n Inserta el elemento y en la cola.\n \"\"\"\n xs = self._primera\n ys = self._segunda\n # Si no hay elementos en la primera lista, se inserta en la segunda\n if not xs:\n ys.insert(0, y)\n # Se invierte la segunda lista y se asigna a la primera\n self._primera = ys[::-1]\n self._segunda = []\n else:\n # Si hay elementos en la primera lista, se inserta en la segunda\n ys.insert(0, y)\n\n def esVacia(self) -> bool:\n \"\"\"\n Devuelve si la cola est\u00e1 vac\u00eda.\n \"\"\"\n return not self._primera\n\n def primero(self) -> A:\n \"\"\"\n Devuelve el primer elemento de la cola.\n \"\"\"\n return self._primera[0]\n\n def resto(self) -> None:\n \"\"\"\n Elimina el primer elemento de la cola.\n \"\"\"\n xs = self._primera\n ys = self._segunda\n del xs[0]\n if not xs:\n self._primera = ys[::-1]\n self._segunda = []\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Cola[A]:\n \"\"\"\n Crea y devuelve una cola vac\u00eda de tipo A.\n \"\"\"\n c: Cola[A] = Cola()\n return c\n\ndef inserta(x: A, c: Cola[A]) -> Cola[A]:\n \"\"\"\n Inserta un elemento x en la cola c y devuelve una nueva cola con\n el elemento insertado.\n \"\"\"\n _aux = deepcopy(c)\n _aux.inserta(x)\n return _aux\n\ndef esVacia(c: Cola[A]) -> bool:\n \"\"\"\n Devuelve True si la cola est\u00e1 vac\u00eda, False si no lo est\u00e1.\n \"\"\"\n return c.esVacia()\n\ndef primero(c: Cola[A]) -> A:\n \"\"\"\n Devuelve el primer elemento de la cola c.\n \"\"\"\n return c.primero()\n\ndef resto(c: Cola[A]) -> Cola[A]:\n \"\"\"\n Elimina el primer elemento de la cola c y devuelve una copia de la\n cola resultante.\n \"\"\"\n _aux = deepcopy(c)\n _aux.resto()\n return _aux\n\n# Generador de colas\n# ==================\n\ndef colaAleatoria() -> st.SearchStrategy[Cola[int]]:\n \"\"\"\n Genera una estrategia de b\u00fasqueda para generar colas 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 cola.\n \"\"\"\n return st.lists(st.integers()).map(Cola)\n\n# Comprobaci\u00f3n de las propiedades de las colas\n# ============================================\n\n# Las propiedades son\n@given(c=colaAleatoria(), x=st.integers())\ndef test_cola1(c: Cola[int], x: int) -> None:\n assert primero(inserta(x, vacia())) == x\n assert resto(inserta(x, vacia())) == vacia()\n assert esVacia(vacia())\n assert not esVacia(inserta(x, c))\n\n@given(c=colaAleatoria(), x=st.integers())\ndef test_cola2(c: Cola[int], x: int) -> None:\n assume(not esVacia(c))\n assert primero(inserta(x, c)) == primero(c)\n assert resto(inserta(x, c)) == inserta(x, resto(c))\n\n# La comprobaci\u00f3n es\n# > poetry run pytest -q colaConListas.py\n# 2 passed in 0.40s\n<\/pre>\n3.4. Implementaci\u00f3n de las colas 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":"