Republica Bolivariana de Venezuela

Ministerio del Poder Popular para la Educacion Superior

Universidad Politecnica Territoria Jose Antonio Anzoategui
Barcelona Estado Anzoategui.

Profesor: Alumno:

Jesús Cardozo Morales Roygel C.I: 20.873.220

Sección 3 – 2do semestre Informática

Turno: Noche - Calatrava

Barcelona, 26 de Noviembre de 2018

 INTRODUCCION

En el próximo contexto a dichas listas también conocidas como secuencio o

colecciones de datos. Según autores están en parte en lo correcto ya que una lista
de cualquier tipo es una estructura ideada con el propósito de albergar datos
agrupados bajo un mismo nombre. Es así como este trabajo se descubrirá la
forma de operación de tres tipos comunes de listas conocidas como: pilas, colas
en programación, el uso de listas es una práctica tan extendida que lenguajes
tales Java, Python y C++ soportan los mecanismos necesarios para trabajar con
estructuras de Vectores, pilas , colas, listas, etc.
1.-) ¿Que son pila o Stacks?

Una pila es una estructura en donde cada elemento es insertado y retirado

del tope de la misma, y debido a esto el comportamiento de un una pila se conoce
como LIFO (último en entrar, primero en salir).

Un ejemplo de pila o stack se puede observar en el mismo procesador, es

decir, cada vez que en los programas aparece una llamada a una función el
microprocesador guarda el estado de ciertos registros en un segmento de
memoria conocido como Stack Segment, mismos que serán recuperados al
regreso de la función.

Pila en arreglo estático

En el programa que se verá en seguida, se simula el comportamiento de

una estructura de pila. Aunque en el mismo se usa un arreglo estático de tamaño
fijo se debe mencionar que normalmente las implementaciones hechas por
fabricantes y/o terceras personas se basan en listas dinámicas o enlazadas.

Para la implementación de la clase Stack se han elegido los métodos:

 Put( ), poner un elemento en la pila

 Get( ), retirar un elemento de la pila
 Empty( ), regresa 1 (TRUE) si la pila esta vacía
 Size( ), número de elementos en la pila

El atributo SP de la clase Stack es el puntero de lectura/escritura, es decir,

el SP indica la posición dentro de la pila en donde la función put() insertará el
siguiente dato, y la posición dentro de la pila de donde la función get() leerá el
siguiente dato.
 Cada vez que put() inserta un elemento el SP se decrementa.
 Cada vez que get() retira un elemento el SP se incrementa.

En el siguiente ejemplo se analiza lo que sucede con el SP (puntero de pila)

cuando se guardan en la pila uno por uno los caracteres 'A', 'B', 'C' y 'D'. Observe
que al principio el SP es igual al tamaño de la pila.

 llenando la pila
SP

Al principio (lista vacía)

SP

A Push ( ‘A’ ) ; después de haber agregado

el primer elemento.

SP

D C B A Después de haber agregado cuatro elemento.

 Vaciando la pila.

SP

D C B A Pop ( );
Después de haber retirado un elemento

SP

D C B A Después de haber retirado todos los

elemento.
Ejemplo: pila basada en un arreglo estático

#include <iostream>
using namespace std;
#define STACK_SIZE 256 /* capacidad máxima */
typedef char arreglo[STACK_SIZE];
class Stack {
int sp; /* puntero de lectura/escritura */
int items; /* número de elementos en lista */
int itemsize; /* tamaño del elemento */
arreglo pila; /* el arreglo */
public:
// constructor
Stack() {
sp = STACK_SIZE-1;
items = 0;
itemsize = 1;
}
// destructor
~Stack() {};
/* regresa el número de elementos en lista */
int size() { return items; }
/* regresa 1 si no hay elementos en la lista, o sea, si la lista está vacia */
int empty() { return items == 0; }
/* insertar elemento a la lista */
int put(char d)
{
if ( sp >= 0) {
pila[sp] = d;
sp --;
items ++;
}
return d;
}
/* retirar elemento de la lista */
int get()
{
if ( ! empty() ) {
sp ++;
items --;
}
return pila[sp];
}
}
// fin de clase Stack
// probando la pila.
// Nota: obseve cómo los elementos se ingresan en orden desde la A hasta la Z,
// y como los mismos se recuperán en orden inverso.
int main()
{
int d;
Stack s; // s es un objeto (instancia) de la clase Stack
// llenando la pila
for (d='A'; d<='Z'; d++) s.put(d);
cout << "Items =" << s.size() << endl;
// vaciando la pila
while ( s.size() ) cout << (char)s.get() << " ";
cout << "\nPara terminar oprima <Enter>...";
cin.get();
return 0;
}
}

Pila dinámica

En el siguiente programa se presenta una implementación de una

estructura dinámica tipo pila o stack. Es importante hacer notar que, a diferencia
de una pila basada en un arreglo estático, una pila enlazada dinámicamente no
posee de forma natural el mecanismo de acceso por índices, en ese sentido, el
programador puede crear los algoritmos necesarios para permitir tal
comportamiento. En la clase que presentaremos en el ejemplo no se ha
implementado el mecanismo de acceso por índices, ya que la misma se presenta
como una alternativa para la simulación de una pila o stack.

Uno de los puntos más destacables en cuando al uso de listas enlazadas

dinámicamente es el hecho de crear estructuras conocidas como nodos. Un nodo
es una especie de eslabón (similar al de una cadena de bicicleta ), es decir, cada
nodo se enlaza con otro a través de un puntero que apunta a una estructura del
mismo tipo que el nodo. Por ejemplo, para crear una estructura de nodo para
almacenar enteros y a la vez para apuntar a otro posible nodo podemos emplear
la sintaxis:
struct nodo {
int data;
nodo *siguiente;
};

Observe que con la declaración anterior estamos creando el tipo

estructurado nodo, mismo que posee a los miembros: data para guardar valores
enteros, y siguiente para apuntar o enlazar a un supuesto siguiente nodo.

Ya que las listas dinámicas inicialmente se encuentran vacías, y más aún,

una lista dinámica no posee una dirección establecida en tiempo de compilación
ya que las dirección de memoria que ocupará cada uno de los elementos se
establecerá en tiempo de ejecución, entonces cómo determinar la condición de
vacío? En nuestro ejemplo usaremos un contador (ITEMS) que dicho sea de paso,
si ITEMS = 0, entonces la lista está vacía. (la condición de vacio también podría
determinarse al verificar el SP, es decir, si el SP = NULL, significa que la lista no
posee elementos ).

Al hacer un análisis previo de los eventos que acontecerán en la pila y su

puntero de lectura y escritura (SP, que en esta ocasión es una estructura tipo
nodo), se tiene lo siguiente:

1.) Al principio la lista está vacía, en ese caso el SP es igual a NULL y, en

consecuencia, el puntero next también es NULL.

SP = NULL

???? next -----> NULL

2.) Después de agregar el primer elemento la situación se vería así:

SP = Asignado
1
data next -----> NULL

3.) Después de agregar otro elemento la situación se vería así:

SP = Asignado
2
data next -----> NULL data next -----> NULL

Ejemplo: Pila basada en un arreglo dinámico

#include <iostream>
//#include <conio.h>
using namespace std;
/* tipo de dato que contendrá la lista */
typedef char DATA_TYPE;

// declaraci¢n de estructura nodo

struct nodo {
DATA_TYPE data;
nodo *next;
};
class StackDin {
// atributos
int ITEMS; /* número de elementos en la lista */
int ITEMSIZE; /* tamaño de cada elemento */
nodo *SP; /* puntero de lectura/escritura */
public:
// constructor
StackDin() : SP(NULL), ITEMS(0), ITEMSIZE(sizeof(DATA_TYPE)) {}
// destructor
~StackDin() {}
/* agregar componente a la lista */
DATA_TYPE put(DATA_TYPE valor)
 {
nodo *temp;
temp = new nodo;
if (temp == NULL) return -1;
temp->data = valor;
temp->next = SP;
SP = temp;
ITEMS ++;
return valor;
}
int empty() { return ITEMS == 0; }
/* retirar elemento de la lista */
DATA_TYPE get()
{
nodo *temp;
DATA_TYPE d;
if ( empty() ) return -1;
d = SP->data;
temp = SP->next;
if (SP) delete SP;
SP = temp;
ITEMS --;
return d;
}
}; // fin de la clase StackDin
/* punto de prueba para la clase StackDin */
int main()
{
//clrscr();
StackDin s;
DATA_TYPE d;
for (d='A'; d<='Z'; d++) s.put(d);
while ( ! s.empty() )
cout << (DATA_TYPE)s.get() << " ";
cout << "\nPara terminar presione <Enter>...";
cin.get();
return 0;
}
2.-) ¿Que son Colas o Queues?

Una cola sencilla es una estructura en donde cada elemento es insertado

Inmediatamente después del último elemento insertado; y donde los elementos se
retiran siempre por el frente de la misma, debido a esto el comportamiento de un
una cola se conoce como FIFO (primero en entrar, primero en salir).

Un ejemplo a citar de cola es el comportamiento del buffer del teclado.

Cuando en el teclado se oprime una tecla, el código del carácter ingresado

es trasladado y depositado en una área de memoria intermedia conocida como "el
buffer del teclado", para esto el microprocesador llama a una rutina específica.
Luego, para leer el carácter depositado en el buffer existe otra función, es decir,
hay una rutina para escribir y otra para leer los caracteres del buffer cada una de
las cuales posee un puntero; uno para saber en donde dentro del buffer se
escribirá el siguiente código y otro para saber de dónde dentro del buffer se leerá
el siguiente código.

Cola en un arreglo estático

En el programa que se ve en seguida, se simula el comportamiento de una

estructura de cola simple. Aunque en el mismo se usa un arreglo estático de
tamaño fijo se debe mencionar que normalmente las implementaciones hechas
por fabricantes y/o terceras personas se basan en listas dinámicas o
dinámicamente enlazadas.

Para la implementación de la clase Queue se han elegido los métodos:

 Put ( ), poner un elemento en la cola

 Get ( ), retirar un elemento de la cola
 Empty ( ), regresa 1 (TRUE) si la cola esta vacía
 Size ( ), número de elementos en la cola
 El atributo cabeza de la clase Queue es el puntero de lectura.
 El atributo cola de la clase Queue es el puntero de escritura.

Es decir, la cola indica la posición dentro de la lista en donde la función put ( )

insertará el siguiente dato, y la cabeza indica la posición dentro de la lista de
donde la función get ( ) leerá el siguiente dato.

 Cada vez que put ( ) inserta un elemento la cola se incrementa.

 Cada vez que get ( ) retira un elemento la cabeza se incrementa.

En el siguiente ejemplo se analiza lo que sucede con la cola y la cabeza

(punteros de escritura y de lectura de la Lista) cuando se guardan en la cola uno
por uno los caracteres 'A', 'B', 'C' y 'D'. Observe que al principio: cola = cabeza =
cero.

Llenando la cola:

Cola

Al principio

Cabeza

Cola

A Put ( ‘A’):
Después de haber agregado el primer elemento

Cabeza
 Cola

A B C D Después de haber agregado cuatro elementos

Cabeza

 Vaciando la cola

Cabeza

A B C D Antes de haber retirado los elementos

Cabeza

A B C D Get ( );
Después de haber retirado un elemento

Cabeza

A B C D Al final después de haber retirado todos los

elementos
Cola

Obsérvese que al final el cabeza apunta hacia el mismo elemento que la

cola, es decir, la cola vuelve a estar vacía. Puesto que la cola que estamos
proyectando reside en un arreglo estático los componentes del arreglo aún están
dentro de la misma, salvo que para su recuperación se debería escribir otro
método. En una cola dinámica (como se demostrará más adelante) los elementos
retirados de la misma se eliminan de la memoria y podría no ser posible su
recuperación posterior.
Ejemplo: cola en un arreglo estático

#include <iostream.h>
#define MAX_SIZE 256 /* capacidad máxima */
typedef char almacen[MAX_SIZE];
class Queue {
int cabeza; /* puntero de lectura */
int cola; /* puntero de escritura */
int ITEMS; /* número de elementos en la lista */
int ITEMSIZE; /* tamaño de cada elemento */
almacen alma; /* el almacen */
public:
// constructor
Queue() {
cabeza = 0;
cola = 0;
ITEMS = 0;
ITEMSIZE = 1;
}
// destructor
~Queue() {}
// regresa 1 (true) si la lista está vacia
int empty() { return ITEMS == 0; }
// insertar elemento a la lista
int put(int d)
{
if ( ITEMS == MAX_SIZE) return -1;
if ( cola >= MAX_SIZE) { cola = 0; }
alma[cola] = d;
cola ++;
ITEMS ++;
return d;
}
// retirar elemento de la lista
int get()
{
char d;
if ( empty() ) return -1;
if ( cabeza >= MAX_SIZE ) { cabeza = 0; }
d = alma[cabeza];
cabeza ++;
 ITEMS --;
return d;
}
// regresa el n£mero de elementos en lista
int size() { return ITEMS; }
}; // fin de la clase Queue
// probando la cola
int main()
{
int d;
Queue q;
for (d='A'; d<='Z'; d++) q.put(d);
cout << "Items = " << q.size() << endl;
while ( q.size() ) {
cout << (char)q.get() << " ";
}
cout << "\nPara terminar oprima <Enter> ...";
cin .get();
return 0;
}

Ejemplo: cola en un arreglo dinámico

#include <iostream>
using namespace std;
typedef char DATA_TYPE;
struct nodo {
DATA_TYPE data;
nodo *next;
};
class QueueDin {
// atributos
int ITEMS, ITEMSIZE;
nodo *cola, *cabeza;
public:
// constructor
QueueDin() : cola(NULL), cabeza(NULL), ITEMS(0), ITEMSIZE(sizeof(DATA_TYPE)) {}
 // destructor
~QueueDin() {}
/* agregar componente a la lista */
DATA_TYPE put(DATA_TYPE valor)
{
nodo *temp;
temp = new nodo;
if (temp == NULL) return -1;
ITEMS ++;
temp->data = valor;
temp->next = NULL;
if (cabeza == NULL)
{
cabeza = temp;
cola = temp;
} else
{
cola->next = temp;
cola = temp;
}
return valor;
}
// regresa 1 (true) si la lista está vacia
int empty() { return ITEMS == 0; }
/* retirar elemento de la lista */
DATA_TYPE get()
{
nodo *temp;
DATA_TYPE d;
if ( empty() ) return -1;
d = cabeza->data;
temp = cabeza->next;
if (cabeza) delete cabeza;
cabeza = temp;
ITEMS --;
return d;
}
}; // fin de la clase QueueDin
/* punto de prueba */
int main()
{
QueueDin s;
DATA_TYPE d;
// llenando la cola
for (d='A'; d<='Z'; d++) {
s.put(d);
cout << d << " ";
}
cout << endl;
// vaciando la cola
while ( ! s.empty() )
cout << (DATA_TYPE)s.get() << " ";
cout << "\nPara terminar presione <Enter>...";
cin.get();
return 0;
}
 CONCLUSION

El tener claros los conceptos y la información a trabajar, además de

generar un análisis exhaustivo de las necesidades que debe cumplir el programa y
por qué medio se van a cumplir, son características fundamentales previo a la
creación de código, si no se tiene claro que se va a diseñar, no se puede tener
claro cómo se va a realizar. El tener un lenguaje correcto para aplicar a los
programas es parte integral de estos, las desventajas de desconocer un lenguaje
o no conocer lo que lo distingue de otros lenguajes es un des favorecimiento para
el programador. Por eso se usa C# lenguaje de programación, debido a que
permite tener una compilación mucho más rápida y un uso para el usuario nada
tedioso. Aunque no se genera un entorno gráfico muy cómodo para el usuario,
este solo se encarga de ingresar la información para obtener el informe que
necesita por lo cual en realidad no es un punto en contra el del lenguaje. El uso de
las mutualistas favorecen las labores de programación, con estas se agiliza
profundamente el tener que hacer validaciones para el ingreso de datos y demás
líneas de código que solo generan acumulación, además de hacer que el
programa sea compilado mucho más lento.