Trabajo y suerte

Una pila es un tipo especial de lista en la que todas las inserciones y supresiones tienen lugar en un extremo denominado tope. A las pilas se les llama también “listas LIFO” (last in first out) o listas “ultimo en entrar, primero en salir”. El modelo intuitivo de una pila es precisamente una pila de fichas de póquer puesta sobre una mesa, o de libros sobre el piso, o de platos en unaestantería, situaciones todas en las que solo es conveniente quitar o agregar un objeto del extremo superior de la pila, al que se denominara en lo sucesivo ”tope”. Un tipo de datos abstracto de la familia PILA incluye a menudo las cinco operaciones siguientes:
1. ANULA(P) convierte la pila P en una pila vacía. Esta operación es exactamente la misma que para las listas generales.
2. TOPE(P)devuelve el valor del elemento de la parte superior de la pila P. Si se identifica la parte superior de una pila con la posición 1, como suele hacerse, entonces TOPE(P) puede escribirse en función de operaciones con listas como RECUPERA(PRIMERO(P), P).
3. SACA(P), en ingles POP, suprime el elemento superior de la pila, es decir, equivale a SUPRIME(PRIMERO(P), P). Algunas veces resulta convenienteimplantar SACA como una función que devuelve el elemento que acaba de suprimir, aunque aquí no se hará eso.
4. METE(x, P), en ingles PUSH, inserta el elemento x en la parte superior de la pila P. El anterior tope se convierte en el siguiente elemento, y así sucesivamente. En función de operaciones primitivas con listas, esta operación es INSERTA(x, PRIMERO (P), P).
5. VACIA(P) devuelveverdadero si la pila Presta vaciá, y falso en caso contrario.
Los editores de textos siempre permiten usar un carácter(por ejemplo, back-space) como carácter de borrado que cancela el carácter anterior no cancelado. Por ejemplo, si “#” es el carácter de borrado, la cadena abc#d##e es en realidad la cadena ae. El primer “#” cancela la c, el segundo la d y el tercero la b.
Los editores de texto tambiéntienen un carácter de eliminación de línea, que cancela todos los caracteres anteriores de la línea actual. A efectos de este ejemplo, se usara “@” como carácter de eliminación de línea.
Un editor puede procesar una línea de texto usando una pila. El editor lee un carácter a la vez. Si el carácter leído no es de borrado ni de eliminación de línea, el editor lo mete en la pila. Si el carácter es deborrado, el editor saca un carácter de la pila, y si es de eliminación de línea, vacía la pila.

Programa que logra el efecto de los caracteres de borrado y cancelación de línea.

procedure EDITA;
var
P: PILA;
c: char;
begin
ANULA (P);
while not eoln do begin
read(c);
if c = ‘# then
SACA (P)
else if c = ‘@ then
ANULA (P)
else { c esun carácter normal }
METE (c, P)
end;
imprime P en orden inverso
end; { EDITA }

En este programa, el tipo PILA debe declararse como una lista de caracteres. el proceso de escribir la pila en orden inverso en la ultima línea del programa tiene un objetivo: sacar de la pila un carácter a la vez da como resultado la inversión de la línea. Algunas realizaciones de pilas, como labasada en arreglos, que se analizara a continuación, permiten escribir un procedimiento sencillo para imprimir los caracteres de la pila a partir de la base. Sin embargo, en general, para invertir una pila, cada elemento debe sacarse y meterse en otra pila; luego, los elementos pueden sacarse de la segunda pila e imprimirse en el orden en que se sacan.

Realización de pilas basadas en arreglosTodas las realizaciones de listas descritas sirven para pilas, puesto que una pila con sus operaciones es un caso especial de lista con sus operaciones. La representación de una pila como lista enlazada es sencilla, pues METE y SACA operan solo con la celda de encabezamiento y con la primera celda de la lista. De hecho, los encabezamientos pueden ser apuntadores o cursores, mas que celdas completas,...