En ciencias da computación, unha cola é un tipo de dato abstracto que serve como colección ordenada de entidades. Por convención, o extremo da cola onde se engaden elementos chámase traseira ou final. O extremo onde se retiran chámase cabeza ou fronte. O nome cola é unha analoxía coas palabras usadas para describir as persoas que esperan quenda para bens ou servizos. Admite dúas operacións principais: Enqueue (encolar), que engade un elemento á traseira da cola. Dequeue (desencolar), que retira un elemento da fronte da cola. Tamén se poden permitir outras operacións, a miúdo unha de vista (peek) ou front, que devolve o valor do seguinte elemento a desencolar sen retiralo.

As operacións fan que unha cola sexa unha estrutura de datos FIFO (do inglés first in, first out): o primeiro elemento engadido é o primeiro en retirarse. Isto equivale a esixir que, unha vez engadido un novo elemento, todos os engadidos antes teñan que retirarse antes ca el. Unha cola é un exemplo de estrutura de datos linear, ou, máis abstractamente, unha colección secuencial.

As colas son comúns nos programas informáticos, onde se implementan como estruturas de datos con rutinas de acceso, como estrutura de datos abstracta ou, en linguaxes orientadas a obxectos, como clases. Unha cola pódese implementar con buffers circulares e listas ligadas, ou usando tanto o punteiro de pila como o punteiro de base.

As colas prestan servizos en ciencias da computación, transporte e investigación de operacións, onde entidades como datos, obxectos, persoas ou eventos se almacenan para procesalos despois. Nestes contextos, a cola cumpre a función dun buffer. Outro uso é a implementación da busca en anchura.

Implementación dunha cola Teoricamente, unha característica dunha cola é que non ten unha capacidade específica: independentemente de cantos elementos conteña, sempre se pode engadir un novo. Tamén pode estar baleira, e entón non se pode retirar ningún elemento ata que se engada outro.

Os vectores de lonxitude fixa teñen capacidade limitada, pero non é necesario copiar os elementos cara á cabeza da cola tras cada extracción. Nun buffer circular, a cabeza e a traseira avanzan por posicións calculadas módulo a capacidade do vector. Así, as insercións e extraccións non desprazan os demais elementos. O tamaño do vector fíxase de antemán; unha variante dinámica pode amplialo, por exemplo duplicándoo cando se enche. O desbordamento de cola (overflow) prodúcese ao tentar engadir un elemento nunha cola chea que non se pode ampliar, e o subdesbordamento (underflow) ao tentar retirar un elemento dunha cola baleira.

Unha cola limitada é unha cola restrinxida a un número fixo de elementos.

Hai varias implementacións eficientes de colas FIFO, que poden realizar as operacións en tempo : Lista ligada: Unha lista ligada dobre ten inserción e borrado nos dous extremos, polo que é a opción natural para colas. Unha lista ligada simple só ten inserción e borrado eficientes nun extremo; con todo, unha pequena modificación —gardar un punteiro ao último nó ademais do primeiro— permítelle implementar unha cola eficiente. Unha cola de dobre extremo (deque) implementada cun vector dinámico modificado.

Colas e linguaxes de programación As colas pódense implementar como un tipo de dato separado, ou considerarse un caso particular dunha cola de dobre extremo. Por exemplo, Perl e Ruby permiten engadir e retirar dun vector polos dous extremos, de modo que se poden usar push() e shift() para encolar e desencolar unha lista (ou, ao revés, unshift() e pop()), aínda que nalgúns casos estas operacións non son eficientes.

A Standard Template Library de C++ fornece a clase modelo std::queue<T>, restrinxida a operacións push/pop. Desde J2SE5.0, a biblioteca de Java contén a interface Queue, con clases implementadoras como LinkedList e, desde J2SE 1.6, ArrayDeque. PHP ten unha clase SplQueue e bibliotecas de terceiros como beanstalkd e Gearman.

Exemplo Unha cola simple implementada en TypeScript. Neste exemplo, shift() pode ter custo ao desprazar os elementos do vector; non é a implementación de tempo constante descrita para o buffer circular. class Queue<T> { private items: T[] = [];

enqueue(element: T): void { this.items.push(element);

dequeue(): T | undefined { return this.items.shift();

isEmpty(): boolean { return this.items.length === 0;

Implementación puramente funcional As colas tamén se poden implementar como estruturas de datos puramente funcionais.Chris Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998. A continuación descríbense unha cola con custo amortizado e unha variante en tempo real con custo no peor caso. A amortización acouta o custo total dunha secuencia, non unha media probabilística sobre entradas aleatorias. Na primeira variante, unha operación individual pode custar . A variante en tempo real descrita aquí usa listas preguiceiras con memoización e admite persistencia. Existen tamén construcións en tempo real baseadas en avaliación estrita.Robert Hood e Robert Melville, «Real-time queue operations in pure Lisp», Information Processing Letters, 13(2):50–54, 1981.

Cola amortizada Os datos desta cola gárdanse en dúas listas ligadas simples chamadas e . A lista contén a parte frontal da cola e a parte traseira en orde inversa: a secuencia lóxica é , onde denota concatenación. Para encolar engádese un nó á cabeza de . Para desencolar retírase a cabeza de ; se está baleira, antes invístese , asígnase o resultado a e baléirase . Se ambas están baleiras, a extracción non está definida.

A inserción (enqueue) leva . A extracción (dequeue) leva cando non está baleira, pero inverter pode levar . Nunha secuencia linear de operacións, cada elemento pasa de a como máximo unha vez, polo que o custo amortizado é por operación. Este argumento non se traslada directamente a un uso persistente con ramificacións, que pode repetir a inversión dunha mesma versión.

Cola en tempo real A cola en tempo real acada en todas as operacións, sen amortización. A estrutura de datos usada consta de tres listas ligadas simples , onde é a fronte da cola e é a traseira en orde inversa. A invariante da estrutura é que é a traseira de sen os seus primeiros elementos, é dicir, . A función auxiliar restaura a invariante tras cada operación. A lista serve de contador de e garante que a traseira nunca sexa máis longa cá fronte; ademais, ao ser unha cola de , forza a avaliación dunha parte da lista preguiceira durante cada operación, de xeito que o custo se mantén constante.

Notas

Véxase tamén Bibliografía Donald Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms, sección 2.2.1, terceira edición, Addison-Wesley, 1997. ISBN 0-201-89683-4. Páxinas 238–243. Thomas H. Cormen et al. Introduction to Algorithms, segunda edición, MIT Press, 2001. Sección 10.1: «Stacks and queues». ISBN 0-262-03293-7. Páxinas 200–204.

Outros artigos Cola de dobre extremo Cola de prioridade Bucle de eventos Cola de mensaxes Teoría de colas Pila

Ligazóns externas Colas en Wikimedia Commons

Categoría:Algoritmos Categoría:Programación