Pilas Y Colas

Concepto de Colas

En las colas el elemento que entro en primer lugar también es el primero en salir por ello se conocen como listas FIFO (First in - First out).

Así pues la diferencia con las pilas recibe en el modo de entrada y salida de datos. En las colas las inserciones se realizan al final de la lista no al principio por ello las colas se usan para almacenar datos que necesiten ser procesados según el orden de llegada.

Nodo I M F

En la informática muchas aplicaciones para las colas (colas de aplicación) etc. . Por ejemplo un sistema de tiempo compartido suele tener un procesador central y una serie de periféricos compartidos: discos, impresoras, etc.

Los recursos se comparten con diferentes usuarios y se utiliza una cola para almacenar el programa por los diferentes usuarios que esperan su turno de ejecución. El procesador atiende por riguroso orden de llamado de usuario.

REPRESENTACIÓN DE COLAS

Las colas pueden representarse como estructuras dinámicas o arrays.

ESTRUCTURA DINAMICA

Inicio Medio Final

ARRAY

100 264 119 48

Inicio Final

COLAS DOBLES

Existe una variable de la cola simple que es la bicola (doble cola). Es una cola bidimensional en la que las inscripciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la cola.

Inserción Eliminación

Inicio Final

Eliminación Inserción

Existen dos variantes de la bicola (cola doble):

Cola doble con entrada restringida: Acepta valor, inserciones solo al final de la columna.

Cola doble con salida restringida: Acepta eliminaciones solo al inicio de la cola.

Indica Memoria Dinámica

Crear I I=NULL

Crear M M=NULL

Crear F F=NULL

Mientras si (Quiere dar de alta)

Si I=Null Entonces

Crear Nodo I

I sig=NULL

M=I

F=I

Si no

Crear nodo F

Fsig =M

M=F

COLA DOBLE CON SALIDA REESTRINGIDA

Acepta eliminaciones solo al inicio de la cola.

I MF

Crear I

Crear F

Crear M

I=NULL, F= NULL , M= NULL

Si I=NULL

Crear Nodo I

Isig1= NULL

Isig2 = NULL

F=I

M=I

Si no

Crear nodo F

Msig1 =F

Fsig2=M

Fsig1=I

M=F

Isig2=F

Solo se da de baja al inicio de la cola

Solo se da de alta al final de la cola.

I MF

BAJA AL FINAL DE LA COLA

M= Fsig2

Msig1=I

Isig2 = M

F=M

BAJA AL PRINCIPIO DE LA COLA

M=I

I=Msig1

Fsig1=M

Msig2=F

I=M

M=F

Concepto de Pilas

Una pila es un tipo de lista lineal en la que la inserción y borrado de nuevos elementos solo se pueden realizar por un extremo que se denomina tope o cima.

La pila es una estructura con numerosas analogías en la vida real, una pila de platos, una pila de documentos, una pila de monedas. Dado que la operación de insertar y eliminar se realizan por un solo extremo (superior) los elementos solo pueden eliminarse en un orden inverso al que se insertan en la pila.

El ultimo elemento que se pone en la pila es el primero que se puede sacar; por ello a estas lista se les conoce como LIFO (Last In - first Out).

0

1

2

3

4

5

6

0

1

2

3

4

5

6

AA

BB

CC

BB

CC

AA

En cualquiera de las tres formas mostradas anteriormente para representar una pila “S” se puede definir un vector con determinado tamaño (longitud máxima). Se considera un elemento entero P como indicador de la pila. P es el subíndice del array correspondiente al elemento cima de la pila (esto ocupa la ultima posición).

Si la pila esta vacía P es igual a cero.

A B C ... r l ...

1 2 3 P-1 P N-2 N-1 N

CIMA LONG.

(Puntero de la pila) MAX

Las operaciones mas usuales asociadas a las pilas son push, que es meter o poner. Pop que es sacar o quitar, que es eliminar el elemento de la pila.

Idealmente una pila puede contener un numero ilimitado de elementos y no producir nunca desbordamiento sin embargo, si hablamos de almacenamiento se hace necesario la implementación de pilas con apuntadores (almacenamiento dinámico).

PILAS DINAMICAS (STACK)

Es la mas sencilla de las estructuras dinámicas de datos. las pilas son utilizadas sobre todo por los sistemas operativos y controladores de lenguaje de alto nivel, una pila es dinámica porque crece y se encoge a mediada que sea necesario o para trabajar con pilas es importante definir los siguientes procedimientos:

PUSH.- Poner datos en la pila.

POP.- sacar datos de la pila

ERROR.- Pueden sacar datos de pilas vacías.

Ejemplo de Cola en Lenguaje 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;

}

~Cola(){

while (elementos != 0) pop();

}

void push(const T& elem){

Nodo* aux = new Nodo;

...