ESCUELA POLITECNICA NACIONAL

FACULTAD DE INGENIERIA EN SISTEMAS

Estructura de datos

Nombre: Alexander Pinchao

Tema: Pilas y Colas

PILASLas pilas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a la posición en la cual pueden realizarse las inserciones y las extracciones de elementos. Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella. En la vida cotidiana existen muchos ejemplos de pilas, una pila de platos en una alacena, una pila de latas en un supermercado, una pila de papeles sobre un escritorio, etc. Debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce como estructura LIFO (Last In, First Out: último en entrar, primero en salir).Representación en MemoriaLas pilas no son estructuras de datos fundamentales, es decir, no están definidas como tales en los lenguajes de programación. Las pilas pueden representarse mediante el uso de :• Arreglos.• Listas enlazadas.Cuando usamos pilas con arreglos, debemos definir el tamaño máximo de la pila, además de un apuntador al último elemento insertado en la pila el cual denominaremos SP(stack pointer ). Cuando utilizamos arreglos para implementar pilas, tenemos la limitante de espacio de memoria reservada. Una vez establecido un máximo de capacidad para la pila, ya no es posible insertar más elementos esto se puede solucionar mediante el uso de espacios compartidos de memoria .La representación gráfica de una pila con arreglo es la siguiente:

Pila utilizando arreglos

Mientras que usando listas enlazadas el limite de la extensión de nuestra pila esta dado por la cantidad de memoria, es decir nuestra pila va creciendo o decreciendo a medida que se agregan o se retiran elementos de la misma.

Pila utilizando listas enlazadas

Operaciones en PilasLas pilas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de "push" y "pop":• Push: Añadir un elemento al final de la pila.• Pop: Leer y eliminar un elemento del final de la pila.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 siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.Las operaciones con pilas son muy simples, no hay casos especiales, salvo que la pila esté vacía.Push en una pila vacía..-Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a la pila valdrá NULL.

El proceso es muy simple, bastará con que:1. nodo->siguiente apunte a NULL.2. Pila apunte a nodo.

Push en una pila no vacía.-Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que podemos y debemos trabajar con una pila vacía como con una pila normal.De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una pila, en este caso no vacía.

El proceso sigue siendo muy sencillo:1. Hacemos que nodo->siguiente apunte a Pila.2. Hacemos que Pila apunte a nodo.

Pop, leer y eliminar un elementoAhora sólo existe un caso posible, ya que sólo podemos leer desde un extremo de la pila. Partiremos de una pila con uno o más nodos, y usaremos un puntero auxiliar, nodo.

1. Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila.2. Asignamos a Pila la dirección del segundo nodo de la pila: Pila->siguiente.3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación pop equivale a leer y borrar.

4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

Si la pila sólo tiene un nodo, el proceso sigue siendo válido, ya que el valor de Pila->siguiente es NULL, y después de eliminar el último nodo la pila quedará vacía, y el valor de Pila será NULL.Algoritmo de la función "push":1. Creamos un nodo para el valor que colocaremos en la pila.2. Hacemos que nodo->siguiente apunte a Pila.3. Hacemos que Pila apunte a nodo.Algoritmo de la función "pop":1. Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila.2. Asignamos a Pila la dirección del segundo nodo de la pila: Pila->siguiente.3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación pop equivale a leer y borrar.4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.Las clases para pilas son versiones simplificadas de las mismas clases que usamos para listas.Para empezar, necesitaremos dos clases, una para nodo y otra para pila. Además la clase para nodo debe ser amiga de la clase pila, ya que ésta debe acceder a los miembros privados de nodo.Los algoritmos para Push y Pop son los mismos que en C, tan sólo cambia el modo de crear y destruir nodos.Cabecera para pilas <stack> Provee la clase adaptadora contenedora std::stack, una pila de datos.El contenedor subyacente puede ser cualquiera de las plantillas de clase de contenedores estándar o alguna otra clase diseñado específicamente contenedor. El único requisito es que soporta las operaciones siguientes:

back() push_back() pop_back()

Por lo tanto se pueden usar las clases contenedoras de plantillas para vectores, listas y colas En caso de no definirse un modelo a seguir el contenedor usado será deque.template < class T, class Container = vector<T> > class stack;T: Tipo de elementContainer :Tipo de contenedor que se esta ocupando para el ingreso y almacenamiento de los datos. Funciones miembro de la librería <stack>,Las funciones miembro de la librería <stack> son:

Crear: se crea la pila vacía. (Construct) Construct es una copia del argumento del numero de elementos pasado al constructor, de lo contrario es un recipiente vacío. para el numero de elementos, en caso de no ser dados los elementos, se devuelve como size ceroForma estándar explicit stack ( const Container& ctnr = Container() );Ejemplo del uso #include <iostream>#include <vector>#include <deque>#include <stack>using namespace std;

int main (){ deque<int> mydeque (3,100); // deque con 3 elementos vector<int> myvector (2,200); // vector con 2 elementos

stack<int> first; // pila vacia stack<int> second (mydeque); // stack copia de deque

stack<int,vector<int> > third; // stack vacia usando vector stack<int,vector<int> > fourth (myvector);

cout << "size of first: " << (int) first.size() << endl; cout << "size of second: " << (int) second.size() << endl; cout << "size of third: " << (int) third.size() << endl; cout << "size of fourth: " << (int) fourth.size() << endl;

return 0;}

Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty).Forma estándar bool empty () const;Ejemplo del uso #include <iostream>#include <stack>using namespace std;int main (){ stack<int> mystack; int sum (0); for (int i=1;i<=10;i++) mystack.push(i); while (!mystack.empty()) { sum += mystack.top(); mystack.pop(); } cout << "total: " << sum << endl; return 0;}Tamaño: regresa el número de elementos de la pila. (size)Forma estándar tamaño size_type () const;ejemplo de uso #include <iostream>#include <stack>using namespace std;int main (){ stack<int> myints; cout << "0. size: " << (int) myints.size() << endl; for (int i=0; i<5; i++) myints.push(i); cout << "1. size: " << (int) myints.size() << endl; myints.pop(); cout << "2. size: " << (int) myints.size() << endl;

return 0;}

Apilar: se añade un elemento a la pila.(push)Forma estándar void push ( const T& x );Ejemplo de uso#include <iostream>#include <stack>using namespace std;

int main (){ stack<int> mystack;

for (int i=0; i<5; ++i) mystack.push(i);

cout << "Popping out elements..."; while (!mystack.empty()) { cout << " " << mystack.top(); mystack.pop(); } cout << endl;

return 0;}

Desapilar: se elimina el elemento frontal de la pila.(pop)Forma estándar void pop ( );Ejemplo de uso#include <iostream>#include <stack>using namespace std;int main (){ stack<int> mystack; for (int i=0; i<5; ++i) mystack.push(i); cout << " saltando elementos ..”; while (!mystack.empty()) { cout << " " << mystack.top(); mystack.pop(); } cout << endl; return 0;}

Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)Forma estándar value_type & top ();const value_type & top () const;Ejemplo de uso.-#include <iostream>#include <stack>using namespace std;int main (){ stack<int> mystack; mystack.push(10);

mystack.push(20); mystack.top() -= 5; cout << "mystack.top() ahora es " << mystack.top() << endl; return 0;}Llena: devuelve cierto si la pila está llena o falso en caso contrario (full).Forma estándar bool full() const;Ejemplo del uso #include <iostream>#include <stack>using namespace std;int main (){ stack<int> mystack; int sum (0); for (int i=1;i<=10;i++) mystack.push(i); do { sum += mystack.top(); mystack.pop(); } while (mystack.full()==0); cout << "total: " << sum << endl; return 0;}

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

A diferencia de las pilas , las colas son una especie de lista enlazada simple que en cada lectura

elimina el valor de la salida, que posee dos puntero que apuntal al inicio y al final de la lista por lo

tanto, las funciones se programan a “mano”, es decir no tenemos plantillas de uso

Nos encontramos ante una estructura con muy pocas operaciones disponibles. Las colas sólo

permiten añadir y leer elementos:

• Añadir: Inserta un elemento al final de la cola.

• Leer: Lee y elimina un elemento del principio de la cola.

Estructura de los nodo de la cola struct nodo

{

int nro;

struct nodo *sgte;

};

Estructura de la cola struct cola

{

nodo *delante;

nodo *atras ;

};

Agregar un elemento a la cola

Las operaciones con colas son muy sencillas, prácticamente no hay casos especiales, salvo que la

cola esté vacía.

Añadir elemento en una cola vacía:

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él,

además los punteros que definen la cola, primero y ultimo que valdrán NULL:

El proceso es muy simple, bastará con que:

1. nodo->siguiente apunte a NULL.

2. Y que los punteros primero y ultimo apunten a nodo.

Añadir elemento en una cola no vacía:

De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una cola, en este

caso, al no estar vacía, los punteros primero y ultimo no serán nulos:

El proceso sigue siendo muy sencillo:

1. Hacemos que nodo->siguiente apunte a NULL.

2. Después que ultimo->siguiente apunte a nodo.

3. Y actualizamos ultimo, haciendo que apunte a nodo.

Añadir elemento en una cola, caso general:

Para generalizar el caso anterior, sólo necesitamos añadir una operación:

1. Hacemos que nodo->siguiente apunte a NULL.

2. Si ultimo no es NULL, hacemos que ultimo->siguiente apunte a nodo.

3. Y actualizamos ultimo, haciendo que apunte a nodo.

4. Si primero es NULL, significa que la cola estaba vacía, así que haremos que primero apunte

también a nodo.

Leer un elemento de una cola(implica eliminarlo):

Ahora también existen dos casos, que la cola tenga un solo elemento o que tenga más de uno.

Leer un elemento en una cola con más de un elemento:

Usaremos un puntero a un nodo auxiliar:

1. Hacemos que nodo apunte al primer elemento de la cola, es decir a primero.

2. Asignamos a primero la dirección del segundo nodo de la pila: primero->siguiente.

3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de

lectura en colas implican también borrar.

4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

Leer un elemento en una cola con un solo elemento:

También necesitamos un puntero a un nodo auxiliar:

1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero.

2. Asignamos NULL a primero, que es la dirección del segundo nodo teórico de la cola: primero-

>siguiente.

3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de

lectura en colas implican también borrar.

4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

5. Hacemos que ultimo apunte a NULL, ya que la lectura ha dejado la cola vacía.

Leer un elemento en una cola caso general:

1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero.

2. Asignamos a primero la dirección del segundo nodo de la pila: primero->siguiente.

3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de

lectura en colas implican también borrar.

4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

Si primero es NULL, hacemos que ultimo también apunte a NULL, ya que la lectura ha dejado la

cola vacía.

Cabecera para colas

<queue>

cola son un tipo de adaptador del recipiente, específicamente diseñado para operar en un

contexto FIFO (primero en entrar, primero en salir), donde los elementos se insertan en un

extremo del recipiente y se extrae de la otra. La cola se implementan como adaptadores de

contenedores , que son clases que utilizan un objeto encapsulado de una clase de contenedor

específico como su contenedor subyacente , proporcionando un conjunto específico de funciones

miembro para acceder a sus elementos. Los elementos se empuja en el "back" del contenedor

específico y surgió a partir de su "frente". El contenedor subyacente puede ser un contenedor de

la plantilla de clase estándar o alguna otra clase diseñada específicamente contenedor. El único

requisito es que soporta las operaciones siguientes: front()

back()

push_back()

pop_front()

Estructura estandartemplate < class T, class Container = deque<T> > class queue;

T: Tipo de element

Container :Tipo de contenedor que se esta ocupando para el ingreso y almacenamiento de los

datos.

Funciones miembro de la librería <deque>

Las funciones miembro de la librería <deque> son:

Construir.-Construir cola y pasar como parámetros el tamaño que va ha tener la cola en caso de

no darse estos valores pasar la cola como vacia (construct)Estructura estándar explicit queue ( const Container& ctnr = Container() );

Ejemplo de manejo#include <iostream>#include <deque>#include <list>#include <queue>using namespace std;int main (){ deque<int> mydeck (3,100); // cola con 3 elementos list<int> mylist (2,200); // lista con 2 elementos queue<int> first; // cola vacía queue<int> second (mydeck); // cola copia de la primera queue<int,list<int> > third; // cola inicializada con la lista queue<int,list<int> > fourth (mylist); cout << "size of first: " << (int) first.size() << endl; cout << "size of second: " << (int) second.size() << endl; cout << "size of third: " << (int) third.size() << endl; cout << "size of fourth: " << (int) fourth.size() << endl; return 0;}

Vacío.- Probar si contenedor está vacío en caso de estar vacia enviar un true caso contrario un

false (empty).Estructura estándar bool empty () const;

Ejemplo de manejo#include <iostream>#include <queue>using namespace std;int main (){ queue<int> myqueue; int sum (0); for (int i=1;i<=10;i++) myqueue.push(i); while (!myqueue.empty()) { sum += myqueue.front(); myqueue.pop(); } cout << "total: " << sum << endl; return 0;}

Tamaño.- Volver tamaño de la cola como un valor entero (size)Estructura estándar size_type size ( ) const;

Ejemplo de manejo#include <iostream>#include <queue>using namespace std;int main (){ queue<int> myints; cout << "0. tamaño: " << (int) myints.size() << endl; for (int i=0; i<5; i++) myints.push(i); cout << "1. tamaño: " << (int) myints.size() << endl; myints.pop(); cout << "2. tamaño: " << (int) myints.size() << endl;

return 0;}

Alfrente.- Devuelve una referencia al siguiente elemento en la cola . Este es el "más antiguo"

elemento en la cola y el mismo elemento que se salió de la cola si es miembro cola (front)Estructura estándar const value_type y delantero () const;value_type y delantero ();

Ejemplo de manejo#include <iostream>#include <queue>using namespace std;int main (){ queue<int> myqueue; myqueue.push(77); myqueue.push(16); myqueue.front() -= myqueue.back(); // 77-16=61 cout << "la parte delantera de mi cola es " << myqueue.front() << endl; return 0;}

Atrás.- Devuelve una referencia al último elemento de la cola . Este es el "nuevo" elemento de la

cola es decir, el último elemento empujado en cola (back)Estructura estándar value_type& back ( );const value_type& back ( ) const;

Ejemplo de manejo#include <iostream>#include <queue>using namespace std;int main (){ queue<int> myqueue; myqueue.push(12); myqueue.push(75); // este es el final ahora myqueue.back() -= myqueue.front(); cout << "la parte final de mi cola es: " << myqueue.back() << endl;

return 0;}

Empuje.- Añade un nuevo elemento al final de la cola , después de su último elemento actual

(push)Estructura estándar void push ( const T& x );

Ejemplo de manejo#include <iostream>#include <queue>using namespace std;int main (){ queue<int> myqueue; int myint; cout << "ingrese un numero entero:\n"; do { cin >> myint; myqueue.push (myint); } while (myint);

cout << "mi cola tiene: "; while (!myqueue.empty()) { cout << " " << myqueue.front(); myqueue.pop(); } return 0;}

Saltar.- Elimina el siguiente elemento de la cola, la reducción efectiva de su tamaño por uno. El

elemento eliminado es el "más antiguo" elemento en la cola (pop)Estructura estándar void pop ( );

Ejemplo de manejo#include <iostream>#include <queue>using namespace std;int main (){ queue<int> myqueue; int myint; cout << "Please enter some integers (enter 0 to end):\n";

do { cin >> myint; myqueue.push (myint); } while (myint);

cout << "mi cola contiene: "; while (!myqueue.empty()) { cout << " " << myqueue.front(); myqueue.pop(); } return 0;

}