Pilas

Una pila o stack es una colección ordenada de elementos homogéneos en la que “hay” restricciones de acceso, los elementos solo pueden ser ingresados o retirados por un solo extremo, denominado top de la pila.

La Pila tiene un comportamiento LIFO (Last In First Out). Así el último elemento que se incorpora a la estructura, es el único que se puede consultar y es el primero a ser eliminado.

Una Pila es aplicable cuando se desea tratar a los elementos en el orden estrictamente inverso al que entraron.

Ej: utilizar ctrl Z

Pila dinámica: Tiene restricciones de ingreso y egreso de elementos pudiéndolo hacer solamente por un extremo que indica el puntero Top. Al ser dinámica se implementa sobre una lista de nodos, no tiene límite teórico de crecimiento y no hay necesidad de control que llego al máximo de capacidad.

Pila estática: Es una estructura de comportamiento LIFO y al ser estática se implementa sobre un array con la particularidad que se maneja la posición con un puntero Top. Crece y decrece por medio de este puntero indicando el último ingresado y siendo el punto de extracción del primero. Cant. max elementos del array.

Especificacion TAD
Pila
  usa Booleanos, Elementos
  tipos pila

operaciones
  pilaVacia: -> pila;
  CrearPila() -> pilaVacia
  Push(pila,elem) -> pila
  Pop(pila) -> pila
  Empty(pila) -> bool
  Peek(pila) -> elem

ecuaciones [Dados S:Pila; e:elem]
  Empty(pilaVacia) = Verdadero;
  Empty(CrearPila()) = Verdadero;
  Empty(Push(S,e)) = Falso
  Peek(pilaVacia) => error ;
  Peek(Push(S,e)) = e
  Pop(pilaVacia) => error ;
  Pop(Push(S,e)) = S

FinEspecificacion

Cuerpo de una pila

Sobre un vector

MaxPila = n //(Máximo valor del array, máximo posible de la pila)
Stack {
  cuerpo = array[1..MaxPila] de elem
  top = [0..MaxPila]
}

Sobre una Lista de nodos

Stack {
  cuerpo = lista (colección de nodos)
  top = puntNodo
}

CrearPila (crea una pila vacía)

Sobre un vector

CrearPila (): pila {
  S->Top = 0
  return S
}

Sobre una Lista de nodos

CrearPila (): pila {
  S->Top = CrearLista()
  return S
}

Peek (lee el tope de la pila)

Sobre un vector

Peek (S:pila) {
  if (Empty(s))
    "error"
  else
    reutrn S->cuerpo[S->top]
  end-if
}

Sobre una Lista de nodos

Peek (S:pila) {
  if (Empty(s))
    "error"
  else
    reutrn Contenido(S->top)
  end-if
}

Push (inserta elemento en pila)

Sobre un vector

Push (S:pila, e:elemento) {
  if (Full(S))
    "error"
  else
    S->top = S->top+1
    S->cuerpo[S->top] = e
  end-if
}

Sobre una Lista de nodos

Push (S:pila, e:elemento) {
  if (Empty(S))
    S->Top = PrimerElemLista(S->Top,e)
  else
    InsAntes(S->top,e)
    S->top = Anterior(S->top) 
  end-if
}

Pop (remueve elemento de la pila)

Sobre un vector

Pop (S:pila):elementos {
  if (Empty(S))
    "error"
  else
    x = S->cuerpo[S->top]
    S->top = S->top-1
    return x
  end-if
}

Sobre una Lista de nodos

Pop (S:pila):elementos {
  if (Empty(S))
    "error"
  else
    p = Siguiente(S->top)
    X = Borrar(S->top)
    S->top = p
    return x
  end-if
}

Empty (devuelve si la pila se encuentra vacía (True o False)

Sobre un vector

Empty (S:pila):boolean {
  if (Siguiente(S->top) == null)
    return true
  else
    return false
  end-if
}

Sobre una Lista de nodos

Empty (S:pila):boolean {
  if (EsListaVacia[S->top])
    return true
  else
    return false
  end-if
}

Full (devuelve si la pila se encuentra llena  (True o False)

Full (S:pila):boolean {
  if (S->top == MaxPila)
    return true
  else
    return false
  end-if
}