ANSI C tarea: Pilas y Colas

Pilas (Stacks)

Las pilas son estructuras de datos tipo LIFO (Last In First Out). Esto significa que funcionan de la siguiente manera: cuando se le agrega un nuevo elemento, éste siempre aparece al principio de la lista de elementos y cuando es cuestión de remover un elemento, siempre se remueve el último elemento agregado (que se encuentra al principio de la lista de elementos, en la cabecera de la pila).

Es de tipo lineal, es decir, sus elementos están acomodados en línea recta y además, puede generarse a partir de arreglos (de manera estática) o con listas enlazadas (de manera dinámica). La mayoría de los lenguajes de programación disponen de un dato tipo Pila, sin embargo, es necesario conocer y comprender su funcionamiento para poder hacer un uso adecuado de éste.

Se consideran 4 operaciones primitivas que pueden realizarse sobre una pila:

1. Inserción. Consiste en agregar datos o elementos a una pila. Se le conoce como push
2. Eliminación. Es la supresión de datos y se le conoce como pop
3. Obtener elemento en el tope (es decir, el elemento primero). A esta operación se le conoce como stacktop y permite obtener el primer elemento de la pila, sin eliminarlo.
4. Pila vacía. Es un método que regresa verdadero si la pila está vacía o falso de lo contrario. Se le conoce como empty.

Colas (Queues)

Son estructuras de datos tipo FIFO (First In First Out). Me agrada relacionarlas con la fila para comprar las tortillas: el primero en ser atendido e irse a casa es el primero que llega y el último en llegar se forma hasta atrás. Con las colas sucede lo mismo: cuando se saca un elemento de la cola, el elemento que sale es el primero que se colocó y que está al frente y cuando se agrega un elemento, éste se agrega hasta el final. Al igual que las pilas, las colas pueden generarse a partir de arreglos (de forma estática) o de listas enlazadas (de forma dinámica).

Existen diversos tipos de cola:

1. La cola circular. Representa a esta estructura de datos como un círculo y gracias a ello, no desaprovecha espacio como ocurre con una cola lineal estática.

2. La bicola o cola doble. Las inserciones y eliminaciones se pueden realizar tanto al inicio como al final. De ésta existen 2 tipos:

• Bicola de entrada restringida: Acepta eliminaciones tanto al inicio como al final, pero solamente acepta inserciones al final.
• Bicola de salida restringida: Acepta eliminaciones solo al inicio, pero las inserciones se pueden realizar tanto al inicio como al final.

3. Cola de prioridades. Es aquella en la que sus elementos tienen un cierto orden de acuerdo con el criterio que les asigna el programador. Hay dos tipos de cola de prioridades:

• Cola de prioridad ascendente. Sus elementos se pueden insertar de manera arbitraria, pero se acomodan dentro de la cola de manera que lleven un orden ascendente.
• Cola de prioridad descendente. Sus elementos se pueden insertar de forma arbitraria, pero se acomodan de manera descendente.

Estas son las operaciones primitivas o básicas que se pueden llevar a cabo con las colas:

1. Insertar un elemento.El nombre puede variar, pero en general a esta operación se le llama insert
2. Eliminación de un elemento. Operación remove. Cabe aclarar que con este nombre en particular tuve algunos problemas pues ya se encuentra definido en la libreria estándar stdio.h, así que usé la versión en español (remover) en el ejemplo que se encuentra al final de este post.
3. Cola vacía. Se encarga de verificar si una cola está vacía. Operación empty.

Ejemplo de implementación

A continuación se encuentra un ejemplo de cómo se modificó el código de las listas enlazadas visto en clase para que se comporte tanto como una pila como una cola.

Empecemos por la pila. Así quedó declarada una librería para pilas (al que llamé pilas.h):

#ifndef PILAS_H

#define PILAS_H

#include "bool.h"

// estructura de un elemento de la lista
struct elemento_de_lista {
  int dato; // donde la info va
  // doblemente enlazada
  struct elemento_de_lista* siguiente; // puntero
  struct elemento_de_lista* anterior; // puntero
}; // <= ojo con el punto y coma

// redefinición por brevedad
typedef struct elemento_de_lista elem;

// eliminar todos los elementos de la lista
elem* borrar_pila(elem* esto);

// checar si la lista contiene un valor dado
// devuelve verdad o falso
// recibe un puntero a un elemento de la lista
// implementacion recursiva
bool buscar_en_pila(int valor, elem* aqui);

// devuelve si o no se pudo eliminar
// (no se puede eliminar si no esta)
// valor cuyo elemento hay que eliminar
// (unicamente elimina el primer elemento
// cuyo valor coincide)
// elemento en el cual estamos buscando = aqui
// direccion del inicio de la lista
bool eliminar_elemento_pila(elem* aqui, 
         elem** inicio);

// interface para llamadas mas bonitas
bool pop(elem** inicio);

void imprime_elemento(elem* esto);

// interface que agrega [ ... ] y el \n
void imprimir_pila(elem* lista);

// agregar un elemento en la posicion que
// le corresponde (valores de menor a mayor)
elem* push(int valor, elem* aqui);

#define MAX 30
#define MIN 1

// numeros pseudoaleatorios [MIN, MAX]
int pseudoaleatorio();

#endif

Esta es la implementación de los métodos declarados en la librería (pilas.c):

#include <stdio.h> // imprimir (printf)
#include <stdlib.h> // reservar memoria
#include "pilas.h"

// eliminar todos los elementos de la lista
// opcion vaciar
elem* borrar_pila(elem* esto) {
  elem* temp; // auxiliar 
  // iterativa
  while (esto != NULL) {
    temp = esto->siguiente;
    free(esto); // liberar
    esto = temp; // avanza al siguinte
  }
  return NULL; // que ya no hay lista
}

// checar si la lista contiene un valor dado
// devuelve verdad o falso
// recibe un puntero a un elemento de la lista
// implementacion recursiva
bool buscar_en_pila(int valor, elem* aqui) {
  if (aqui != NULL) {

    printf("Buscando por %d en %d.\n", 
    valor, aqui->dato);

    // si el valor buscado esta en este elemento
    if (aqui->dato == valor) {

      printf("Son iguales.\n");

      return TRUE; // busqueda exitosa

    }
    // pasar la pelota al siguiente elemento
    return buscar_en_pila(valor, aqui->siguiente);
  }
  else { // aqui es null
    // este elemento actual ya es null, o sea,
    // no en realidad es un elemento

    printf("Ya se acabo. No estuvo.\n");
    return FALSE; // busqueda fallida
  }
}

// devuelve si o no se pudo eliminar
// (no se puede eliminar si no esta)
// valor cuyo elemento hay que eliminar
// (unicamente elimina el primer elemento
// cuyo valor coincide)
// elemento en el cual estamos buscando = aqui
// direccion del inicio de la lista
bool eliminar_elemento_pila(elem* aqui, 
         elem** inicio) {
  if (aqui != NULL) { // si hay algo
    *inicio = aqui->siguiente;
    free(aqui); // borrame      return TRUE; // eliminacion exitosa
    return TRUE;
    } 
  return FALSE;
}

// interface para llamadas mas bonitas
bool pop(elem** inicio) {
  return 
    eliminar_elemento_pila(*inicio, inicio);
}

void imprime_elemento(elem* esto) {
  // iterativa
  while (esto != NULL) {
    printf("%d ", esto->dato);
    esto = esto->siguiente;
  }
  return;
}

// interface que agrega [ ... ] y el \n
void imprimir_pila(elem* lista) {
  printf("[ ");
  imprime_elemento(lista);
  printf("]\n");
  return;
}

// agregar un elemento en la posicion que
// le corresponde (valores de menor a mayor)
elem* push(int valor, elem* aqui) {
  elem* nuevo = NULL; // auxiliar
  // para crear el nuevo elemento
 
  if (aqui != NULL) {
    printf("Estoy en %d, insertando un %d.\n",
    aqui->dato, valor);
  } else {
    printf("No hay nada.\n");
  }
 
  if (aqui == NULL) { // no hay nadie
    nuevo = (elem*)malloc(sizeof(elem));
    nuevo->dato = valor; // asignar dato
    nuevo->siguiente = NULL; // el unico
    nuevo->anterior = NULL; // el unico
    return nuevo;
  } 
  else {
    nuevo = (elem*)malloc(sizeof(elem));
    nuevo->dato = valor; // pon el valor
    nuevo->siguiente = aqui;
    aqui->anterior = nuevo;
    nuevo->anterior = NULL; 
  }
  return nuevo;
}

// numeros pseudoaleatorios [MIN, MAX]
int pseudoaleatorio() {
  return ((rand() % (MAX - MIN + 1)) + MIN);
}

En el archivo prueba_pilas.c se encuentra el método principal que manda a llamar a las rutinas propias de la pila (contenidas en pilas.c):

#include "pilas.h"
#include "entrada.h"
#include  // printf
#include  // srand

// rutina principal
int main(int argc, char** args) {
  elem* lista = NULL; // vacia al inicio
  int valor; // auxiliares
  char op;
  bool basta = FALSE;

  while (!basta) {
    printf("Que quieres hacer?\n");
    printf("Agregar = a\nBuscar = b\n");
    printf("Eliminar = e\nVaciar = v\n");
    printf("Imprimir = i\nSalir = s\n> ");
    op = pide_opcion("abevis");
    switch (op) {
    case 'a':
      valor = pide_numero(MIN, MAX);
      lista = push(valor, lista);      
      break;
    case 'b':
      valor = pide_numero(MIN, MAX);
      printf("%d %s esta en la lista.\n",
      valor, (buscar_en_pila(valor, lista) ? 
       "SI" : "NO"));
      break;
    case 'e':
      if (pop(&lista)) {
 printf("%d eliminado.\n", valor);
      } else {
 printf("Pila vacia.No pudo eliminarse informacion de la pila");
      }
      break;
    case 'v':
      lista = borrar_pila(lista);
      break;
    case 'i':
      imprimir_pila(lista);
      break;
    case 's':
      basta = TRUE;
      break;
    default:
      printf("Esto no deberia pasar nunca.\n");
      break;
    }
  }
  return 1; // ya no hacemos nada
}

En la siguiente imagen se aprecia la salida del programa para las pilas:

A continuación se encuentra el código para las colas. Esta es la libreria que contiene la funcionalidad de las colas (colas.h):

#ifndef COLAS_H

#define COLAS_H

#include "bool.h"

// estructura de un elemento de la lista
struct elemento_de_lista {
  int dato; // donde la info va
  // doblemente enlazada
  struct elemento_de_lista* siguiente; // puntero
  struct elemento_de_lista* anterior; // puntero
}; // <= ojo con el punto y coma

// redefinicion por brevedad
typedef struct elemento_de_lista elem;

// eliminar todos los elementos de la lista
elem* borrar(elem* esto);

// checar si la lista contiene un valor dado
// devuelve verdad o falso
// recibe un puntero a un elemento de la lista
// implementacion recursiva
bool buscar(int valor, elem* aqui);

// devuelve si o no se pudo eliminar
// (no se puede eliminar si no esta)
// valor cuyo elemento hay que eliminar
// (unicamente elimina el primer elemento
// cuyo valor coincide)
// elemento en el cual estamos buscando = aqui
// direccion del inicio de la lista
bool eliminar_elemento_cola(elem* aqui, 
         elem** inicio);

// interface para llamadas mas bonitas
bool remover(elem** inicio);

void imprime_elemento(elem* esto);

// interfase que agrega [ ... ] y el \n
void imprimir_cola(elem* lista);

// agregar un elemento en la posicion que
// le corresponde (valores de menor a mayor)
elem* insert(int valor, elem* aqui);

#define MAX 30
#define MIN 1

// numeros pseudoaleatorios [MIN, MAX]
int pseudoaleatorio();

#endif

En este archivo (colas.c) se realizaron las modificaciones necesarias para obtener el comportamiento de una cola (colas.c)

#include  // imprimir (printf)
#include  // reservar memoria
#include "colas.h"

// eliminar todos los elementos de la lista
// opcion vaciar
elem* borrar(elem* esto) {
  elem* temp; // auxiliar 
  // iterativa
  while (esto != NULL) {
    temp = esto->siguiente;
    free(esto); // liberar
    esto = temp; // avanza al siguinte
  }
  return NULL; // que ya no hay lista
}

// checar si la lista contiene un valor dado
// devuelve verdad o falso
// recibe un puntero a un elemento de la lista
// implementacion recursiva
bool buscar(int valor, elem* aqui) {
  if (aqui != NULL) {

    printf("Buscando por %d en %d.\n", 
    valor, aqui->dato);

    // si el valor buscado esta en este elemento
    if (aqui->dato == valor) {
      printf("Son iguales.\n");
      return TRUE; // busqueda exitosa
    } 
    // pasar la pelota al siguiente elemento
    return buscar(valor, aqui->siguiente);
  } else { // aqui es null
    // este elemento actual ya es null, o sea,
    // en realidad no es un elemento
    printf("Ya se acabo. No estuvo.\n");
    return FALSE; // busqueda fallida
  }
}

// devuelve si o no se pudo eliminar
// (no se puede eliminar si no esta)
// valor cuyo elemento hay que eliminar
// (unicamente elimina el primer elemento
// cuyo valor coincide)
// elemento en el cual estamos buscando = aqui
// direccion del inicio de la lista
bool eliminar_elemento_cola(elem* aqui, 
         elem** inicio) {
  if (aqui != NULL) { // si hay algo
    *inicio = aqui->siguiente;
    free(aqui); // borrame
      return TRUE; // eliminacion exitosa
  }
  return FALSE;
}

// interface para llamadas mas bonitas
bool remover(elem** inicio) {
  return 
    eliminar_elemento_cola(*inicio, inicio);
}

void imprime_elemento(elem* esto) {
  // iterativa
  while (esto != NULL) {
    printf("%d ", esto->dato);
    esto = esto->siguiente;
  }
  return;
}

// interface que agrega [ ... ] y el \n
void imprimir_cola(elem* lista) {
  printf("[ ");
  imprime_elemento(lista);
  printf("]\n");
  return;
}

// agregar un elemento en la posicion que
// le corresponde (valores de menor a mayor)
elem* insert(int valor, elem* aqui) {
  elem* nuevo = NULL; // auxiliar
  // para crear el nuevo elemento
 
  if (aqui != NULL) {
    printf("Estoy en %d, insertando un %d.\n",
    aqui->dato, valor);
  } else {
    printf("No hay nada.\n");
  }

    nuevo = (elem*)malloc(sizeof(elem));
    nuevo->dato = valor; // asignar dato 

  if (aqui == NULL) { // no hay nadie
    nuevo->siguiente = NULL; // el unico
    nuevo->anterior = NULL; // el unico
    return nuevo;
  } 
  else {
    if(aqui->siguiente != NULL){
      insert(valor, aqui->siguiente);
    }
    else{
      printf("Anexando al final.\n");
     
      aqui->siguiente = nuevo;
      nuevo->anterior = aqui;
      nuevo->siguiente = NULL; // el ultimo
    }
  }
  return aqui;
}

// numeros pseudoaleatorios [MIN, MAX]
int pseudoaleatorio() {
  return ((rand() % (MAX - MIN + 1)) + MIN);
}

El siguiente código muestra el método principal y la llamada a los métodos propios de la cola (prueba_colas.c):

#include "pilas.h"
#include "entrada.h"
#include  // printf
#include  // srand

// rutina principal
int main(int argc, char** args) {
  elem* lista = NULL; // vacia al inicio
  int valor; // auxiliares
  char op;
  bool basta = FALSE;

  while (!basta) {
    printf("Que quieres hacer?\n");
    printf("Agregar = a\nBuscar = b\n");
    printf("Eliminar = e\nVaciar = v\n");
    printf("Imprimir = i\nSalir = s\n> ");
    op = pide_opcion("abevis");
    switch (op) {
    case 'a':
      valor = pide_numero(MIN, MAX);
      lista = push(valor, lista);      
      break;
    case 'b':
      valor = pide_numero(MIN, MAX);
      printf("%d %s esta en la lista.\n",
      valor, (buscar_en_pila(valor, lista) ? 
       "SI" : "NO"));
      break;
    case 'e':
      if (pop(&lista)) {
 printf("%d eliminado.\n", valor);
      } else {
 printf("Pila vacia.No pudo eliminarse informacion de la pila");
      }
      break;
    case 'v':
      lista = borrar_pila(lista);
      break;
    case 'i':
      imprimir_pila(lista);
      break;
    case 's':
      basta = TRUE;
      break;
    default:
      printf("Esto no deberia pasar nunca.\n");
      break;
    }
  }
  return 1; // ya no hacemos nada
}

Finalmente, este es el resultado de la compilación y ejecución de colas.c, prueba_colas.c y entrada.c. Éste último es necesario compilarlo junto con los otros dos pues se hace uso de sus métodos para requerir valores al hipotético usuario:

Referencias

"Queue (data structure)". Wikipedia. The Free Encyclopedia, 2011.

"Stack (data structure)." Wikipedia. The Free Encyclopedia, 2011.

Apuntes de Estructuras de Datos. Semestre Agosto-Diciembre de 2010.