Las computadoras adquieren su nombre de su capacidad de computar, esto quiere decir que las computadoras son capaces de realizar cálculos sobre un conjunto de datos.

En su inicio, las computadoras se inventaron con el fin de facilitar y agilizar el procesamiento de datos, la primera computadora, la ENIAC, se empezó a construir durante la segunda guerra mundial, con el objetivo de cálcular los parámetros correctos de disparo de la artillería aliada, tomando en cuenta diferentes constantes, como lo eran la altitud, la velocidad del aire, etc.  Posteriormente, la UNIVAC se comercializó para universidades, dependencias de gobierno y empresas grandes con el fin de facilitar el procesamiento de datos, ya que era capaz de realizar algunos miles de sumas y restas por segundo.  La UNIVAC era capaz de hacer incluso algunas decenas de divisiones por segundo!

Hoy en día las computadoras se utilizan para una gran cantidad de aplicaciones, juegos de video, relojes, calculadoras portátiles, hornos de microondas, automóviles, laboratorios de investigación, procesamiento de imágenes, etc.  Sin embargo, aún cuando podría parecer que las computadoras han perdido el rumbo de su finalidad original, esto no es cierto.  Todas las aplicaciones actuales de las computadoras siguen siendo básicamente la manipulación y procesamiento de datos!

Por ejemplo, en un juego de video, la computadora debe procesar una serie de datos que representán un mundo virtual, como son, posiciones de los personajes, orientación de los mismos, puntos de vida, capacidad de ataque, etc.  con base en estos datos y la entrada del usuario, la computadora realizará operaciones sobre los mismos y determinará para el siguiente instante, que caracteres siguen vivos, cuales han cambiado sus puntos de vida, etc.

En un automóvil la computadora recibe datos de los sensores del auto y con base en los mismos, determina la cantidad de combustible y aire que debe introducir a los pistones para el óptimo rendimiento del carro.

Y así, por inverosímil que parezca, todas las aplicaciones de las computadoras en el mundo actual se basan en el procesamiento de los datos adquiridos para obtener el resultado buscado.

Ya sabemos que el principal objetivo de las computadoras es el de realizar cálculos a un conjunto de datos, pero, ¿De dónde obtiene los datos? ¿Los recibe uno por uno, o todos a la vez? ¿Dónde los almacena? ¿Los procesa todos de manera simúltanea o uno por uno?

Aunque existen varios modelos computacionales, el más común cuenta con un espacio de almacenamiento llamado "memoria" y una Unidad Central de Procesos (CPU).  En la memoria se almacenan los datos y el programa que procesa los mismos, la Unidad Central de Procesos se encarga de ejecutar los comandos del programa, al final de la ejecución los datos han sido procesados.  

La memoria no es mas que un medio de almacenamiento capaz de "recordar" una serie de datos, lo común es que los datos almacenados en una memoria sean datos binarios, es decir, una serie de '1' y '0's que representan algo.  Sin embargo, conocer el contenido de la memoria, sirve de muy poco si no sabes de antemano lo que los datos representan.  Por ejemplo, la cadena binaria

A menudo resulta más sencillo describir las estructuras de datosen función de las operacioens efectuadas, en lugar de hacerlo en términos de los detalles de la implementación.  Cuando se define de esta forma una estructura de datos, se denomina tipo de datos abstracto. La idea es separar el "concepto" de lo que debe hacer la estructura de datos de cualquier implementación particular. 

Cuando una estrutura de datos se define de manera completa, es decir, no únicamente con la descripción de las operaciones, sino con la implementación de las mismas se conoce como tipo de datos concreto.  

En estos apuntes se analízaran varias estructuras de datos.  Todas las estructuras se verán desde un punto de vista abstracto en su definición y posteriormente se presentará una implementación de las operaciones para una estructura de datos que maneje enteros.  

Es importante observar que aunque el tipo de datos concreto se presentará con números enteros, ustedes pueden modificar la implementación para que soporte cualquier tipo de datos, inclusive, tipos de dato compuestos.  Lo importante es que cumpla con la definición del tipo de datos abstracto.

INICIO

La PILA es quizá la estructura de datos común con un acceso más restrictivo, y sin embargo es quizá también la más usada en el funcionamiento diario de cualquier programa de cómputo.

La PILA cuenta únicamente con dos operaciones básicas: se puede insertar un dato al inicio de la  pila, y se puede remover un dato del inicio de la  pila.

La pila, como puede inferirse, deriva su nombre de que los datos se apilan uno sobre otro, ocasionando que en cualquier momento únicamente se tenga acceso al dato superior de la pila.  La pila funciona como si hicieran una pila de cajas de refrescos, cuando llega una nueva caja, la ponen hasta arriba de la pila, ya que sería mucho trabajo levantar todas las cajas para poder meterla nueva caja hasta abajo.  Cuando se necesita un refresco se retira de la caja superior, si esta se vacía, entonces se remueve y se prosigue con la siguiente caja.  Como se habrán dado cuenta, existe la posibilidad de que una caja de refrescos quede olvidada en la parte inferior de la pila y se eche a perder. ¡Sin embargo, un taquero con éxito, debe ser capaz de terminar con toda la pila sin que ningún refresco se le eche a perder!  

A las pilas se les conoce en la literatura como estructuras LIFO por sus siglas en inglés (Last In - First Out), que quiere decir, que el último que entro es el primero que sale.  De ahí el consabido dicho de "Los últimos serán los primeros".

Las pilas tienen un campo de aplicación muy grande en los programas, el más común es la recursividad, aunque tal vez no lo notaron, ya que el compilador lo hace por ustedes, para poder implementar cualquier rutina recursiva es necesario contar con una pila.  En la sección de ejercicios se revisarán aplicaciones de una pila para implementar recursión y para analizar una sentencia.

Una buena implementación de pila debe de tomar en cuenta dos puntos.  El primero es que no debe permitir el remover un dato cuando la pila esta vacía, y el segundo es que no debe permitir que se inserten datos a la pila si esta ya esta llena.

A continuación se muestra la implementación de una pila en C y en Pascal utilizando memoria estática.

Las COLAS, al igual que las pilas, son una estructura de datos de acceso restrictivo.  Al igual que en una pila únicamente se cuenta con 2 operaciones, la operación insertar y la operación remover.   

La diferencia entre una cola y una pila es que en la cola (como en una cola para comprar boletos), el primero que llegó es al primero que se atiende, es decir, una cola tiene un inicio y un final, los nuevos elementos que llegan se agregan al final de la cola, cuando se remueve un elemento, se remueve del inicio de la misma.

A las colas se les conoce como estructuras FIFO (First In - First Out), que quiere decir que el primero que entra, es el primero que sale.

Existe una implementación muy común de la cola que se conoce como cola circular, esta implementación aprovecha el espacio en memoria de la computadora de la siguiente forma: inicialmente aparta un espacio para la cola, conforme llegan los elementos los va agregando al final, cuando remueve un elemento lo hace del inicio de la cola, una vez que ha terminado con el espacio de memoria que había apartado, revisa si ya se liberó el espacio al inicio de la cola y "da la vuelta" para aprovechar el espacio al máximo, la implementacion que se presenta a continuación es la de una cola circular.

Al igual que en la pila, en la cola es muy importante revisar si todavía hay espacio para seguir guardando elementos, o si la cola esta vacía.