Pilas#

Objetivos

Objetivo 1…
Objetivo 2…

1. Introduccion#

En los programas tipicos, la cantidad de memoria que usan es desconocida. xx

2. Pila (Stack)#

Una pila (stack) es una ADT que permite almacenar y recuperar datos. Esta presenta un modo de acceso a sus elementos de tipo LIFO (del inglés Last In, First Out, último en entrar, primero en salir) debido a que los datos almacenados en ella se retiran en orden inverso al que fueron entrados.

../_images/CH_02-S06-stack_fig1.png — Fig. 81 Representación y operaciones de una pila (stack)#

Cuando se trabajan con pilas se manejan las siguientes operaciones básicas:

Verificar lista vacia: Inicia una pila vacia.
Inicializar: Inicia una pila vacia.
Apilar (push): Consiste en insertar un registro al principio de una lista ligada.
Desapilar (pop): Consiste en eliminar el primer nodo de la lista y retornar el dato que se hallaba en ese nodo.

Simulación

En el siguiente link se muestra una simulación de una pila.

2.1. Definición de la pila#

La siguiente estructura se define una pila (stack) de tamaño fijo (CAPACITY) cuyos miembros son:

count: Catidad de elementos agregados a la pila.
data: Arreglo donde se almacenan los elementos de la pila.

#define CAPACITY 10

typedef struct _stack {
  int count;
  int data[CAPACITY];
} stack;

La siguiente figura muestra la estructura asociada a la pila (stack) previamente definida:

../_images/CH_02-S06-stack_fig1a_.png — Fig. 82 Estructura asociada a la pila (`stack`)#

Es importante tener en cuenta, que en este caso, como la pila implementada tiene un tamaño fijo, la forma como se maneja la memoria no es la mas eficiente. Al respecto, si el tamaño (CAPACITY) de la pila es mucho mas grande que la cantidad de elementos almacenados, se puede estar desperdiciando una gran cantidad de memoria debido a la gran cantidad de espacio sin usar; por contrario, si el tamaño de la pila es muy pequeño, este puede hacer se la pila se quede corta cuando la cantidad de datos a manejar es mayor.

2.2. Funcionas de la pila#

Las operaciones asociadas la ADT stack definida previamente se destriben a continuación:

stack_init: crea una pila vacía:

void stack_init(stack *s) { 
  s->count = 0;
}

stack_push: Agrega dato item a en la pila.

void stack_push(stack *s, int item) {
  assert(s != NULL);
  assert(s->count < CAPACITY);
  s->data[s->count] = item;
  s->count++;
}

stack_pop: Elimina el último elemento agregado a la pila y dejandola con un elemento menos (elementos previamente agregados).

int stack_pop(stack *s) {
  assert(s != NULL);
  assert(s->count > 0);
  s->count--;
  return s->data[s->count];
}

stack_empty: Retorna si la pila esta vacia 1 o 0 en caso contrario.

int stack_empty(stack *s) {
  assert(s != NULL);
  return (s->count == 0);
}

stack_peek: Retorna el dato que está de último en la pila (el último agregado), sin eliminarlo.

int stack_peek(stack *s) {
  int top;
  top = s->data[s->count];
  return top;
}

stack_full: Retorna si la pila esta llena 1 o 0 en caso contrario.

int stack_full(stack *s) {
  assert(s != NULL);
  return (s->count == CAPACITY);
}

3. Uso de la estructura `stack`#

Recordemos que el programa cliente es aquel que hace el llamado de las funciones definidas en bibliotecas, modulos o clases para realizar determinadas tareas.

En un programa, la función encargada de iniciar la ejecución de este es la función main. En esta función, se implementa la logica de la aplicación mediante el llamado a las funciones que han sido previamente definidas tal y como se muestra en la siguiente figura:

../_images/CH_02-S06-stack_fig1b.png — Fig. 84 Función `main`#

El siguiente código, muestra el caso como seria un programa de un solo archivo en el cual se hace uso de la estructura stack. Notese que al implementarse la logica de la aplicación función main, las instrucciones se definen de acuerdo a los requerimientos de la aplicación.

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

#define CAPACITY 10

/*
Definicion de la pila
*/
typedef struct _stack {
  int count;
  int data[CAPACITY];
} stack;


/*
Declaración de las funciones asociadas a la pila
*/
void stack_init(stack *s);
int stack_empty(stack *s);
void stack_push(stack *s, int item);
int stack_pop(stack *s);
int stack_full(stack *s);
int stack_peek(stack *s);

/*
Funcion principal
*/
int main(int argc, char *argv[]) {
  // Codigo de la aplicacion
  ...
  
  return 0;
}

/*
Definicion de las funciones asociadas a la pila
*/
void stack_init(stack *s) { 
  s->count = 0;
}

int stack_empty(stack *s) {
  assert(s != NULL);
  return (s->count == 0);
}

void stack_push(stack *s, int item) {
  assert(s != NULL);
  assert(s->count < CAPACITY);
  s->data[s->count] = item;
  s->count++;
}

int stack_pop(stack *s) {
  assert(s != NULL);
  assert(s->count > 0);
  s->count--;
  return s->data[s->count];
}

int stack_full(stack *s) {
  assert(s != NULL);
  return (s->count == CAPACITY);
}

int stack_peek(stack *s) {
  assert(s != NULL);
  int top = s->data[s->count - 1];
  return top;
}

3.1. Ejemplos#

Asumiendo una pila de 3 elementos (CAPACITY = 3).

Codigo 1: Mediante código implemente la siguiente pila:

../_images/CH_02-S06-stack_fig2.png — Fig. 85 Pila asociada al ejemplo.#

El siguiente fragmento de código hace uso de las funciones definidas anteriormente para:

Inicializar una pila (S).
Agregar tres elementos a la pila: 1, 2 y 3 respectivamente.
Mostrar si la pila esta vacia, llena o parcialmente llena (indicando el numero de elementos que puede se pueden colocar).
Mostrar cada vez que se agrega un elemento el valor del tope (top) de la pila.

La implementación de este código se muestra a continuación (simulación):

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

#define CAPACITY 3

typedef struct _stack {
  int count;
  int data[CAPACITY];
} stack;

// Declaración de funciones
// Codigo declaración...


// Codigo main
int main() {
  stack S;
  stack_init(&S);
  if(stack_empty(&S) == 1) {
    printf("La pila esta vacia\n");
  }
  else if (stack_full(&S) == 1) {
    printf("La pila esta llena\n");
  }
  else {
    printf("En la pila aun caben %d elementos\n",CAPACITY - S.count);
  }
  stack_push(&S, 1);
  printf("Elemento agregado: %d\n", stack_peek(&S));
  stack_push(&S, 2);
  printf("Elemento agregado: %d\n", stack_peek(&S));
  if(stack_empty(&S) == 1) {
    printf("La pila esta vacia\n");
  }
  else if (stack_full(&S) == 1) {
    printf("La pila esta llena\n");
  }
  else {
    printf("En la pila aun caben %d elementos\n",CAPACITY - S.count);
  }
  stack_push(&S, 3);
  printf("Elemento agregado: %d\n", stack_peek(&S));
  if(stack_empty(&S) == 1) {
    printf("La pila esta vacia\n");
  }
  else if (stack_full(&S) == 1) {
    printf("La pila esta llena\n");
  }
  else {
    printf("En la pila aun caben %d elementos\n",CAPACITY - S.count);
  }
  return 0;
}

// Definición de funciones
// Codigo definición...

El resultado del código anterior, se muestra a continuación:

../_images/CH_02-S06-stack_fig2a.png — Fig. 86 Resultado código anterior#

Codigo 2: Partiendo de la lista de 3 elementos anteriormente mostrada, saque el ultimo elemento agregado tal y como se muestra en la siguiente figura:

../_images/CH_02-S06-stack_fig3.png — Fig. 87 Pila asociada al ejemplo anterior#

La implementación realizada en el siguiente fragmento de código (simulacion) hace lo siguiente:

Inicializa la pila al estado inicial (1, 2 y 3).
Saca el ultimo elemento ingresado a la pila (3) imprimiendo su valor.
Muestra la cantidad de elementos que quedan en la pila.

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

#define CAPACITY 3

typedef struct _stack {
  int count;
  int data[CAPACITY];
} stack;

// Declaración de funciones
// Codigo declaración...


// Codigo main
int main() {
  stack S;
  stack_init(&S);    // S = [ ] : Lista vacia
  stack_push(&S, 1); // S = [|top|-> 1]
  stack_push(&S, 2); // S = [|top|-> 2 , 1]
  stack_push(&S, 3); // S = [|top|-> 3, 2 , 1]
  int e = stack_pop(&S); // S = [|top|-> 2 , 1] ; e = 3
  printf("Elemento sacado de la pila: %d\n", e);
  printf("Elementos disponibles en la pila: %d \n",  S.count);
  return 0;
}

// Definición de funciones
// Codigo definición...

La salida del fragmento de código anterior, se muestra a continuación:

../_images/CH_02-S06-stack_fig3a.png — Fig. 88 Resultado código anterior#

4. Enlaces#

https://ranger.uta.edu/~alex/courses/3318/
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
http://cslibrary.stanford.edu/
https://web.stanford.edu/dept/cs_edu/resources/textbook/
https://web.stanford.edu/class/cs106x/handouts.html
https://web.stanford.edu/class/cs107/
https://web.stanford.edu/class/archive/cs/cs107/cs107.1248/calendar
https://web.stanford.edu/class/cs106x/res/reader/CS106BX-Reader.pdf
http://cslibrary.stanford.edu/
https://www.cs.swarthmore.edu/~newhall/cs45/s14/#schedule
https://www.cs.swarthmore.edu/~newhall/unixlinks.html#lang
https://publications.gbdirect.co.uk/c_book/
https://www.cs.swarthmore.edu/~newhall/unixlinks.html#Clang
https://www.cs.swarthmore.edu/~newhall/unixhelp/os_stats.php
https://www.cs.swarthmore.edu/~newhall/cs35/
https://www.cs.swarthmore.edu/~newhall/unixhelp/C_linkedlists.pdf
https://www.cs.princeton.edu/courses/archive/spring20/cos217/
https://www.cs.princeton.edu/courses/archive/spring20/cos217/precepts/09voidptrs/symtablelist.pdf
https://www.cs.princeton.edu/courses/archive/spring20/cos217/lectures/01_Intro.pdf
https://august.princeton.edu/
https://www.cs.princeton.edu/courses/archive/fall07/cos217/lectures/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/pages/lectures-and-assignments/data-structures-debugging/
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/pages/lectures-and-assignments/data-structures-debugging/
https://ocw.mit.edu/courses/6-033-computer-system-engineering-spring-2018/
https://ocw.mit.edu/courses/6-828-operating-system-engineering-fall-2012/
https://ocw.mit.edu/courses/6-087-practical-programming-in-c-january-iap-2010/
https://ocw.mit.edu/courses/6-087-practical-programming-in-c-january-iap-2010/pages/lecture-notes/
https://ocw.mit.edu/courses/1-00-introduction-to-computers-and-engineering-problem-solving-spring-2012/
https://ocw.mit.edu/courses/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/
https://ocw.mit.edu/courses/6-100l-introduction-to-cs-and-programming-using-python-fall-2022/
https://ocw.mit.edu/collections/introductory-programming/
https://cs61c.org/su24/
https://www.cs.princeton.edu/courses/archive/spr24/cos126/schedule/
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/schedule.html
https://bytesoftheday.wordpress.com/2014/07/04/q14/
https://www.cs.princeton.edu/courses/archive/spring20/cos217/
https://embeddedwala.com/Blogs/embedded-c/memory-layout-of-c-program
https://www.cs.mtsu.edu/~cs2170/C++labs/lab18/OSmemlayout.pdf
https://d1b10bmlvqabco.cloudfront.net/attach/j6fe5friemd22w/hzd1madqsie3ts/j7kw6i4tmqf8/61C_Note_1_Memory.pdf
https://ocw.mit.edu/courses/6-s096-introduction-to-c-and-c-january-iap-2013/bba9056d5290198d563edc47dfcff0e9_MIT6_S096_IAP13_lec3.pdf
https://cs61c.org/su24/
http://wla.berkeley.edu/~cs61c/fa17/
https://www.cs.princeton.edu/courses/archive/fall07/cos217/index.html
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/lectures/21-cmem/writeup/pdf/main.pdf
https://cs.gmu.edu/~zduric/cs262/Slides/teoX.pdf
https://d1b10bmlvqabco.cloudfront.net/attach/j6fe5friemd22w/hzd1madqsie3ts/j7kw6i4tmqf8/61C_Note_1_Memory.pdf
https://www.cs.princeton.edu/courses/archive/fall07/cos217/
https://www.cs.mtsu.edu/~cs2170/C++labs/lab18/OSmemlayout.pdf
https://web2.qatar.cmu.edu/~mhhammou/15122-s23/lectures/21-cmem/writeup/pdf/main.pdf
https://www.cs.princeton.edu/courses/archive/spr24/cos126/schedule/
https://github.com/vishwa27yvs/Intro-to-Computer-Science-COS-126
https://www.berthon.eu/wiki/foss:wikishelf:linux:memory
http://resources.infosecinstitute.com/system-address-map-initialization-in-x86x64-architecture-part-1-pci-based-systems/#gref
https://fypandroid.wordpress.com/2011/01/17/anatomy-of-a-program-in-memory/
https://www.securitysift.com/windows-exploit-development-part-1-basics/
https://www.ibm.com/developerworks/library/j-nativememory-linux/
https://gabrieletolomei.wordpress.com/miscellanea/operating-systems/in-memory-layout/
http://www.cs.utexas.edu/users/fussell/cs310h/lectures/Lecture_17-310h.pdf
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-087-practical-programming-in-c-january-iap-2010/lecture-notes/
https://stackoverflow.com/questions/2128728/allocate-matrix-in-c
https://www.geeksforgeeks.org/dynamically-allocate-2d-array-c/
https://www.programiz.com/c-programming/c-dynamic-memory-allocation
https://www.cs.swarthmore.edu/~newhall/unixhelp/C_arrays.html

Introducción al lenguaje C

Pilas

Contents

Pilas#

1. Introduccion#

2. Pila (Stack)#

2.1. Definición de la pila#

2.2. Funcionas de la pila#

3. Uso de la estructura `stack`#

3.1. Ejemplos#

4. Enlaces#

Introducción al lenguaje C

Pilas

Contents

Pilas#

1. Introduccion#

2. Pila (Stack)#

2.1. Definición de la pila#

2.2. Funcionas de la pila#

3. Uso de la estructura stack#

3.1. Ejemplos#

4. Enlaces#

3. Uso de la estructura `stack`#