El tipo abstracto de datos de las colas

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

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

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.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

{-# 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.

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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

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.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

{-# 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)

__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

>>> c = Cola()

>>> c

>>> c.inserta(5)

>>> c.inserta(2)

>>> c.inserta(3)

>>> c.inserta(4)

>>> c

5 | 2 | 3 | 4

>>> c.primero()

>>> 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

>>> vacia()

>>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))

5 | 2 | 3 | 4

>>> primero(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))

>>> 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

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

134

__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

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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

__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

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

El tipo abstracto de datos de las colas

1. El tipo abstracto de datos de las colas

2. Las colas en Haskell

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

2.2. Implementación de las colas mediante listas

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

2.4. Implementación de las colas mediante sucesiones

3. Las colas en Python

3.1. El tipo abstracto de las colas en Python

3.2. Implementación de las colas mediante listas

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

3.4. Implementación de las colas mediante deque

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

1. El tipo abstracto de datos de las colas

2. Las colas en Haskell

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

2.2. Implementación de las colas mediante listas

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

2.4. Implementación de las colas mediante sucesiones

3. Las colas en Python

3.1. El tipo abstracto de las colas en Python

3.2. Implementación de las colas mediante listas

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

3.4. Implementación de las colas mediante deque

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico