Tarea#1 - Filas y Pilas

Filas (Queue) y Colas(Stacks)

En esta ocasión, nos toco hablar acerca de algunas estructuras de datos, en este caso particularmente de las estructuras de datos lineales, que son las Filas que también son conocidas como Colas y las Pilas, particularmente estas dos estructuras se comportan como una Lista que también es una estructura de datos lineal pero con característica especial cada una.
Estas tres estructuras son dinámicas, aunque, dependiendo del lenguaje en el que se este implementanto se puede implementar usando un array con longitud fija pero resulta ser ineficiente tanto en memoria como en forma de implementación.

Otra cuestión acerca de la implementación es la gran ayuda en lenguajes de muy alto nivel como lo que es Python ya que por defecto contiene una estructura de datos que son las listas. Esta estructura de datos, que también es un objeto, contiene una serie de métodos que además lo vuelven dinámico que ya nos sirven para agregar elementos y eliminar elementos en cualquier posición, entre otros. Las listas en Python se puede acceder a cualquier elemento de ella por medio de indices como en los Arrays, de echo, en este lenguaje no existen los arrays sino que de forma generica se utilizan las listas como arrays gracias a su gran potencial.
Python tiene también una característica muy especial que es la compresión de listas que nos permiten entre otras cosas darles valores iniciales a los elementos de la lista en una sola linea de código. Por otro lado Python contiene partición o rebanado de listas (list slicing), el cual consiste en a parir de una lista obtener una parte de ella solamente.

ej. en Python interactivo

>>> [0 for i in range(10)] #compresión de listas
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>> [i for i in range(10)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>
>>> list = [i for i in range(10)]
>>> list[3:7] #regresa los elementos desde el indice 3 al elemento anterior al 7 indice
[3, 4, 5, 6]
>>> list[-1] #regresa el último elemento
9
>>>
>>> list[::-1]#regresa la lista invertida
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]|

Para una mejor referencia recomiendo esta liga: http://docs.Python.org/2/tutorial/introduction.html#lists

Filas o Colas (Queues)

Son estructuras de datos similares a las listas pero con comportamiento especial ya que se unicamente se puede acceder al ultimo y primer elemento de ella, ya que contiene una estructura FIFO(First in First Out) es decir, el primero que entra es el primero que sale de esta colección.
Por su comportamiento nos dice que solamente para poder insertar elementos en ella se puede al final y para poder eliminar elementos se realiza del principio.
Las operaciones principales de las Filas son:

1. Crear: Se crea la Fila Vacía.
2. Encolar (añadir, entrar, push): Se añade un elemento al final de esta.
3. Desencolar(sacar, salir, pop): Se elimina un elemento al principio o frente de esta, es decir el primer elemento que entró.
4. Frente: (mostrar, consultar, front): se devuelve el elemento frontal, es decir, el primer elemento que entró.

En Python es posible utilizar una lista como una Fila, sin embargo, no son eficientes para este propósito. Mientras que agrega y elimina elementos al final de la lista lo hacen rápido, hacier inserciones o remover del principio resulta ser mucho mas lento ya que cada elemento se debe de recorrer por uno. Por tal motivo para poer implementar Filas utilizaremos "deque" del módulo collections, que fue diseñado para insertar o eliminar elementos de cualquier extremo.

ej. en Python interactivo.

>>> from collections import deque
>>> fila = deque(["Marin", "Constantino", "Marco"]) #se puede utilizar esto fila = deque([]) para crear la pila vacía.
>>> fila.append("Oscar")
>>> print fila
deque(['Marin', 'Constantino', 'Marco', 'Oscar'])
>>> fila.append("Pepe")
>>> print fila
deque(['Marin', 'Constantino', 'Marco', 'Oscar', 'Pepe'])
>>> fila.popleft()
'Marin'
>>> print fila
deque(['Constantino', 'Marco', 'Oscar', 'Pepe'])
>>> fila.popleft()
'Constantino'
>>> fila
deque(['Marco', 'Oscar', 'Pepe'])

Para una información más amplia recomiendo esta liga: http://docs.python.org/2/library/collections.html

Pilas (Stacks)

Al igual que las Filas las Pilas o Stacks son estructuras de datos similares a las lista y su comportamiento especial es que que sólo se puede acceder al último elemento de ella, contiene una estructura LIFO (Last in First Out) es decir, el último elemento en entrar es el primero en salir. Una analogía es cuando apilas platos en la alacena, se va poniendo uno sobre otro y a la hora de utilizarlo lo más conveniente es utilizar el que está más por encima es decir el último en entrar.
Sus operaciones son similares a las de las Filas:

1. Crear: Se crea la pila vacía.
2. Apilar: Se añade un elemento al final de la pila (push).
3. Desapilar: Se elimina un elemento al final de la pila (pop).
4. Tope: Devuelve el elemento final de la pila o que está en la cima de ella. (top).
5. Vacía: Devuelve True si la pila está vacía o false en caso contrario.

En Python los métodos de las listas hacen que sea muy fácil de utilizar una lista como una pila, donde el último elemento añadido es el primer elemento recuperado. Para añadir un elemento a la parte superior de la pila, use "append()". Para recuperar un elemento de la parte superior de la pila, use "pop()" sin un índice explícito.

ej. en Python interactivo:

>>> stack=[] #se crea la pila vacía
>>> stack.append(6)
>>> stack.append(5)
>>> stack.append(7)
>>> stack.append(5)
>>> stack
[6, 5, 7, 5]
>>> stack.pop()
5
>>> stack.pop()
7
>>> stack
[6, 5]
>>> stack.append(45)
>>> stack
[6, 5, 45]
>>>

Para terminar, en Python tambien se pueden hacer implementaciones un poco más complejas de estas estructuras de datos, empleados mediante Nodos que apuntas a los diferentes elementos, como lo hacíamos en la programación en el lenguaje ANSI C, pero la intención de esta entrada es mostrar la simplicidad de Python para manipular estructuras de datos y realizarlo de una forma más didáctica. También existen operaciones que no mencione en la parte de código, que es para validar si esta vacía o obtener el lemento tope o fondo según cada estructura. Pero en Python es muy intuitivo saberlo como para encontrar el tope pues se usa lista[len(lista)], para fondo pues es lista[0] podemos crear métodos que realicen este tipo de búsquedas de una forma más general. Por otra parte existe un módulo Queue que principalmente es utilizada para el procesamiento de Hilos, maneja Filas de prioridad, Listas FIFO o LIFO, entre otras funcionalidades. Para más información acerca de este módulo y para no hacer esta entrada más extensa, se recomienda esta liga: http://docs.python.org/2/library/queue.html