UNIDAD III ESTRUCTURAS DE DATOS (LINEALES Y NO LINEALES)

Actividad 1

DEFINICIÓN DE UNA ESTRUCTURA DE DATOS PILA

Definición 1

Colección de datos. Es una estructura de datos que permite almacenar datos del mismo tipo, en la cual en un extremo se puede insertar y eliminar elementos, llamado la parte superior de la pila o cima. A este tipo de estructura de datos se le conoce como LIFO (primero en entrar, último en salir).

70705" RKNCU

Definición 2

Una pila (stack) es una estructura lineal a cuyos datos sólo se puede acceder por un solo extremo, denominado  tope o  cima (top). En esta estructura sólo se pueden efectuar dos operaciones: añadir y eliminar un elemento, acciones que se conocen por meter (push), y sacar (pop). Si se meten varios elementos en la pila y después se sacan de ésta, el último elemento en entrar será el primero en salir. Por esta razón se dice que la pila es una estructura en la que el último en entrar es el primero en salir, en inglés, LIFO (last in first out).

Definición 3

Una pila es un tipo especial  de lista en la que todas las  inserciones y borrados tienen lugar en un extremo denominado  tope. A las pilas se les llama también “listas LIFO” (last in first out) o  listas “último en entrar, primero en salir”.

LA ESTRUCTURA DE UNA PILA

 

CÓMO FUNCIONA UNA PILA

Una pila es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. Sólo es

posible un modo de acceso a esta estructura: a través de la cabeza de la pila. De este modo podemos

añadir un elemento a

la cabeza de la pila o

extraer un elemento de la cabeza de la pila. Debido a que las operaciones de extracción e inserción

se realizan por el mismo extremo, el último elemento en ser añadido será el primero en ser extraído; por ello a estas

estructuras se las conoce con el nombre de
LIFO (last-in, first-out; último en entrar, primero en salir).

APLICACIONES DE LAS PILAS

IMPLEMENTACION ALGORITMICA DE UNA PLIA

#include <stdlib.h>
#include <stdio.h>

typedef struct _nodo \{
   int valor;
   struct _nodo *siguiente;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;

/* Funciones con pilas: */
void Push(Pila *l, int v);
int Pop(Pila *l);

int main() \{
   Pila pila = NULL;

   Push(&pila, 20);
   Push(&pila, 10);
   printf("%d, ", Pop(&pila));
   Push(&pila, 40);
   Push(&pila, 30);
   printf("%d, ", Pop(&pila));
   printf("%d, ", Pop(&pila));
   Push(&pila, 90);
   printf("%d, ", Pop(&pila));
   printf("%d\n", Pop(&pila));
   getchar();
   return 0;
}
void Push(Pila *pila, int v) \{
   pNodo nuevo;

   /* Crear un nodo nuevo */
   nuevo = (pNodo)malloc(sizeof(tipoNodo));
   nuevo->valor = v;
  
   /* Añadimos la pila a continuación del nuevo nodo */
   nuevo->siguiente = *pila;
   /* Ahora, el comienzo de nuestra pila es en nuevo nodo */
   *pila = nuevo;
}
int Pop(Pila *pila) \{
   pNodo nodo; /* variable auxiliar para manipular nodo */
   int v;      /* variable auxiliar para retorno */
  
   /* Nodo apunta al primer elemento de la pila */
   nodo = *pila;
   if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */
   /* Asignamos a pila toda la pila menos el primer elemento */
   *pila = nodo->siguiente;
   /* Guardamos el valor de retorno */
   v = nodo->valor;
   /* Borrar el nodo */
   free(nodo);
   return v;
}



IMPLEMENTACIÓN DE UNA PILA EN LENGUAJE C++

/* -------------------------------------------------- */
/* Implementación de una pila mediante lista enlazada */
/* ------ http://www.lawebdelprogramador.com -------- */
/* -------------------------------------------------- */
#include <stdio.h>
#include <stdlib.h>
/* declaracion de la pila*/
struct tipo_pila
{
 int clave;
 struct tipo_pila *sig;
};
/* Cabeceras de prototipos de funciones */
void crear_pila(struct tipo_pila **pila);
int es_vacia(struct tipo_pila *pila);
void apilar_pila(struct tipo_pila *pila, int elem);
void desapilar_pila(struct tipo_pila *pila, int *elem);
void crear_pila(struct tipo_pila **pila)
{
 *pila=(struct tipo_pila *) malloc(sizeof(struct tipo_pila));
 (*pila)->sig=NULL;
}
void apilar_pila(struct tipo_pila *pila, int elem)
{
 struct tipo_pila *nuevo;
 nuevo=(struct tipo_pila *) malloc(sizeof(struct tipo_pila));
 nuevo->clave=elem;
 nuevo->sig=pila->sig;
 pila->sig=nuevo;
}
void desapilar_pila(struct tipo_pila *pila, int *elem)
{
 struct tipo_pila *aux;
 aux=pila->sig;
 *elem=aux->clave;
 pila->sig=aux->sig;
 free(aux);
}
int es_vacia(struct tipo_pila *pila)
{
 return (pila->sig==NULL);
}
/* programa principal */
main(void)
{
 struct tipo_pila *pila;
 int elem;
 crear_pila(&pila);
 if (es_vacia(pila)) printf("\nPila vacia!");
 apilar_pila(pila, 1);
 desapilar_pila(pila, &elem);
}