Menu Close

El tipo abstracto de datos de las colas

José A. Alonso,

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ón de inserción se realiza por un extremo (el posterior o final) y la operación de extracción por el otro (el anterior o frente).

Las operaciones que definen a tipo abstracto de datos (TAD) de las colas (cuyos elementos son del tipo a) son las siguientes:

   vacia   :: Cola a
   inserta :: a -> Cola a -> Cola a
   primero :: Cola a -> a
   resto   :: Cola a -> Cola a
   esVacia :: Cola a -> Bool

tales que

  • vacia es la cola vacía.
  • (inserta x c) es la cola obtenida añadiendo x al final de c.
  • (primero c) es el primero de la cola c.
  • (resto c) es la cola obtenida eliminando el primero de c.
  • (esVacia c) se verifica si c es la cola vacía.

Las operaciones tienen que verificar las siguientes propiedades:

  • primero (inserta x vacia) == x
  • Si c es una cola no vacía, entonces primero (inserta x c) == primero c,
  • resto (inserta x vacia) == vacia
  • Si c es una cola no vacía, entonces resto (inserta x c) == inserta x (resto c)
  • esVacia vacia
  • not (esVacia (inserta x c))

2. Las colas en Haskell

2.1. El tipo abstracto de datos de las colas en Haskell

El TAD de las colas se encuentra en el módulo Cola.hs cuyo contenido es el siguiente:

module TAD.Cola
  (Cola,
   vacia,      -- Cola a
   inserta,    -- a -> Cola a -> Cola a
   primero,    -- Cola a -> a
   resto,      -- Cola a -> Cola a
   esVacia,    -- Cola a -> Bool
  ) where
 
import TAD.ColaConListas
-- import TAD.ColaConDosListas
-- import TAD.ColaConSucesiones

Para usar el TAD hay que usar una implementación 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ándola y comentando las otras.

2.2. Implementación de las colas mediante listas

La implementación se encuentra en el módulo ColaConListas.hs cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}
 
module TAD.ColaConListas
  (Cola,
   vacia,   -- Cola a
   inserta, -- a -> Cola a -> Cola a
   primero, -- Cola a -> a
   resto,   -- Cola a -> Cola a
   esVacia, -- Cola a -> Bool
  ) where
 
import Test.QuickCheck
 
-- Colas como listas:
newtype Cola a = C [a]
  deriving Eq
 
-- (escribeCola c) es la cadena correspondiente a la cola c. Por
-- ejemplo,
--    escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == "3 | 2 | 5"
escribeCola :: Show a => Cola a -> String
escribeCola (C [])     = "-"
escribeCola (C [x])    = show x
escribeCola (C (x:xs)) = show x ++ " | " ++ escribeCola (C xs)
 
-- Procedimiento de escritura de colas.
instance Show a => Show (Cola a) where
  show = escribeCola
 
-- Ejemplo de cola:
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    3 | 2 | 5
 
-- vacia es la cola vacía. Por ejemplo,
--    λ> vacia
--    -
vacia :: Cola a
vacia = C []
 
-- (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
--    λ> ej = inserta 2 (inserta 3 vacia)
--    λ> ej
--    3 | 2
--    λ> inserta 5 ej
--    3 | 2 | 5
inserta :: a -> Cola a -> Cola a
inserta x (C c) = C (c ++ [x])
 
-- (primero c) es el primer elemento de la cola c. Por ejemplo,
--    λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))
--    3
primero :: Cola a -> a
primero (C [])    = error "primero: cola vacia"
primero (C (x:_)) = x
 
-- (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
--    λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))
--    2 | 5
resto :: Cola a -> Cola a
resto (C (_:xs)) = C xs
resto (C [])     = error "resto: cola vacia"
 
-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,
--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False
--    esVacia vacia  == True
esVacia :: Cola a -> Bool
esVacia (C xs)  = null xs
 
-- Generador de colas                                          --
-- ==================
 
-- genCola es un generador de colas de enteros. Por ejemplo,
--    λ> sample genCola
--    -
--    -
--    -3 | 2
--    6 | 0 | 1
--    -5 | 0 | -5 | 0 | -4
--    2 | 9 | -6 | 9 | 0 | -1
--    -
--    11 | -5 | 5
--    -
--    16 | 6 | 15 | -3 | -9
--    11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13
genCola :: (Arbitrary a, Num a) => Gen (Cola a)
genCola = do
  xs <- listOf arbitrary
  return (foldr inserta vacia xs)
 
-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Cola a) where
  arbitrary = genCola
 
-- Propiedades de las colas
-- ========================
 
-- Las propiedades son
prop_colas1 :: Int -> Cola Int -> Bool
prop_colas1 x c =
  primero (inserta x vacia) == x &&
  resto (inserta x vacia) == vacia &&
  esVacia vacia &&
  not (esVacia (inserta x c))
 
prop_colas2 :: Int -> Cola Int -> Property
prop_colas2 x c =
  not (esVacia c) ==>
  primero (inserta x c) == primero c &&
  resto (inserta x c) == inserta x (resto c)
 
-- La comprobación es:
--    λ> quickCheck prop_colas1
--    +++ OK, passed 100 tests.
--    λ> quickCheck prop_colas2
--    +++ OK, passed 100 tests; 3 discarded.

2.3. Implementación de las colas mediante pares de listas

En esta implementación, 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).

Al dividir la lista en dos parte e invertir la segunda de ellas, esperamos hacer más eficiente las operaciones sobre las colas.

Impondremos también una restricción adicional sobre la representación: las colas serán representadas mediante pares (xs,ys) tales que si xs es vacía, entonces ys será también vacía. Esta restricción ha de ser conservada por los programas que crean colas.

La implementación se encuentra en el módulo ColaConDosListas.hs cuyo contenido es el siguiente:

module TAD.ColaConDosListas
  (Cola,
   vacia,      -- Cola a
   inserta,    -- a -> Cola a -> Cola a
   primero,    -- Cola a -> a
   resto,      -- Cola a -> Cola a
   esVacia,    -- Cola a -> Bool
  ) where
 
import Test.QuickCheck
 
-- Las colas como pares listas.
newtype Cola a = C ([a],[a])
 
-- (escribeCola p) es la cadena correspondiente a la cola p. Por
-- ejemplo,
--    λ> escribeCola (inserta 5 (inserta 2 (inserta 3 vacia)))
--    "3 | 2 | 5"
escribeCola :: Show a => Cola a -> String
escribeCola (C (xs,ys)) = aux (xs ++ reverse ys)
  where aux []     = "-"
        aux [z]    = show z
        aux (z:zs) = show z ++ " | " ++ aux zs
 
-- Procedimiento de escritura de colas.
instance Show a => Show (Cola a) where
  show = escribeCola
 
-- Ejemplo de cola:
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    3 | 2 | 5
 
-- vacia es la cola vacía. Por ejemplo,
--    λ>  vacia
--    -
vacia :: Cola a
vacia  = C ([],[])
 
-- (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    3 | 2 | 5
inserta :: a -> Cola a -> Cola a
inserta y (C (xs,ys)) = C (normaliza (xs,y:ys))
 
-- (normaliza p) es la cola obtenida al normalizar el par de listas
-- p. Por ejemplo,
--    normaliza ([],[2,5,3])   ==  ([3,5,2],[])
--    normaliza ([4],[2,5,3])  ==  ([4],[2,5,3])
normaliza :: ([a],[a]) -> ([a],[a])
normaliza ([], ys) = (reverse ys, [])
normaliza p        = p
 
-- (primero c) es el primer elemento de la cola c. Por ejemplo,
--    λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))
--    3
primero  :: Cola a -> a
primero (C (x:_,_)) = x
primero _           = error "primero: cola vacia"
 
-- (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
--    λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))
--    2 | 5
resto  :: Cola a -> Cola a
resto (C ([],[]))   = error "resto: cola vacia"
resto (C (_:xs,ys)) = C (normaliza (xs,ys))
resto (C ([],_:_))  = error "Imposible"
 
-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,
--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False
--    esVacia vacia == True
esVacia :: Cola a -> Bool
esVacia (C (xs,_)) = null xs
 
-- (valida c) se verifica si la cola c es válida; es decir, si
-- su primer elemento es vacío entonces también lo es el segundo. Por
-- ejemplo,
--    valida (C ([2],[5]))  ==  True
--    valida (C ([2],[]))   ==  True
--    valida (C ([],[5]))   ==  False
valida :: Cola a -> Bool
valida (C (xs,ys)) = not (null xs) || null ys
 
-- ---------------------------------------------------------------------
-- Igualdad de colas                                                  --
-- ---------------------------------------------------------------------
 
-- (elementos c) es la lista de los elementos de la cola c en el orden de
-- la cola. Por ejemplo,
--    λ> elementos (inserta 5 (inserta 2 (inserta 3 vacia)))
--    [3,2,5]
elementos :: Cola a -> [a]
elementos (C (xs,ys)) = xs ++ reverse ys
 
-- (igualColas c1 c2) se verifica si las colas c1 y c2 son iguales. Por
-- ejemplo,
--    igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2]))   ==  True
--    igualColas (C ([3,2],[5,4,7])) (C ([],[5,4,7,2,3]))  ==  False
igualColas :: Eq a => Cola a -> Cola a -> Bool
igualColas c1 c2 =
  valida c1 &&
  valida c2 &&
  elementos c1 == elementos c2
 
instance Eq a => Eq (Cola a) where
  (==) = igualColas
 
-- Generador de colas                                          --
-- ==================
 
-- genCola es un generador de colas de enteros. Por ejemplo,
--    λ> sample genCola
--    -
--    -
--    -3 | 2
--    6 | 0 | 1
--    -5 | 0 | -5 | 0 | -4
--    2 | 9 | -6 | 9 | 0 | -1
--    -
--    11 | -5 | 5
--    -
--    16 | 6 | 15 | -3 | -9
--    11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13
genCola :: (Arbitrary a, Num a) => Gen (Cola a)
genCola = do
  xs <- listOf arbitrary
  return (foldr inserta vacia xs)
 
-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Cola a) where
  arbitrary = genCola
 
-- Propiedades de las colas
-- ========================
 
-- Las propiedades son
prop_colas1 :: Int -> Cola Int -> Bool
prop_colas1 x c =
  primero (inserta x vacia) == x &&
  resto (inserta x vacia) == vacia &&
  esVacia vacia &&
  not (esVacia (inserta x c))
 
prop_colas2 :: Int -> Cola Int -> Property
prop_colas2 x c =
  not (esVacia c) ==>
  primero (inserta x c) == primero c &&
  resto (inserta x c) == inserta x (resto c)
 
-- La comprobación es:
--    λ> quickCheck prop_colas1
--    +++ OK, passed 100 tests.
--    λ> quickCheck prop_colas2
--    +++ OK, passed 100 tests; 3 discarded.

2.4. Implementación de las colas mediante sucesiones

La implementación (que usa la librería Data.Sequence) se encuentra en el módulo ColaConSucesiones.hs cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}
 
module TAD.ColaConSucesiones
  (Cola,
   vacia,   -- Cola a
   inserta, -- a -> Cola a -> Cola a
   primero, -- Cola a -> a
   resto,   -- Cola a -> Cola a
   esVacia, -- Cola a -> Bool
  ) where
 
import Data.Sequence as S
import Test.QuickCheck
 
-- Colas como sucesiones:
newtype Cola a = C (Seq a)
  deriving Eq
 
-- (escribeCola c) es la cadena correspondiente a la cola c. Por
-- ejemplo,
--    escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == "3 | 2 | 5"
escribeCola :: Show a => Cola a -> String
escribeCola (C xs) = case viewl xs of
    EmptyL   -> "-"
    x :< xs' -> case viewl xs' of
        EmptyL -> show x
        _      -> show x ++ " | " ++ escribeCola (C xs')
 
-- Procedimiento de escritura de colas.
instance Show a => Show (Cola a) where
  show = escribeCola
 
-- Ejemplo de cola:
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    3 | 2 | 5
 
-- vacia es la cola vacía. Por ejemplo,
--    λ> vacia
--    C []
vacia :: Cola a
vacia = C empty
 
-- (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
--    λ> ej = inserta 2 (inserta 3 vacia)
--    λ> ej
--    3 | 2
--    λ> inserta 5 ej
--    3 | 2 | 5
inserta :: a -> Cola a -> Cola a
inserta x (C xs) = C (xs |> x )
 
-- (primero c) es el primer elemento de la cola c. Por ejemplo,
--    λ> primero (inserta 5 (inserta 2 (inserta 3 vacia)))
--    3
primero :: Cola a -> a
primero (C xs) = case viewl xs of
  EmptyL -> error "primero de la pila vacia"
  x :< _ -> x
 
-- (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
--    λ> resto (inserta 5 (inserta 2 (inserta 3 vacia)))
--    2 | 5
resto :: Cola a -> Cola a
resto (C xs) = case viewl xs of
  EmptyL   -> error "resto la pila vacia"
  _ :< xs' -> C xs'
 
-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,
--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False
--    esVacia vacia  == True
esVacia :: Cola a -> Bool
esVacia (C xs)  = S.null xs
 
-- Generador de colas                                          --
-- ==================
 
-- genCola es un generador de colas de enteros. Por ejemplo,
--    λ> sample genCola
--    -
--    2 | -2
--    0 | 0 | 0 | 4
--    -
--    2
--    -1 | -6 | 9
--    12 | -12 | -12 | 7 | -2 | -3 | 5 | -8 | -3 | -9 | -6
--    -11 | -5 | -7 | -8 | -10 | 8 | -9 | -7 | 6 | -12 | 8 | -9 | -1
--    -16 | -12
--    -17 | -17 | 1 | 2 | -15 | -15 | -13 | 8 | 13 | -12 | 15
--    -16 | -18
genCola :: (Arbitrary a, Num a) => Gen (Cola a)
genCola = do
  xs <- listOf arbitrary
  return (foldr inserta vacia xs)
 
-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Cola a) where
  arbitrary = genCola
 
-- Propiedades de las colas
-- ========================
 
-- Las propiedades son
prop_colas1 :: Int -> Cola Int -> Bool
prop_colas1 x c =
  primero (inserta x vacia) == x &&
  resto (inserta x vacia) == vacia &&
  esVacia vacia &&
  not (esVacia (inserta x c))
 
prop_colas2 :: Int -> Cola Int -> Property
prop_colas2 x c =
  not (esVacia c) ==>
  primero (inserta x c) == primero c &&
  resto (inserta x c) == inserta x (resto c)
 
-- La comprobación es:
--    λ> quickCheck prop_colas1
--    +++ OK, passed 100 tests.
--    λ> quickCheck prop_colas2
--    +++ OK, passed 100 tests; 9 discarded.

3. Las colas en Python

3.1. El tipo abstracto de las colas en Python

La implementación se encuentra en el módulo cola.py cuyo contenido es el siguiente:

__all__ = [
    'Cola',
    'vacia',
    'inserta',
    'primero',
    'resto',
    'esVacia',
    'colaAleatoria'
]
from src.TAD.colaConListas import (Cola, colaAleatoria, esVacia, inserta,
                                   primero, resto, vacia)
# from src.TAD.colaConDosListas import (Cola, colaAleatoria, esVacia, inserta,
#                                       primero, resto, vacia)
# from src.TAD.colaConDeque import (Cola, vacia, inserta, primero, resto,
#                                   esVacia, colaAleatoria)

Para usar el TAD hay que usar una implementación 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ándola y comentando las otras.

3.2. Implementación de las colas mediante listas

La implementación se encuentra en el módulo colaConListas.py en el que se define la clase Cola con los siguientes métodos:

  • inserta(x) añade x al final de la cola.
  • primero() es el primero de la cola.
  • resto() elimina el primero de la cola.
  • esVacia() se verifica si la cola es vacía.

Por ejemplo,

   >>> c = Cola()
   >>> c
   -
   >>> c.inserta(5)
   >>> c.inserta(2)
   >>> c.inserta(3)
   >>> c.inserta(4)
   >>> c
   5 | 2 | 3 | 4
   >>> c.primero()
   5
   >>> c.resto()
   >>> c
   2 | 3 | 4
   >>> c.esVacia()
   False
   >>> c = Cola()
   >>> c.esVacia()
   True

Además se definen las correspondientes funciones. Por ejemplo,

   >>> vacia()
   -
   >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))
   5 | 2 | 3 | 4
   >>> primero(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   5
   >>> resto(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   2 | 3 | 4
   >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   False
   >>> esVacia(vacia())
   True

Finalmente, se define un generador aleatorio de colas y se comprueba que las colas cumplen las propiedades de su especificación.

__all__ = [
    'Cola',
    'vacia',
    'inserta',
    'primero',
    'resto',
    'esVacia',
    'colaAleatoria'
]
 
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar
 
from hypothesis import assume, given
from hypothesis import strategies as st
 
A = TypeVar('A')
 
# Clase de las colas mediante listas
# ==================================
 
@dataclass
class Cola(Generic[A]):
    _elementos: list[A] = field(default_factory=list)
 
    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la cola separados por " | ".
        Si la cola está vacía, devuelve "-".
        """
        if not self._elementos:
            return '-'
        return ' | '.join(str(x) for x in self._elementos)
 
    def inserta(self, x: A) -> None:
        """
        Inserta el elemento x al final de la cola.
        """
        self._elementos.append(x)
 
    def esVacia(self) -> bool:
        """
        Comprueba si la cola está vacía.
 
        Devuelve True si la cola está vacía, False en caso contrario.
        """
        return not self._elementos
 
    def primero(self) -> A:
        """
        Devuelve el primer elemento de la cola.
        """
        return self._elementos[0]
 
    def resto(self) -> None:
        """
        Elimina el primer elemento de la cola
        """
        self._elementos.pop(0)
 
# Funciones del tipo de las listas
# ================================
 
def vacia() -> Cola[A]:
    """
    Crea y devuelve una cola vacía de tipo A.
    """
    c: Cola[A] = Cola()
    return c
 
def inserta(x: A, c: Cola[A]) -> Cola[A]:
    """
    Inserta un elemento x en la cola c y devuelve una nueva cola con
    el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux
 
def esVacia(c: Cola[A]) -> bool:
    """
    Devuelve True si la cola está vacía, False si no lo está.
    """
    return c.esVacia()
 
def primero(c: Cola[A]) -> A:
    """
    Devuelve el primer elemento de la cola c.
    """
    return c.primero()
 
def resto(c: Cola[A]) -> Cola[A]:
    """
    Elimina el primer elemento de la cola c y devuelve una copia de la
    cola resultante.
    """
    _aux = deepcopy(c)
    _aux.resto()
    return _aux
 
# Generador de colas
# ==================
 
def colaAleatoria() -> st.SearchStrategy[Cola[int]]:
    """
    Genera una estrategia de búsqueda para generar colas 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 cola.
    """
    return st.lists(st.integers()).map(Cola)
 
# Comprobación de las propiedades de las colas
# ============================================
 
# Las propiedades son
@given(c=colaAleatoria(), x=st.integers())
def test_cola1(c: Cola[int], x: int) -> None:
    assert primero(inserta(x, vacia())) == x
    assert resto(inserta(x, vacia())) == vacia()
    assert esVacia(vacia())
    assert not esVacia(inserta(x, c))
 
@given(c=colaAleatoria(), x=st.integers())
def test_cola2(c: Cola[int], x: int) -> None:
    assume(not esVacia(c))
    assert primero(inserta(x, c)) == primero(c)
    assert resto(inserta(x, c)) == inserta(x, resto(c))
 
# La comprobación es
#    > poetry run pytest -q colaConListas.py
#    1 passed in 0.24s

3.3. Implementación de las colas mediante pares de listas

La implementación se encuentra en el módulo colaConDosListas.py cuyo contenido es

__all__ = [
    'Cola',
    'vacia',
    'inserta',
    'primero',
    'resto',
    'esVacia',
    'colaAleatoria'
]
 
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar
 
from hypothesis import assume, given
from hypothesis import strategies as st
 
A = TypeVar('A')
 
# Clase de las colas mediante listas
# ==================================
 
@dataclass
class Cola(Generic[A]):
    _primera: list[A] = field(default_factory=list)
    _segunda: list[A] = field(default_factory=list)
 
    def _elementos(self) -> list[A]:
        """
        Devuelve una lista con los elementos de la cola en orden.
        """
        return self._primera + self._segunda[::-1]
 
    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la cola separados por " | ".
        Si la cola está vacía, devuelve "-".
        """
        elementos = self._elementos()
        if not elementos:
            return "-"
        return " | ".join(map(str, elementos))
 
    def __eq__(self, c) -> bool:
        """
        Comprueba si la cola actual es igual a otra cola.
        Se considera que dos colas son iguales si tienen los mismos
        elementos en el mismo orden.
 
        Parámetro:
        - c (Cola): La cola con la que se va a comparar.
 
        Devuelve True si las dos colas son iguales, False en caso
        contrario.
        """
        return self._elementos() == c._elementos()
 
    def inserta(self, y: A) -> None:
        """
        Inserta el elemento y en la cola.
        """
        xs = self._primera
        ys = self._segunda
        # Si no hay elementos en la primera lista, se inserta en la segunda
        if not xs:
            ys.insert(0, y)
            # Se invierte la segunda lista y se asigna a la primera
            self._primera = ys[::-1]
            self._segunda = []
        else:
            # Si hay elementos en la primera lista, se inserta en la segunda
            ys.insert(0, y)
 
    def esVacia(self) -> bool:
        """
        Devuelve si la cola está vacía.
        """
        return not self._primera
 
    def primero(self) -> A:
        """
        Devuelve el primer elemento de la cola.
        """
        return self._primera[0]
 
    def resto(self) -> None:
        """
        Elimina el primer elemento de la cola.
        """
        xs = self._primera
        ys = self._segunda
        del xs[0]
        if not xs:
            self._primera = ys[::-1]
            self._segunda = []
 
# Funciones del tipo de las listas
# ================================
 
def vacia() -> Cola[A]:
    """
    Crea y devuelve una cola vacía de tipo A.
    """
    c: Cola[A] = Cola()
    return c
 
def inserta(x: A, c: Cola[A]) -> Cola[A]:
    """
    Inserta un elemento x en la cola c y devuelve una nueva cola con
    el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux
 
def esVacia(c: Cola[A]) -> bool:
    """
    Devuelve True si la cola está vacía, False si no lo está.
    """
    return c.esVacia()
 
def primero(c: Cola[A]) -> A:
    """
    Devuelve el primer elemento de la cola c.
    """
    return c.primero()
 
def resto(c: Cola[A]) -> Cola[A]:
    """
    Elimina el primer elemento de la cola c y devuelve una copia de la
    cola resultante.
    """
    _aux = deepcopy(c)
    _aux.resto()
    return _aux
 
# Generador de colas
# ==================
 
def colaAleatoria() -> st.SearchStrategy[Cola[int]]:
    """
    Genera una estrategia de búsqueda para generar colas 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 cola.
    """
    return st.lists(st.integers()).map(Cola)
 
# Comprobación de las propiedades de las colas
# ============================================
 
# Las propiedades son
@given(c=colaAleatoria(), x=st.integers())
def test_cola1(c: Cola[int], x: int) -> None:
    assert primero(inserta(x, vacia())) == x
    assert resto(inserta(x, vacia())) == vacia()
    assert esVacia(vacia())
    assert not esVacia(inserta(x, c))
 
@given(c=colaAleatoria(), x=st.integers())
def test_cola2(c: Cola[int], x: int) -> None:
    assume(not esVacia(c))
    assert primero(inserta(x, c)) == primero(c)
    assert resto(inserta(x, c)) == inserta(x, resto(c))
 
# La comprobación es
#    > poetry run pytest -q colaConListas.py
#    2 passed in 0.40s

3.4. Implementación de las colas mediante deque

La implementación (que usa la librería deque) se encuentra en el módulo colaConDeque.py y su contenido es el siguiente:

__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
Haskell y Python
,

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.