Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.
En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.
Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.
Las pilas suelen emplearse en los siguientes contextos:
- Evaluación de expresiones en notación postfija (notación polaca inversa).
- Reconocedores sintácticos de lenguajes independientes del contexto
- Implementación de recursividad.
Historia
El método de pila para la evaluación de expresiones fue propuesto en 1955 y dos años después patentado por Friedrich L. Bauer, quién recibió en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.Pila como tipo abstracto de datos
A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). 'Push' añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.Operaciones
Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.- Crear: se crea la pila vacía. (constructor)
- Tamaño: regresa el número de elementos de la pila. (size)
- 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 (empty).
Implementación
Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.
Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobación de errores).
Implementación en Python
class Stack(object): def __init__(self): self.stack_pointer = None def push(self, element): self.stack_pointer = Node(element, self.stack_pointer) def pop(self): e = self.stack_pointer.element self.stack_pointer = self.stack_pointer.next return e def peek(self): return self.stack_pointer.element def __len__(self): i = 0 sp = self.stack_pointer while sp: i += 1 sp = sp.next return i class Node(object): def __init__(self, element=None, next=None): self.element = element self.next = next if __name__ == '__main__': # small use example s = Stack() for i in range(10):s.push(i) for i in range(len(s)):print(s.pop())
Implementación en Maude
La PilaNV es la pila no vacía, que diferenciamos de la pila normal a la hora de tomar en cuenta errores. El elemento X representa el tipo de valor que puede contener la pila: entero, carácter, registro, etc.fmod PILA-GENÉRICA {X :: TRIV} is
sorts Pila{X} PilaNV{X}.
subsorts PilaNV{X} < Pila{X}.
***generadores:
op crear: -> Pila {X} [ctor].
op apilar : X$Elt Pila{X} -> PilaNV{X} [ctor].
***constructores
op desapilar : Pila{X} -> Pila{X}.
***selectores
op cima : PilaNV{X} -> X$Elt.
***variables
var P : Pila{X}.
var E : X$Elt.
***ecuaciones
eq desapilar (crear) = crear.
eq desapilar(apilar(E, P)) = P.
eq cima(apilar(E, P)) = E.
endfm
Implementación en Visual Basic
Public Class Stack Private p_index As Integer Private list As New ArrayList Public Sub New() p_index = -1 End Sub ReadOnly Property count Get Return list.Count End Get End Property Public Sub push(ByVal value As Object) list.Add(value) p_index += 1 End Sub Public Function pop() As Object Dim obj As Object = list.Item(p_index) list.RemoveAt(p_index) p_index -= 1 Return obj End Function Public Sub clear() list.Clear() p_index = -1 End Sub Public Function peek() As Object Return list.Item(p_index) End Function End Class
En C++
#ifndef PILA #define PILA // define la pila template <class T> class Pila { private: struct Nodo { T elemento; Nodo* siguiente; // coloca el nodo en la segunda posicion }* ultimo; unsigned int elementos; public: Pila() { elementos = 0; } ~Pila() { while (elementos != 0) pop(); } void push(const T& elem) { Nodo* aux = new Nodo; aux->elemento = elem; aux->siguiente = ultimo; ultimo = aux; ++elementos; } void pop() { Nodo* aux = ultimo; ultimo = ultimo->siguiente; delete aux; --elementos; } T cima() const { return ultimo->elemento; } bool vacia() const { return elementos == 0; } unsigned int altura() const { return elementos; } }; #endif
Implementación en Java
public class Nodo<tipo> { public tipo dato; private Nodo<tipo> siguiente; public Nodo(tipo Dato) { dato = Dato; siguiente = null; } public void conectar(Nodo<tipo> elSiguiente) { siguiente = elSiguiente; } public Nodo<tipo> getSiguiente() { return siguiente; } } public class Pila<tipo> { Nodo<tipo> cima; public Pila() { cima = null; } public int tamano() { Nodo<tipo> lectorAuxiliar = cima; int contadorDeDatos = 0; while (lectorAuxiliar != null) { contadorDeDatos++; lectorAuxiliar = lectorAuxiliar.getSiguiente(); } return contadorDeDatos; } public void apilar(tipo datoNuevo) { Nodo<tipo> nuevo = new Nodo<tipo>(datoNuevo); nuevo.conectar(cima); cima = nuevo; } public tipo desapilar() { tipo dato = cima.dato; cima = cima.getSiguiente(); return dato; } public tipo getCima() { return cima.dato; } public boolean estaVacia() { return cima == null; } public String toString() { Nodo<tipo> lectorAuxiliar = cima; String respuesta = "IN/OUT <->"; while (lectorAuxiliar != null) { respuesta += " [" + lectorAuxiliar.dato.toString() + "] "; lectorAuxiliar = lectorAuxiliar.getSiguiente(); } return respuesta; } }
Estructuras de datos relacionadas
El tipo base de la estructura FIFO (el primero en entrar es el primero en salir)es la cola, y la combinación de las operaciones de la pila y la cola es proporcionado por el deque. Por ejemplo, el cambio de una pila en una cola en un algoritmo de búsqueda puede cambiar el algoritmo de búsqueda en primera profundidad (en inglés, DFS) por una búsqueda en amplitud (en inglés, BFS). Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.Pilas Hardware
Un uso muy común de las pilas a nivel de arquitectura hardware es la asignación de memoria.
Arquitectura básica de una pila
Una pila típica es un área de la memoria de los computadores con un origen fijo y un tamaño variable. Al principio, el tamaño de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la más reciente localización en la pila; cuando la pila tiene un tamaño de cero, el puntero de pila de puntos en el origen de la pila.Las dos operaciones aplicables a todas las pilas son:
- Una operación apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la dirección en el puntero de pila se ajusta por el tamaño de los datos de partida.
- Una operación desapilar: un elemento de datos en la ubicación actual apuntado por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamaño de los datos de partida.
Por ejemplo, una pila puede comenzar en una posición de la memoria de mil, y ampliar por debajo de las direcciones, en cuyo caso, los nuevos datos se almacenan en lugares que van por debajo de 1000, y el puntero de pila se decrementa cada vez que un nuevo elemento se agrega. Cuando un tema es eliminado de la pila, el puntero de pila se incrementa.
Los punteros de pila pueden apuntar al origen de una pila o de un número limitado de direcciones, ya sea por encima o por debajo del origen (dependiendo de la dirección en que crece la pila), sin embargo el puntero de pila no puede cruzar el origen de la pila. En otras palabras, si el origen de la pila está en la dirección 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, y así sucesivamente), el puntero de pila nunca debe ser incrementado más allá de 1000 (para 1001, 1002, etc.) Si un desapilar operación en la pila hace que el puntero de pila se deje atrás el origen de la pila, una pila se produce desbordamiento. Si una operación de apilar hace que el puntero de pila incremente o decremente más allá del máximo de la pila, en una pila se produce desbordamiento.
La pila es visualizada ya sea creciente de abajo hacia arriba (como pilas del mundo real), o, con el máximo elemento de la pila en una posición fija, o creciente, de izquierda a derecha, por lo que el máximo elemento se convierte en el máximo a "la derecha". Esta visualización puede ser independiente de la estructura real de la pila en la memoria. Esto significa que rotar a la derecha es mover el primer elemento a la tercera posición, la segunda a la primera y la tercera a la segunda. Aquí hay dos equivalentes visualizaciones de este proceso:
Manzana Plátano Plátano ==rotar a la derecha==> Fresa Fresa Manzana
Fresa Manzana Plátano ==rotar a la izquierda==> Fresa Manzana Plátano
Una pila es normalmente representada en los ordenadores por un bloque de celdas de memoria, con los "de abajo" en una ubicación fija, y el puntero de pila de la dirección actual de la "cima" de células de la pila. En la parte superior e inferior se utiliza la terminología con independencia de que la pila crece realmente a la baja de direcciones de memoria o direcciones de memoria hacia mayores.
Apilando un elemento en la pila,se ajusta el puntero de pila por el tamaño de elementos (ya sea decrementar o incrementar, en función de la dirección en que crece la pila en la memoria), que apunta a la próxima celda, y copia el nuevo elemento de la cima en área de la pila. Dependiendo de nuevo sobre la aplicación exacta, al final de una operación de apilar, el puntero de pila puede señalar a la siguiente ubicación no utilizado en la pila, o tal vez apunte al máximo elemento de la pila. Si la pila apunta al máximo elemento de la pila, el puntero de pila se actualizará antes de que un nuevo elemento se apile, si el puntero que apunta a la próxima ubicación disponible en la pila, que se actualizará después de que el máximo elemento se apile en la pila.
Desapilando es simplemente la inversa de apilar. El primer elemento de la pila es eliminado y el puntero de pila se actualiza, en el orden opuesto de la utilizada en la operación de apilar.
Soporte de Hardware
Muchas CPUs tienen registros que se pueden utilizar como punteros de pila. Algunos, como el Intel x86, tienen instrucciones especiales que implícitamente el uso de un registro dedicado a la tarea de ser un puntero de pila. Otros, como el DEC PDP-11 y de la familia 68000 de Motorola tienen que hacer frente a los modos de hacer posible la utilización de toda una serie de registros como un puntero de pila. La serie Intel 80x87 numérico de coprocessors tiene un conjunto de registros que se puede acceder ya sea como una pila o como una serie de registros numerados. Algunos microcontroladores, por ejemplo algunos PICs, tienen un fondo fijo de pila que no es directamente accesible. También hay una serie de microprocesadores que aplicar una pila directamente en el hardware:- Computer vaqueros MuP21
- Harris RTX línea
- Novix NC4016
Soporte de Software
En programas de aplicación escrito en un lenguaje de alto nivel, una pila puede ser implementada de manera eficiente, ya sea usando vectores o listas enlazadas. En LISP no hay necesidad de aplicar la pila, puesto que las funciones apilar y desapilar están disponibles para cualquier lista. Adobe PostScript también está diseñada en torno a una pila que se encuentra directamente visible y manipuladas por el programador. El uso de las pilas está muy presente en el desarrollo de software por ello la importancia de las pilas como tipo abstracto de datos.Expresión de evaluación y análisis sintáctico
Se calcula empleando la notación polaca inversa utilizando una estructura de pila para los posibles valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversión de una forma de la expresión a otra forma necesita de una pila. Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. Antes de traducir el código de bajo nivel. La mayoría de los lenguajes de programación son de contexto libre de los idiomas que les permite ser analizados con máquinas basadas en la pila.Por ejemplo, el cálculo: ((1 + 2) * 4) + 3, puede ser anotado como en notación postfija con la ventaja de no prevalecer las normas y los paréntesis necesario:
1 2 + 4 * 3 +
La expresión es evaluada de izquierda a derecha utilizando una pila:
- Apilar cuando se enfrentan a un operando y
- Desafilar dos operandos y evaluar el valor cuando se enfrentan a una operación.
- Apilar el resultado.
ENTRADA OPERACIÓN PILA 1 Apilar operando 1 2 Apilar operando 1, 2 + Añadir 3 4 Apilar operando 3, 4 * Multiplicar 12 3 Apilar operando 12, 3 + Añadir 15
El resultado final, 15, se encuentra en la parte superior de la pila al final del cálculo.
Tiempo de ejecución de la gestión de memoria
Artículo principal: Pila basada en la asignación de memoria y Pila máquina. Una serie de lenguajes de programación están orientadas a la pila, lo que significa que la mayoría definen operaciones básicas (añadir dos números, la impresión de un carácter) cogiendo sus argumentos de la pila, y realizando de nuevo los valores de retorno en la pila. Por ejemplo, PostScript tiene una pila de retorno y un operando de pila, y también tiene un montón de gráficos estado y un diccionario de pila.Forth utiliza dos pilas, una para pasar argumentos y una subrutina de direcciones de retorno. El uso de una pila de retorno es muy común, pero el uso poco habitual de un argumento para una pila legible para humanos es el lenguaje de programación Forth razón que se denomina una pila basada en el idioma.
Muchas máquinas virtuales también están orientadas hacia la pila, incluida la p-código máquina y la máquina virtual Java.
Casi todos los entornos de computación de tiempo de ejecución de memoria utilizan una pila especial PILA para tener información sobre la llamada de un procedimiento o función y de la anidación con el fin de cambiar al contexto de la llamada a restaurar cuando la llamada termina. Ellos siguen un protocolo de tiempo de ejecución entre el que llama y el llamado para guardar los argumentos y el valor de retorno en la pila. Pila es una forma importante de apoyar llamadas anidadas o a funciones recursivas. Este tipo de pila se utiliza implícitamente por el compilador para apoyar CALL y RETURN estados (o sus equivalentes), y no es manipulada directamente por el programador.
Algunos lenguajes de programación utilizar la pila para almacenar datos que son locales a un procedimiento. El espacio para los datos locales se asigna a los temas de la pila cuando el procedimiento se introduce, y son borradas cuando el procedimiento termina. El lenguaje de programación C es generalmente aplicado de esta manera. Utilizando la misma pila de los datos y llamadas de procedimiento tiene importantes consecuencias para la seguridad (ver más abajo), de los que un programador debe ser consciente, a fin de evitar la introducción de graves errores de seguridad en un programa.
Solucionar problemas de búsqueda
La búsqueda de la solución de un problema, es independientemente de si el enfoque es exhaustivo u óptimo, necesita espacio en la pila. Ejemplos de búsqueda exhaustiva métodos son fuerza bruta y backtraking. Ejemplos de búsqueda óptima a explorar métodos,son branch and bound y soluciones heurísticas. Todos estos algoritmos utilizan pilas para recordar la búsqueda de nodos que se han observado, pero no explorados aún. La única alternativa al uso de una pila es utilizar la recursividad y dejar que el compilador sea recursivo (pero en este caso el compilador todavía está utilizando una pila interna). El uso de pilas es frecuente en muchos problemas, que van desde almacenar la profundidad de los árboles hasta resolver crucigramas o jugar al ajedrez por ordenador. Algunos de estos problemas pueden ser resueltos por otras estructuras de datos como una cola.Seguridad
La seguridad a la hora de desarrollar software usando estructuras de datos de tipo pila es un factor a tener en cuenta debido a ciertas vulnerabilidad que un uso incorrecto de éstas puede originar en la seguridad de nuestro software o en la seguridad del propio sistema que lo ejecuta. Por ejemplo, algunos lenguajes de programación usan una misma pila para almacenar los datos para un procedimientos y el link que permite retornar a su invocador. Esto significa que el programa introduce y extrae los datos de la misma pila en la que se encuentra información crítica con las direcciones de retorno de las llamadas a procedimiento, supongamos que al introducir datos en la pila lo hacemos en una posición errónea de manera que introducimos una datos de mayor tamaño al soportado por la pila corrompiendo así las llamadas a procedimientos provocariamos un fallo en nuestro programa. Ésta técnica usada de forma maliciosa (es similar, pero en otro ámbito al buffer overflow) permitiría a un atacante modificar el funcionamiento normal de nuestro programa y nuestro sistema, y es al menos una técnica útil si no lo evitamos en lenguajes muy populares como el ejemplo C++.Véase también
Cola (informática)Usos concretos de la cola
La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.
Información adicional
En caso de estar vacía, borrar un elemento sería imposible hasta que no se añade un nuevo elemento. A la hora de añadir un elemento podríamos darle una mayor importancia a unos elementos que a otros (un cargo VIP) y para ello se crea un tipo de cola especial que es la cola de prioridad. (Ver cola de prioridad).Operaciones Básicas
- Crear: se crea la cola vacía.
- Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
- Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
- Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.
Implementaciones
Colas en Maude
La ColaNV es la cola no vacía, que diferenciamos de la cola normal a la hora de tomar en cuenta errores. A su vez, el elemento X representa el tipo de valor que puede contener la cola: entero, carácter, registro.... fmod COLA {X :: TRIV} is
sorts ColaNV{X} Cola{X} .
subsort ColaNV{X} < Cola{X} .
*** generadores
op crear : -> Cola{X} [ctor] .
op encolar : X$Elt Cola{X} -> ColaNV {X} [ctor] .
*** constructores
op desencolar : Cola{X} -> Cola{X} .
*** selectores
op frente : ColaNV{X} -> X$Elt .
*** variables
var C : ColaNV{X} .
vars E E2 : X$Elt .
*** ecuaciones
eq desencolar(crear) = crear .
eq desencolar(encolar(E, crear)) = crear .
eq desencolar(encolar(E, C)) = encolar(E, desencolar(C)) .
eq frente(encolar(E, crear)) = E .
eq frente(encolar(E, C)) = frente(C) .
endfm
Especificación de una cola de colas de enteros en Maude:
view VInt from TRIV to INT is
sort Elt to Int .
endv
view VColaInt from TRIV to COLA{VInt} is
sort Elt to Cola{VInt} .
endv
fmod COLA-COLAS-INT is
protecting INT .
protecting COLA{VColaInt} .
*** operaciones propias de la cola de colas de enteros
op encolarInt : Int ColaNV{VColaInt} -> ColaNV{VColaInt} .
op desencolarInt : Cola{VColaInt} -> Cola{VColaInt} .
op frenteInt : ColaNV{VColaInt} -> [Int] .
*** variables
var CCNV : ColaNV{VColaInt} .
var CC : Cola{VColaInt} .
var CE : Cola{VInt} .
var E : Int .
*** ecuaciones
eq encolarInt(E, encolar(CE, CC)) = encolar(encolar(E, CE), CC) .
eq desencolarInt (encolar(CE, crear)) = encolar(desencolar(CE), crear) .
eq desencolarInt (encolar(CE, CCNV)) = encolar(CE, desencolarInt(CCNV)) .
eq frenteInt(CCNV) = frente(frente(CCNV)) .
endfm
Colas en C++
#ifndef COLA #define COLA // Define la cola template <class T> class Cola{ private: struct Nodo{ T elemento; struct Nodo* siguiente; // coloca el nodo en la segunda posición }* primero; struct Nodo* ultimo; unsigned int elementos; public: Cola(){ elementos = 0; } cout<<" Hola Mundo! "<<endl; cout<<" Hello, World! "<<endl; ~Cola(){ while (elementos != 0) pop(); } void push(const T& elem){ Nodo* aux = new Nodo; aux->elemento = elem; if (elementos == 0) primero = aux; else ultimo->siguiente = aux; ultimo = aux; ++elementos; } void pop(){ Nodo* aux = primero; primero = primero->siguiente; delete aux; --elementos; } T consultar() const{ return primero->elemento; } bool vacia() const{ return elementos == 0; } unsigned int size() const{ return elementos; } }; #endif
Colas en JAVA
public void inserta(Elemento x) { Nodo Nuevo; Nuevo = new Nodo(x, null); if (NodoCabeza == null) { NodoCabeza = Nuevo; } else { NodoFinal.Siguiente = Nuevo; } NodoFinal = Nuevo; } public Elemento cabeza() throws IllegalArgumentException { if (NodoCabeza == null) { throw new IllegalArgumentException(); } else { return NodoCabeza.Info; } } public Cola() { // Devuelve una Cola vacía NodoCabeza = null; NodoFinal = null; }
Colas en C#
public partial class frmPrincipal { // Variables globales public static string[] Cola; public static int Frente; public static int Final; public static int N; [STAThread] public static void Main(string[] args) { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new frmPrincipal()); } public frmPrincipal() // Constructor { InitializeComponent(); Cola = new string[5]; // Arreglo lineal de 5 N = 4; Frente = -1; Final = -1; } void CmdInsercionClick(object sender, System.EventArgs e) { frmInsercion Insercion = new frmInsercion(); Insercion.Show(); } void CmdRecorridoClick(object sender, System.EventArgs e) { frmRecorrido Recorrido = new frmRecorrido(); Recorrido.Show(); } void CmdBusquedaClick(object sender, EventArgs e) { frmBusqueda Busqueda = new frmBusqueda(); Busqueda.Show(); } void CmdEliminacionClick(object sender, EventArgs e) { frmEliminacion Eliminar = new frmEliminacion(); Eliminar.Show(); } }
void CmdInsertarClick(object sender, System.EventArgs e) { elemento = txtInsercion.Text; // Se verifica que haya espacio en la Cola if (frmPrincipal.Frente == 0 && frmPrincipal.Final == frmPrincipal.N) { MessageBox.Show("La Cola esta llena"); return; } if (frmPrincipal.Frente == frmPrincipal.Final + 1) { MessageBox.Show("La Cola esta llena"); return; } // Si la cola esta vacia se inicializan punteros if (frmPrincipal.Frente == -1) { frmPrincipal.Frente = 0; frmPrincipal.Final = 0; } else if (frmPrincipal.Final == frmPrincipal.N) { frmPrincipal.Final = 0; } else { frmPrincipal.Final = frmPrincipal.Final + 1; } // Se agrega elemento a la Cola frmPrincipal.Cola[frmPrincipal.Final] = elemento; txtInsercion.Text = ""; }
void CmdEliminarClick(object sender, EventArgs e) { if (frmPrincipal.Frente == -1) { MessageBox.Show("Cola Vacia"); return; } string elemento = frmPrincipal.Cola[frmPrincipal.Frente]; // si la cola tiene un solo elemento if (frmPrincipal.Frente == frmPrincipal.Final) { frmPrincipal.Frente = -1; frmPrincipal.Final = -1; } else if (frmPrincipal.Frente == frmPrincipal.N) { frmPrincipal.Frente = 0; } else { frmPrincipal.Frente = frmPrincipal.Frente + 1; } lsEliminado.Items.Add(elemento); }
import java.util.*; public class Cola <Tipo>{ private List<Tipo> cola; public Cola(){ cola=new ArrayList<Tipo>(); } public boolean colaVacia(){ return cola.isEmpty(); } public void agregar(Tipo elemento){ cola.add(elemento); } public Tipo sacar(){ if(colaVacia())return null; Tipo elemento=cola.get(0); cola.remove(0); return elemento; } }// Fin de la clase Cola
public class Manejador { public static void main(String[] args) { Cola cola=new <Integer>Cola(); System.out.println(cola.sacar()); cola.agregar(23); cola.agregar(24); cola.agregar(25); while(!cola.colaVacia()){ System.out.println(cola.sacar()); } Cola nombres=new <String>Cola(); nombres.agregar("Jorge"); nombres.agregar("Raquel"); nombres.agregar("Mayra Alejandra"); while(!nombres.colaVacia()){ System.out.println(nombres.sacar()); } } }// Fin de la clase Manejadora
Tipos de colas
- Colas circulares (anillos): en las que el último elemento y el primero están unidos.
- Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:
- Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
- Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
- Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:
- Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.
- Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.
Véase también
- Pila (estructura de datos)
- Lista (estructura de datos)
- Cola de prioridad (estructura de datos)
- Cola circular
- Bicola
DOS QUE TRES LA INFORMACION LOS CODIGOS NO CORREN
ResponderEliminar