PILAS Y COLAS

PILA:
Una pila (stack en inglés) es una lista ordenada o estructura de datos que permite almacenar y
recuperar datos, el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In, First Out,
«último en entrar, primero en salir») . Esta estructura se aplica en multitud de supuestos en el
área de informática debido a su simplicidad y capacidad de dar respuesta a numerosos procesos.

Para el manejo de los datos 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 anterior (apilado con
anterioridad), que pasa a ser el último, el nuevo TOS.

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 conte0xto
 Implementación de recursividad.

En un sistema operativo cada proceso tiene un espacio de memoria (pila) para almacenar valores y
llamadas a funciones.

Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.

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 equivaldría a retirarlo.

A modo de resumen, 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 ya presentes en la pila. «Pop» devuelve y elimina el actual nodo superior de
la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos dispuesta en una
cafetería en un contenedor con un muelle que mantiene la pila a nivel. En esa serie, solo el primer
plato es visible y accesible para el usuario, todos las demás permanecen ocultos. Como se añaden
nuevos platos, cada nuevo plato se convierte en la parte superior de la pila, permaneciendo
escondidos debajo los demás. A medida que el plato superior se extrae de la pila, el
inmediatamente inferior pasa a ocupar la parte superior de la pila. Dos principios importantes son
ilustrados por esta metáfora: únicamente se accede al plato que se encuentra en la parte superior
(el último en depositarse), y el resto de platos de la pila permanecen ocultos. Para extraer un plato
distinto al superior habrá que extraer antes los que se encuentran sobre él.
Operaciones

Habitualmente, junto a las dos operaciones básicas de apilar y desapilar (push, pop), la pila puede
implementar otra serie de funciones:

 Crear (constructor): crea la pila vacía.

 Tamaño (size): regresa el número de elementos de la pila.
 Apilar (push): añade un elemento a la pila.
 Desapilar (pop): lee y retira el elemento superior de la pila.
 Leer último (top o peek): lee el elemento superior de la pila sin retirarlo.
 Vacía (empty): devuelve cierto si la pila está sin elementos o falso en caso de que
contenga alguno.

Una pila puede implementarse fácilmente ya sea mediante una matriz o una lista enlazada. Lo que
identifica a una estructura de datos como una pila en cualquier caso no es su estructura sino su
interfaz: al usuario solo se le permite colocar y extraer datos en el modo que se espera de una pila
y algunas otras operaciones auxiliares.

Arquitectura básica de una pila

Una pila típica es un área de la memoria de los computadores con un origen fijo, un espacio para
almacenar datos y un puntero. Al principio, su número de elementos es cero y la dirección del
puntero coincide con la dirección de origen. Conforme van incorporándose datos, los elementos
contenidos en la pila van incrementándose y el puntero va actualizando su dirección para hacerla
coincidir con el último en incorporase.

Las dos operaciones aplicables a todas las pilas son:

 Apilar: colocar un nuevo dato en la pila. Se lee el puntero para localizar el último
elemento, se incorpora a continuación de este y se redirecciona el puntero para que
apunte al nuevo dato incorporado.
 Desapilar: extraer un dato de la pila. Se localiza el último dato mediante el puntero, se lee
el dato y se redirecciona el puntero al elemento inmediato anterior para que vuelva a
apuntar al último dato de la pila.

Una pila queda definida por su origen (una dirección de memoria), y su capacidad para almacenar
datos. Cuando se intenta leer más allá de su origen (esto es, se intenta leer un elemento cuando
está vacía) o cuando se intenta sobrepasar su capacidad de almacenar elementos, se produce un
error: error por desbordamiento.
Se puede visualizar una pila de datos (independientemente de cómo se almacene en la memoria)
como una serie de datos colocados unos sobre otros (representación que se corresponde con el
mundo real) o como una sucesión de datos colocados de izquierda a derecha, unos tras otros.

Una pila ocuparía un bloque de celdas de memoria, con una dirección de origen, un espacio
reservado para la acumulación de datos y un puntero que apunta al último dato incorporado. La
estructura que adopte una pila puede ser muy variada: almacenando datos en direcciones
crecientes o decrecientes, con capacidad de almacenamiento flexible, con punteros que apunten
al último elemento o a la posición que deberá ocupar el próximo elemento que se incorpore… En
cualquier caso, quedará definida por su algoritmo: último en entrar, primero en salir.

Insertar elementos en una Pila:

Eliminar o quitar un elemento de la pila:

 Ejercicio:

#include <stdlib.h>

#include <stdio.h>

typedef struct _nodo {

int valor;

struct _nodo *siguiente;

} tipoNodo;

/* Funciones con pilas: */

void Push(tipoNodo **, int v);

int Pop(tipoNodo **);

int main(){

tipoNodo *pila = NULL;

int cant=3,num,i;

for(i=0;i<cant;i++){

printf("ingrese numero \n");

scanf("%i",&num);

Push(&pila,num);

printf("\n");

for(i=0;i<cant;i++){

printf("%i, ",Pop(&pila));

system("PAUSE");
return 0;

void Push(tipoNodo **pila, int v){

tipoNodo *nuevo,*aux;

nuevo = malloc(sizeof(tipoNodo));

nuevo->valor = v;

nuevo->siguiente = *pila;

*pila = nuevo;

printf("\n");

int Pop(tipoNodo **pila){

tipoNodo *nodo;

nodo = *pila;

int v;

if(nodo==NULL){

printf("Pila vacia ");

return 0;

else{

*pila = nodo->siguiente;

v = nodo->valor;

free(nodo);

return v;

}
COLA:
Una cola (también llamada fila) es una estructura de datos, caracterizada por ser una secuencia de
elementos en la que la operación de inserción push se realiza por un extremo y la operación de
extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out),
debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre

otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se
guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos
abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas
enlazadas.

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.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando

para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña
peluquería, etc. La idea esencial es que son todos líneas de espera.

En estos casos, el primer elemento de la lista realiza su función (pagar comida, pagar entrada para
el partido o para el cine) y deja la cola. Este movimiento está representado en la cola por la
función pop o desencolar. Cada vez que otro elemento se añade a la lista de espera se añaden al
final de la cola representando la función push o encolar. Hay otras funciones auxiliares para ver el
tamaño de la cola (size), para ver si está vacía en el caso de que no haya nadie esperando (empty)
o para ver el primer elemento de la cola (front).

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 darles 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.

Operaciones Básicas

 Crear: se crea la cola vacía.

 Encolar: 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ó.
Insertar elementos en una Cola.

Eliminar o quitar un elemento de la Cola.

 Ejercicio:

#include <stdlib.h>

#include <stdio.h>

typedef struct nodo{

char dat;

struct nodo *sig;

}Nodo;

int main(){

int op,n;

char dato;

Nodo *frente=NULL;

Nodo *fin=NULL;

do{

printf("\t Menu \n");

printf("1.- Anadir caracter \n");

printf("2.- Quitar caracter \n");

printf("3.- Mostrar \n");

printf("4.- Salir \n");

scanf("%i",&op);

switch(op){

case 1:

fflush(stdin);

printf("Ingrese caracter \n");

scanf("%c",&dato);

Nodo *nuevo;
 nuevo=malloc(sizeof(Nodo));

nuevo->dat=dato;

nuevo->sig=NULL;

if(frente==NULL){

frente=nuevo;

else{

fin->sig=nuevo;

fin=nuevo;

break;

case 2:

printf("Quitando elemento....\n");

n=frente->dat;

Nodo *aux=frente;

if(frente==fin){

frente=NULL;

fin=NULL;

else{

frente=frente->sig;

aux=NULL;

break;

case 3:

aux=frente;

if(aux!=NULL){
 while(aux!=NULL){

printf(" %c \n",aux->dat);

aux=aux->sig;

else{

printf("Cola vacia \n");

break;

case 4:

break;

}while(op!=4);

getch();

return 0;

}
 Árbol Recorridos:
PreOrden:

(Raíz, izquierda, derecha). Para recorrer un árbol binario no vacío en PreOrden, hay que realizar las
siguientes operaciones recursivamente en cada nodo, comenzando con el nodo raíz.

Orden De impresión

 Visite la raíz
 Atraviese el sub-árbol izquierdo
 Atraviese el sub-árbol derecho

Código:

InOrden:

(Izquierda, raiz, derecho). Para recorrer un árbol binario no vacío en InOrden, hay que realizar las
siguientes operaciones recursivamente en cada nodo:

 Atraviese el sub-árbol izquierdo

 Visite la raíz
 Atraviese el sub-árbol derecho
Código:

Post Orden:

(izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en PostOrden, hay que realizar
las siguientes operaciones recursivamente en cada nodo:

 Atraviese el sub-árbol izquierdo

 Atraviese el sub-árbol derecho
 Visite la raíz

Codigo: