miniatura|Do mesmo xeito que cunha pila de pratos, engadir ou retirar só é práctico pola parte superior. miniatura|350px|dereita|alt=Representación simple dunha pila en execución.|Representación simple dunha pila en execución coas operacións push e pop.
En ciencias da computación, unha pila é un tipo de dato abstracto que serve como colección de elementos con dúas operacións principais: Push (apilar), que engade un elemento á colección, e Pop (desapilar), que retira o elemento engadido máis recentemente. Ademais, unha operación de vista (peek) pode, sen modificar a pila, devolver o valor do último elemento engadido (o da cima). O nome pila é unha analoxía cun conxunto de obxectos apilados un sobre outro, como unha pila de pratos.
A orde en que os elementos se engaden ou retiran dunha pila descríbese como último en entrar, primeiro en saír, abreviada como LIFO (do inglés last in, first out).Pola contra, unha cola funciona como primeiro en entrar, primeiro en saír (FIFO). Como nunha pila de obxectos físicos, esta estrutura fai doado retirar un elemento da cima, pero acceder a un dato máis profundo na pila require tipicamente retirar antes varios elementos.
Considerada unha colección secuencial, unha pila ten un extremo que é a única posición onde poden ocorrer as operacións de apilar e desapilar, a cima, e está fixada polo outro extremo, a base. Unha pila pódese implementar, por exemplo, cunha lista ligada simple cun punteiro ao elemento da cima.
Unha pila pode implementarse cunha capacidade limitada. Se a pila está chea e non ten espazo para aceptar outro elemento, está nun estado de desbordamento de pila (stack overflow).
Historia As pilas entraron na literatura informática en 1946, cando Alan Turing usou os termos «bury» e «unbury» como xeito de chamar a subrutinas e retornar delas. Presentado o 19 de marzo de 1946 ante o Executive Committee of the National Physical Laboratory (Reino Unido). As subrutinas e unha pila de dous niveis xa se implementaran no Z4 de Konrad Zuse en 1945.
Klaus Samelson e Friedrich L. Bauer, da Universidade Técnica de Múnic, propuxeron a idea dunha pila chamada Operationskeller («adega operacional») en 1955 e presentaron unha patente en 1957. En marzo de 1988, cando Samelson xa falecera, Bauer recibiu o Computer Pioneer Award do IEEE pola invención do principio de pila. Conceptos similares foron desenvolvidos de forma independente por Charles Leonard Hamblin na primeira metade de 1954 e por Wilhelm Kämmerer coa súa automatisches Gedächtnis («memoria automática») en 1958.
As pilas descríbense a miúdo coa analoxía dunha pila de pratos nunha cafetería. Os pratos limpos colócanse enriba da pila, empurrando os que xa están. Ao retirar o prato de arriba, o de abaixo elévase para ser a nova cima.
Operacións non esenciais En moitas implementacións, unha pila ten máis operacións cás esenciais «push» e «pop». Un exemplo de operación non esencial é «top of stack» ou «peek», que observa o elemento da cima sen retiralo. Como se pode descompor nun «pop» seguido dun «push» do mesmo dato, non se considera esencial. Se a pila está baleira, prodúcese unha condición de subdesbordamento (underflow) ao executar «peek» ou «pop». Ademais, moitas implementacións inclúen operacións de conveniencia, como comprobar se a pila está baleira ou devolver o seu tamaño.
Pilas de software miniatura|200px|alt=Diagrama UML dunha pila.|Diagrama UML dunha pila.
Implementación Unha pila pódese implementar doadamente cun vector ou cunha lista ligada, pois é un caso particular dunha lista. En calquera dos dous casos, o que identifica a estrutura de datos como pila non é a implementación senón a interface: só se permite apilar ou desapilar elementos, con poucas operacións auxiliares. A continuación amósanse as dúas implementacións con pseudocódigo.
Vector Un vector pódese usar para implementar unha pila (limitada) como segue. O primeiro elemento, normalmente no desprazamento cero, é a base, de modo que array é o primeiro en entrar e o último en saír. O programa debe levar a conta do tamaño da pila, cunha variable top que rexistra o número de elementos apilados, apuntando así ao lugar do vector onde se ha inserir o seguinte. A pila pódese implementar como unha estrutura de tres elementos:
structure stack: maxsize: integer top: integer items: array of item
procedure initialize(stk: stack, size: integer): stk.items ← new array of size items, initially empty stk.maxsize ← size stk.top ← 0
A operación push engade un elemento e incrementa o índice top, tras comprobar o desbordamento: miniatura|200px|alt=Operación push nunha pila baseada en vector.|Animación da operación push nunha pila baseada en vector, do subdesbordamento ao desbordamento. procedure push(stk: stack, x: item): if stk.top = stk.maxsize: report overflow error else: stk.items[stk.top] ← x stk.top ← stk.top + 1
Do mesmo xeito, pop decrementa o índice top tras comprobar o subdesbordamento e devolve o elemento que estaba na cima: miniatura|200px|alt=Operación pop nunha pila baseada en vector.|Animación da operación pop nunha pila baseada en vector, do estado cheo ao subdesbordamento. procedure pop(stk: stack): if stk.top = 0: report underflow error else: stk.top ← stk.top − 1 r ← stk.items[stk.top] return r
Cun vector dinámico pódese implementar unha pila que medre ou diminúa canto cómpre. O tamaño da pila é simplemente o tamaño do vector dinámico, que é unha implementación moi eficiente, xa que engadir ou retirar elementos ao final dun vector dinámico require tempo amortizado O(1).
Lista ligada Outra opción é usar unha lista ligada simple. A pila é entón un punteiro á «cabeza» da lista, acaso cun contador do tamaño:
structure frame: data: item next: frame or nil
structure stack: head: frame or nil size: integer
procedure initialize(stk: stack): stk.head ← nil stk.size ← 0
As operacións de apilar e desapilar fanse na cabeza da lista; nesta implementación non hai desbordamento (agás que se esgote a memoria): miniatura|200px|alt=Operación push nunha pila baseada en lista ligada.|Animación da operación push nunha pila baseada en lista ligada. procedure push(stk: stack, x: item): newhead ← new frame newhead.data ← x newhead.next ← stk.head stk.head ← newhead stk.size ← stk.size + 1 miniatura|200px|alt=Operación pop nunha pila baseada en lista ligada.|Animación da operación pop nunha pila baseada en lista ligada. procedure pop(stk: stack): if stk.head = nil: report underflow error else: r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 return r
Pilas e linguaxes de programación Algunhas linguaxes, como Perl, LISP, JavaScript e Python, inclúen as operacións de pila push e pop nos seus tipos de lista/vector estándar. Algunhas linguaxes, en particular as da familia Forth (incluído PostScript), están deseñadas arredor de pilas definidas pola linguaxe, directamente visibles e manipulables polo programador.
O seguinte é un exemplo de manipulación dunha pila en Common Lisp: > (setf stack (list 'a 'b 'c)) ;; fixar a variable "stack" (A B C) > (pop stack) ;; obter o elemento da cima (o máis á esquerda) A > stack ;; comprobar o valor de stack (B C) > (push 'new stack) ;; apilar un novo elemento (NEW B C)
Varios tipos de contedor da biblioteca estándar de C++ teñen operacións push_back() e pop_back() con semántica LIFO; ademais, a clase modelo std::stack adapta contedores existentes para fornecer unha API restrinxida con só operacións push/pop. PHP ten unha clase SplStack. A biblioteca de Java contén unha clase Stack, especialización de Vector. A continuación, un programa de exemplo en Java que usa esa clase:
package org.wikipedia.examples;
import java.util.Stack;
public class Example { public static void main(String[] args) { Stack<Character> stack = new Stack<>(); stack.push('a'); // Insertar 'a' na pila stack.push('b'); // Insertar 'b' na pila stack.push('c'); // Insertar 'c' na pila stack.push('d'); // Insertar 'd' na pila System.out.println(stack.peek()); // Imprime a cima da pila ('d') stack.pop(); // retirar a cima ('d') stack.pop(); // retirar a seguinte cima ('c')
Algúns procesadores, como o PDP-11, o VAX e a serie Motorola 68000, teñen modos de direccionamento útiles para a manipulación de pila. O seguinte código ensamblador do PDP-11 apila dous números e sómaos, deixando o resultado na pila.
; Suponse que R0 apunta a unha área de pila ; -(R0) predecrementa o punteiro, reservando un elemento ; (R0)+ posincrementa o punteiro, retirando un elemento ; MOV #12,-(R0) ; Apilar 12 MOV #34,-(R0) ; Apilar 34 ADD (R0)+,(R0) ; Desapilar 34 e sumarllo a 12 ; deixando o resultado na pila
Pila de hardware Un uso común das pilas no nivel da arquitectura é a asignación e o acceso á memoria.
Arquitectura básica dunha pila Unha pila típica é unha área de memoria cunha orixe fixa e un tamaño variable. Inicialmente o tamaño é cero. Un punteiro de pila (normalmente un rexistro do procesador) apunta á localización referenciada máis recentemente; cando o tamaño é cero, apunta á orixe.
As dúas operacións aplicables a todas as pilas son: Unha operación push: a dirección do punteiro de pila axústase polo tamaño do dato e escríbese un dato na localización apuntada. Unha operación pop ou pull: lese o dato da localización actual á que apunta o punteiro e o punteiro móvese a unha distancia correspondente ao tamaño dese dato.
Hai moitas variacións do principio básico das operacións de pila. Cada pila ten unha localización fixa en memoria na que comeza. A medida que se engaden datos, o punteiro de pila desprazase para indicar a extensión actual da pila, que se expande afastándose da orixe.
Os punteiros de pila poden apuntar á orixe dunha pila ou a un rango limitado de direccións por riba ou por debaixo dela (segundo a dirección de crecemento); con todo, o punteiro de pila non pode cruzar a orixe. Se unha operación pop fai que o punteiro pase máis alá da orixe, prodúcese un subdesbordamento de pila. Se unha operación push fai que o punteiro se incremente ou decremente máis alá da extensión máxima da pila, prodúcese un desbordamento de pila.
Algúns contornos que dependen moito das pilas poden fornecer operacións adicionais, por exemplo: Duplicate: desapílase o elemento da cima e apílase dúas veces, de xeito que quedan dúas copias do antigo elemento da cima. Peek: inspecciónase (ou devólvese) o elemento da cima, pero o punteiro e o tamaño da pila non cambian. Tamén se chama operación top. Swap ou exchange: os dous elementos da cima intercambian as súas posicións. Rotate (ou Roll): os elementos da cima desprázanse de forma rotatoria.
As pilas visualízanse a miúdo medrando de abaixo arriba. Tamén se poden visualizar medrando de esquerda a dereita, coa cima na parte máis á dereita, ou mesmo de arriba abaixo. O importante é que a base da pila estea nunha posición fixa.
Unha pila represéntase normalmente nos ordenadores por un bloque de celas de memoria, coa «base» nunha localización fixa e o punteiro de pila coa dirección da cela actual da «cima». A nomenclatura «cima» e «base» úsase independentemente de se a pila medra cara a direccións de memoria superiores.
Ao apilar un elemento, o punteiro de pila axústase polo tamaño do elemento, apuntando á seguinte cela, e cópiase o novo elemento da cima á área da pila. Dependendo da implementación exacta, ao final dunha operación push o punteiro pode apuntar á seguinte localización non usada ou ao elemento da cima. Ao desapilar, simplemente invístese o proceso.
Pila na memoria principal