.

Las pilas son una de las estructuras de datos con mayor uso en sistemas computacionales. Esto se debe a que es muy eficiente para realizar sus operaciones básicas de empujar (push) y sacar (pop), las cuales toman un tiempo constante en ejecutarse.

• Una pila (stack) es una estructura de datos LIFO (Last in, First Out) lineal en donde la inserción (push) de nuevos elementos y remoción estos (pop) únicamente se pueden realizar en extremo de la linea llamado cima (top).

• LIFO significa que el último elemento que ingresó a la pila debe ser el primero en salir.

• Un extremo de la pila debe de ser designado como la cima.

• A la pilas también también se les conoce como pushdown lists.

• Las pilas almacenan objetos del mismo tipo.

• En principio, las pilas son de tamaño ilimitado.
  • Agregar un nuevo elemento a esta produce una estructura más grande.
  • Únicamente debemos guardar la dirección (u otra referencía) del objeto en la cima.
• A La pila sin elementos se le conoce como pila vacía (empty stack).
  • La operación pop no esta definida en pilas vacías.
  • Para poder detectar si la operación pop esta definida, debemos definir la operación isempty (esta vacía).

• Las pilas se pueden almacenar en memoria de forma no contigua.

La desventaja principal de las pilas es el tiempo de acceso aleatorio:

Si asumimos que las operaciones de pull y push toman tiempo 1,

¿Cuál es el tiempo promedio que tarda el obtener un elemento en la posición \(i\) de una pila que contiene \(n\) elementos?

Solución:

Indexemos a los elementos por su posición con respecto a la cima de la pila, donde el primer elemento es el elemento en la cúspide.

Entonces, para obtener el \(i\)-esímo elemento necesitamos realizar \(i\) operaciones pull.

Luego, el promedio es \[\frac{\sum_i^n i}{n}= \frac{\frac{n(n+1)}{2}}{n} = \frac{n(n+1)}{2n}= \frac{n+1}{2}.\] Esto es, el tiempo de consulta (seek time) de un elemento cualquiera crece en relación lineal con respecto al tamaño de la pila.

En C podemos implementar una pila usando arreglos o listas ligadas.

• A la primera opción se le conoce como almacenamiento contiguo o estático.

• A la segunda almacenamiento ligado o dinámico.

En general, para implementar una pila necesitamos guardar la dirección del elemento que se encuentra en la cima y poco más.

Para implementar una pila de almacenamiento contiguo necesitamos.

• Un espacio contiguo en memoria del mismo tipo (arreglo).
• Una variable que guarde la cima de esta (dentro del arreglo).

Implementación:

#include <stdio.h>
#define MAXPILA 20

typedef char bool;
#define TRUE  1
#define FALSE 0

struct stack{
    int elementos[MAXPILA];
    int cima;
};

bool isempty(struct stack *pila){
    if (pila -> cima > -1){
        return 0;
    }
    return 1;
}

void push(struct stack *pila, int elemento){
    if ( (*pila).cima < MAXPILA-1){
            (*pila).cima ++;
            (*pila).elementos[pila->cima]=elemento;
            }
    return;
}

int pop(struct stack *pila){
    int salida;
    
    if (isempty(pila))
        return NULL;
    
    salida = pila -> elementos[pila -> cima];
    
    pila-> cima--;
    
    return salida;
}

int main(){
     
     int i;
     struct stack pila;
     
     pila.cima = -1;
     
     int llenado[] = {1,2,3,4,5};
     
     for(i = 0; i < 5; i++){
        push(&pila, llenado[i]);
     }
     
     for(i = 3; i > 0; i--){
        printf("%d\n", pop(&pila));
     }
     
     return 0;
 }
 

.

Como verán en su curso de Autómatas y Lenguajes formales, las pilas son una forma natural de procesar una clase de lenguajes llamados libres de contexto.

Paréntesis Balanceados.

En una cadena de texto, los paréntesis se dicen que están balanceados si, por cada uno que abre '(' hay uno que cierra ')' en el orden adecuado.

Con el siguiente programa veremos que la pila es una forma eficiente de procesar cadenas de paréntesis balanceados.

Problema:

Dada una cadena, decidir si los paréntesis en esta están balanceados o no.

#include <stdio.h>
#define MAXPILA 100

typedef char bool;
#define TRUE  1
#define FALSE 0

struct stack{
    int elementos[MAXPILA];
    int cima;
};

bool isempty(struct stack *pila){
    if (pila -> cima > -1){
        return 0;
    }
    
    return 1;
}

void push(struct stack *pila, int elemento){
    if ( (*pila).cima < MAXPILA-1){
            (*pila).cima ++;
            (*pila).elementos[pila->cima]=elemento;
            }
    return;
}

int pop(struct stack *pila){
    int salida;
    
    if (isempty(pila))
        return NULL;
    
    salida = pila -> elementos[pila -> cima];
    pila-> cima--;
    
    return salida;
}

bool estaBalanceado(char *cadena, int longitud);

int main(){
    
    char cadena[20];
    
    printf("Escribe la Cadena: ");
    scanf("%s",cadena);
    
    if(estaBalanceado(cadena, sizeof(cadena))){
         printf("La cadena SI esta balanceada.\n");
         }
    else
         printf("La cadena NO esta balanceada.\n");
     
    return 0;
 }

bool estaBalanceado(char *cadena, int longitud){
    int i;
    char c;
    struct stack pila;
     
    pila.cima = -1;
    
    if (cadena[0]=='(')
        push(&pila, cadena[0]);
    if (cadena[0]==')')
        return FALSE;   
    

    for(i = 1; i < longitud; i++){
        c = cadena[i];
            
        if (cadena[i]=='('){
            push(&pila, 1);
            }
        if (cadena[i]==')')
        {
            if (isempty(&pila))
                return FALSE;
            pop(&pila);
        }
            
    }
    if(isempty(&pila))
        return TRUE;
    
    return FALSE;
}

Hasta ahora nos hemos enfocado en estructuraras de datos cuyo tamaño de se debe de definir al momento de escribir el programa. A este tipos de estructuras se les conoce como estructuras estáticas.

• Por ejemplo, al definir un arreglo tenemos que especificar su tamaño al momento de escribir un programa y este normalmente no se puede cambiar.

En constaste, vamos a conocer cómo estructuras dinámicas a aquellas estructuras de datos que nos van a permitir almacenar, en teoría, una cantidad no limitada de datos. La primera de este tipos de estructuras que voy ha introducir son las listas simplemente ligadas o enlazadas.

La forma natural de construir una estructura dinámica es por medio de eslabones o nodos, donde estos son objetos que contienen un dato a guardar y la dirección de memoria de los objetos adyacentes.

De esta forma, al consultar un nodo tenemos el valor del dato guardado y la dirección de memoria del siguiente objeto en una cadena o lista.

• Es importante notar que, a diferencia de un arreglo, el almacenamiento de una lista no tiene la obligación de ser continuo.

En C, un nodo (simplemente ligado) se puede definir por la siguiente estructura:

struct Nodo{
  tipo data;
  struct Nodo* next;
};

.

#include <stdio.h>
#include <stdlib.h>

struct nodo{
  int valor;
  struct nodo *siguiente;
};

struct list{
  struct nodo *primero;
};

struct nodo* nuevoNodo(){
    struct nodo *nuevo;
    nuevo = malloc(sizeof(struct nodo));

    return nuevo;
};

void agregarAlFinal(struct list l, int val) {

    struct nodo *buf, *nuevo;
    
    buf = l.primero;
    nuevo = nuevoNodo();
    nuevo->valor = val;
    nuevo->siguiente = NULL;

    if (buf == NULL){
        l.primero = nuevo;
        return;
    }
    while(buf->siguiente != NULL){
        buf = buf -> siguiente;
    }

    buf -> siguiente = nuevo;
}

struct nodo elementoEnLista(struct list l, int pos){
    int i;
    struct nodo *buf;
     
    buf = l.primero;
    for (i = 0; i < pos; i++){
        buf = buf -> siguiente;
    }
    
    return *buf;
}

int main()
{
    int i, c, entero;
    struct list lista;
    struct nodo seleccion;
    
    lista.primero = NULL;

    printf("Cuantos elementos tiene tu lista?\n");
    scanf("%d", &i);

    if (i > 0){
        printf("Escribe un entero para aregar a la lista.\n");
        scanf("%d", &entero);
        
        lista.primero = nuevoNodo();
        lista.primero -> siguiente = NULL;
        lista.primero -> valor = entero;
    }

    for(c=i-1;c>0;c--){
        printf("Escribe un entero para aregar a la lista.\n");
        scanf("%d", &entero);
        agregarAlFinal(lista, entero);
      }
    
    while(1){
        printf("Que elemento quieres?\n");
        scanf("%d", &c);
        
        if ((c<0)||(c>=i))
            break;

        seleccion = elementoEnLista(lista, c);
        printf("El valor es: %d\n",seleccion.valor);
    }
    return 0;
}

En comparación con un arreglo, las listas ligadas:

Ventajas:

• Son de tamaño (en teoría) indefinido.
• Se reserva solo el espacio que se usa.
• Se pueden almacenar de forma no contigua.
• Se pueden almacenar en desorden.

Desventajas :

• Son de acceso secuencial.
• Cada elemento ocupa más memoria,
  • Debemos guardar el apuntador.

Usando la estructura de nodo es posible definir una pila de tamaño no acotado.

#include <stdio.h>
#include <stdlib.h>

struct nodo{
  int valor;
  struct nodo *anterior;
};

struct stack{
   struct nodo *cima;
};

struct nodo* nuevoNodo(){
    struct nodo *nuevo;
    nuevo = malloc(sizeof(struct nodo));

    return nuevo;
};

void push(struct stack *pila, int elemento){
    struct nodo *nuevo, *viejaCima;
    
    nuevo = nuevoNodo();
    viejaCima = pila -> cima;
    
    nuevo -> valor = elemento;
    nuevo -> anterior = viejaCima;
    pila -> cima = nuevo;
 
    return;
}

int pop(struct stack *pila){
    int salida;
    struct nodo *viejaCima;
   
    viejaCima = pila -> cima;
    salida = viejaCima -> valor;
   
    pila -> cima = viejaCima -> anterior;
    
    free(viejaCima);
    return salida;
}

int main(){
     
     int i;
     struct stack pila;
     struct nodo piso; 
     
     pila.cima = NULL;
     
     int llenado[] = {1,2,3,4,5};
     
     for(i = 0; i < 5; i++){
        push(&pila, llenado[i]);
     }
     
     for(i = 5; i > 0; i--){
        printf("%d\n", pop(&pila));
     }
     return 0;
 }

La ventaja que tiene la implementación anterior de una pila en comparación con la lista ligada es que la operaciones push y pop son mucho más rápidas que agregarAlFinal y su equivalente, quitarDelFinal.

.

En términos informales, una cola o fila (queue) es una estructura que acomoda y mueve los datos como una fila de personas esperando un servicio: la primera persona en llegar es la primera en ser atendida, y cualquier nuevo cliente debe de colocarse después de la última persona presente.

Esta estructura de datos es una forma natural de organizar lo que en ingles se llama scheduling, que es el organizar procesos o eventos.

• Una cola o fila (queue) es una estructura de datos FIFO (First in, First out) lineal en donde la inserción de elementos (encolado, push) y la remoción y consulta de estos (desencolar, pop) se realizan en extremos opuestos de la linea.

• Estos extremos opuestos son llamados entrada (final, rear) y salida (principio, front) respectivamente.

• FIFO significa que el primer elemento que entra a la estructura de datos es el primero en salir.

• Las operaciones de inserción (encolado, push) y remoción (desencolar, pop) toman tiempo constante.
  • Es decir, no dependen del número de elementos guardados en la estructura.

• Las operaciones de inserción (encolado, push) y remoción (desencolar, pop) siempre cambian la longitud de la estructura.
  • pop siempre remueve el primer elemento de la estructura.

Algunas aplicaciones de las colas son las siguientes:

• Se usan en algoritmos que resuelven problemas de manera eficiente.
• Para organizar las tareas en un sistema.
• Para organizar las tareas en sistemas no computacionales.

Entre los tipos distintos de colas tenemos:

• Colas lineales (linear queues)
• Colas circulares (anillos, circular queue)
• Bícolas (double ended queue)
• Colas de prioridad (priority queue)

La desventaja principal de las pilas es el tiempo de acceso aleatorio:

Si asumimos que las operaciones de pull y push toman tiempo 1,

¿Cuál es el tiempo promedio que tarda el obtener un elemento en la posición \(i\) de una pila que contiene \(n\) elementos?

Hint: Ver la solución para pilas.

En forma similar una pila, podemos implementar una lista usando arreglos o listas ligadas.

• A la primera opción se le conoce como almacenamiento contiguo o estático.

• A la segunda almacenamiento ligado o dinámico.

En general, para implementar una lista necesitamos guardar la dirección de la entrada y la salida y poco más.

Para implementar una pila de almacenamiento contiguo necesitamos.

• Un espacio contiguo en memoria del mismo tipo (arreglo).
• Dos variables que guarden la entrada y salida respectivamente (dentro del arreglo).

#include <stdio.h>
#define MAXCOLA 20

struct queue{
    int elementos[MAXCOLA];
    int entrada;
    int salida;
};

void push(struct queue *cola, int elemento){
  
    cola -> entrada++;
    (cola -> elementos)[cola -> entrada]=elemento;

    return;
}

int pop(struct queue *cola){
    int resultado;
    
    resultado = (cola -> elementos)[cola -> salida];
    cola -> salida++;
    
    return resultado;
}

int main(){
     int i;
     struct queue cola;
     
     cola.salida = 0;
     cola.entrada = -1;
     
     int llenado[] = {1,2,3,4,5};
     
     for (i=0;i<5; i++){
         push(&cola, llenado[i]);
     }
     
     for (i=0;i<5; i++){
         printf("%d\n",pop(&cola));
     }
     return 0;
 }
 

.

#include <stdio.h>
#define MAXCOLA 5

struct queue{
    int elementos[MAXCOLA];
    int entrada;
    int salida;
};

//Consulta
int arregloToroC(int *arreglo, int n, int indice){
    int i;
    i = indice % n;
    return arreglo[i];
}

//Asignacion
void arregloToroA(int *arreglo, int n, int indice, int val){
    int i;
    i = indice % n;
    arreglo[i] = val;
}

void push(struct queue *cola, int elemento){
  
    cola -> entrada++;
    //(cola -> elementos)[cola -> entrada]=elemento;
    arregloToroA(cola -> elementos, MAXCOLA, cola -> entrada, elemento);
    
    return;
}

int pop(struct queue *cola){
    int resultado;
    //resultado = (cola -> elementos)[cola -> salida];
    resultado = arregloToroC(cola -> elementos, MAXCOLA, cola -> salida);
    cola -> salida++;
    return resultado;
}

int main(){
     int i,j;
     struct queue cola;
     cola.salida = 0;
     cola.entrada = -1;
     
     int llenado[] = {1,2,3,4,5};
     
     for(j=0;j<3;j++){
        for (i=0;i<5; i++){
         push(&cola, llenado[i]);
        }
        for (i=0;i<5; i++){
         printf("%d\n",pop(&cola));
        }
        printf("-----\n");
     }
     return 0;
 }

.

Es posible implementar una cola de almacenamiento dinámico usando listas ligadas.

Recordemos que los elementos o eslabones de una lista ligada simple son estructuras, comúnmente llamados nodos, que guardan la dirección de memoria del siguiente eslabón de la cadena y el valor guardado correspondiente.

Para implementar una cadena de memoria dinámica necesitamos guardar dos direcciones de memoria:

• La dirección de memoria del nodo de entrada.

• La dirección de memoria del nodo de salida.

Y poco más.

#include <stdio.h>
#include <stdlib.h>

struct nodo{
  int valor;
  struct nodo *siguiente;
};

struct nodo* nuevoNodo(){
    struct nodo *nuevo;
    nuevo = malloc(sizeof(struct nodo));

    return nuevo;
};

struct queue {
    struct nodo *entrada;
    struct nodo *salida;
};

void push(struct queue *cola, int elemento){
    struct nodo *nuevo;
    
    nuevo = nuevoNodo();
    nuevo -> valor = elemento;
    nuevo -> siguiente = NULL;
    
    if(cola->entrada==NULL){
        cola->entrada = nuevo;
        cola->salida = nuevo;
        return;
        }
 
    cola -> entrada -> siguiente = nuevo;
    cola -> entrada = nuevo;
    
    return;
}

int pop(struct queue *cola){
    int salida;
    struct nodo *viejaSalida;
    
    viejaSalida = cola -> salida;
    salida = viejaSalida -> valor;
    
    if(cola ->salida == cola ->entrada){
        cola -> entrada = NULL;
        cola -> salida = NULL;
    } else {
        cola -> salida = viejaSalida -> siguiente;
        }
    
    free(viejaSalida);
    return salida;
}

int main(){
     int i,j;
     struct queue cola;
     
     cola.salida = NULL;
     cola.entrada = NULL;
     int llenado[] = {1,2,3,4,5};
     
     for(j=0;j<3;j++){
        for (i=0;i<5; i++){
         push(&cola, llenado[i]);
        }
        printf("Termino llenado.\n\n");
        for (i=0;i<5; i++)
          printf("%d) %d\n",i+1,pop(&cola));
        printf("-----\n");
     }
     return 0;
 }

.

De forma similar a las pilas, podemos considerar a las colas de almacenamiento dinámico como un caso en particular de una lista ligada.

Por lo anterior, la ventajas y desventajas de la implementación dinámica en comparación con una implementación estática son similares a la de una lista en comparación con un arreglo.

Ventajas:

• Son de tamaño (en teoría) indefinido.
• Se reserva solo el espacio que se usa.
• Se pueden almacenar de forma no contigua.
• Se pueden almacenar en desorden.

Desventajas :

• Son de acceso secuencial.
• Cada elemento ocupa más memoria,
  • Debemos guardar el apuntador.

Una cola circular de memoria estática es aquella en donde el último y el primer elemento del arreglo que contiene a las entradas de la pila se ve como un círculo en vez de una linea.

.

• Podemos considerar a esta estructura nuestra primer estructura no lineal.

• La implementación ya la realizamos y se encuentra en la página 45 de este documento.

• La implementación de colas circulares dinámicas se realiza de manera natural en listas circulares.

  • Únicamente es necesario guardar una dirección de memoria.

Una lista circular es aquella que en donde el último elemento de esta hace referencia al primero.

.

#include <stdio.h>
#include <stdlib.h>

struct nodo{
  int valor;
  struct nodo *siguiente;
};

struct nodo* nuevoNodo(){
    struct nodo *nuevo;
    nuevo = malloc(sizeof(struct nodo));

    return nuevo;
};

struct queue {
    struct nodo *entrada;
};

void push(struct queue *cola, int elemento){
    struct nodo *nuevo;
    
    nuevo = nuevoNodo();
    nuevo -> valor = elemento;
    
    if (cola -> entrada == NULL){
            nuevo -> siguiente = nuevo;}
        else{
            nuevo -> siguiente = cola -> entrada -> siguiente;
            cola -> entrada -> siguiente = nuevo;
        }
        
    cola -> entrada = nuevo;
    
    return;
}

int pop(struct queue *cola){
    int salida;
    struct nodo *nuevaSalida, *viejaSalida;
    
    viejaSalida = cola -> entrada -> siguiente;
    nuevaSalida = viejaSalida -> siguiente;
    salida =viejaSalida -> valor;
    
    if(viejaSalida == nuevaSalida){
        cola -> entrada = NULL;
    } else {
    cola -> entrada -> siguiente = nuevaSalida; 
    }
    
    free(viejaSalida);
    
    return salida;
}

int main(){
     int i,j;
     struct queue cola;
     
     cola.entrada = NULL;
     
     int llenado[] = {1,2,3,4,5};
     for(j=0;j<3;j++){
        for (i=0;i<5; i++){
         push(&cola, llenado[i]);
        }
        printf("Termino llenado.\n\n");
        for (i=0;i<5; i++)
          printf("%d) %d\n",i+1,pop(&cola));
        printf("-----\n");
     }
     
     return 0;
 }

.

.