Pilas acotadas (estructura de datos)

Pilas acotadas (estructura de datos)

Pilas acotadas (estructura de datos)

Una pila acotada es una estructura de datos de tipo LIFO (el último elemento en entrar, es el primero en salir) cuyo tama o máximo queda limitado en su especificación. Una pila acotada cuenta con opreaciones básicas:

  • Crear: se crea la pila vacía.
  • Apilar: se añade un elemento a la pila.(push)
  • Desapilar: se elimina el elemento frontal de la pila.(pop)
  • Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
  • Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.
  • Llena: devuelve cierto si la pila está llena o falso en caso contrario.

Lógicamente no podremos apilar en una pila que está llena.

Implementación

Para ilustrar exponemos la implementación de un pila acotada.

En MAUDE

Necesitaremos una teoría para definir el tama o máximo de la pila.

fth CONSTANTE is
  protecting NAT .
  op cte: -> NAT .
endfth

Pasamos a definir la pila acotada parametrizada.

fmod PILA-ACOTADA {X :: TRIV , AC :: CONSTANTE} is
  protecting NAT .
  sorts PilaAC{X , AC} PilaACNV{X , AC} .
  subsort PilaACNV{X , AC} < PilaAC{X , AC} .
  *** generadores
  op crear : -> PilaAC{X , AC} [ctor] .
  op apilar : X$Elt PilaAC{X , AC} -> PilaACNV{X , AC} [ctor] .
  *** constructores
  op desapilar : PilaAC{X , AC} -> PilaAC{X , AC} .
  *** selectores
  op cima : PilaACNV{X , AC} -> X$Elt .
  op longitud : PilaAC{X , AC} -> Nat .
  op estaLlena? : PilaAC{X , AC} -> Bool .
  *** variables
  var P : PilaAC{X , AC} .
  var E : X$Elt .
  *** ecuaciones impurificadoras
  ceq apilar (E, P) = P if estaLlena?(P) .
  eq desapilar (crear) = crear .
  ceq desapilar (apilar(E, P)) = P if not estaLlena?(P) .
  ceq cima (apilar(E, P)) = E if not estaLlena?(P) .
  eq longitud (crear) = 0 .                    
  ceq longitud (apilar(E, P)) = 1 + longitud (P)
     if not estaLlena?(P) .                      
  eq estaLlena?(P) = longitud (P) >= cte .;
endfm

Véase también

  • Listas
  • Pilas
  • Colas

Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Pila (informática) — Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”