Estructuras de Datos: Stacks

Stacks

El stack es una estructura de datos LIFO (last in, first out), queriendo decir que el ultimo elemento que fue agregado, sera el primero en ser accedido.

Para implementar un stack como estructura de datos abstracta vamos a necesitar una estructura con:

1. Espacio para almacenar los elementos.
2. Pointer al top (ultimo elemento agregado) del stack.

Las operaciones que se implementaran son:

• push: insertar un nuevo elemento.
• pop: eliminar un elemento del stack.
• peek: ver un elemento en un indice especificado.
• stack_top: ver cual es el elemento top del stack.
• is_empty: dice si el stack esta vacio.
• is_full: dice si el stack esta lleno.

Podemos utilizar tanto arrays como linked lists para implementar un stack.

Implementacion Usando un Array

Para implementar un stack usando arrays vamos a usar la siguiente estructura:

struct stack
{
  int size;
  int top; // indice top
  int *s;
};

Podemos crear un stack con una funcion similar a la siguiente:

struct stack
stack_create (int size)
{
  struct stack s = { 0 };
  s.size = s;
  s.s = calloc (1, sizeof (int));
  s.top = -1;
  return s;
}

Y dos de las operaciones mencionadas is_empty y is_full pueden ser implementadas de la siguiente manera:

_Bool
stack_is_empty (struct stack *s)
{
  if (!s || s->top != -1)
      return 0;
  return 1;
}

_Bool
stack_is_full (struct stack *s)
{
  if (!s || s->top !=  (s->size - 1))
    return 0;
  return 1;
}

Podemos implementar push vamos a insertar un elemento en s.top + 1 y debemos revisar que no este lleno tampoco al momento de insertar:

void
stack_push (int x, struct stack *s)
{
  if (!s || s->top ==  (s->size - 1))
    return;

  s->top++;
  s->s[s->top] = x;
}

Para pop, vamos a obtener el ultimo valor del stack, vamos a modificar el valor de top a top - 1 y vamos a devolver el valor eliminado. Esto se debe ejecutar, siempre y cuando top != -1.

int
stack_pop (struct stack *s)
{
  if (!s || s->top == -1)
    return -1;

  return s->s[s->top--];
}

La complejidad de tiempo para estas dos operaciones es \(O(1)\).

Para peek y obtener un valor de una posicion especificada, podemos convertir la posicion del stack a un indice del array haciendo: top - pos + 1:

int
stack_peek (int pos, struct stack *s)
{
  if (!s)
    return -1;

  int i = s->top - pos + 1;
  if (i < 0)
    return -1;
  return s->s[i];
}

Y por ultimo stack_top:

int
stack_top (struct stack *s)
{
  if (!s || s->top == -1)
    return -1;
  return s->s[s->top];
}

La complejidad de tiempo de todas las operaciones del stack tiene una complejidad de tiempo \(O(1)\).

Stacks Usando Linked Lists

En una implementacion de stack en una linked list, para evitar que la complejidad de tiempo de operaciones simples como la de push o pop tengan una complejidad de tiempo \(O(n)\) sino que sea \(O(1)\) se van a realizar estas operaciones en la parte izquierda de la lista, es decir, siempre sera con el primer elemento.

Para push y pop ya lo vimos antes, es hacer la operacion antes del primer nodo.

Cuando top == NULL, es decir, la lista no tenga nodos, decimos que el stack esta vacio.

Y como aqui podemos crear tantos nodos como nos permitan los recursos, la condicion para saber si un stack esta lleno, es si no podemos crear nuevos nodos, es decir, ya no haya memoria en el heap:

struct nodo
{
  int dato;
  struct nodo *next;
};

void
stack_push (int x, struct nodo **s)
{
  struct nodo *t = calloc (1, sizeof (*t));
  if (!t)
    return; // el stack esta lleno

  t->dato = x;
  t->next = *s;
  *s = t;
}

int
stack_pop (struct nodo **s)
{
  if (!s)
    return -1; // el stack esta vacio

  struct nodo *p = *s;
  *s = p->next;
  int x = p->dato;
  free (p);

  return x;
}

int
stack_peek (int pos, struct nodo *s)
{
  if (!s)
    return -1;

  struct node *p = s;
  for (int i = 0; i < pos - 1 && p; i++)
    p = p->next;

  if (!p)
    return -1;
  return p->dato;
}

int
stack_top (struct nodo *s)
{
  if (!s)
    return -1;
  return s->dato;
}

_Bool
stack_is_empty (struct nodo *s)
{
  return s ? 0 : 1;
}

_Bool
stack_is_full ()
{
  struct nodo *n = calloc (1, sizeof (*n));

  if (!n)
    return 1;

  free (n);
  return 0;
}

Parenthesis Matching

Una de las aplicaciones del stack es la de emparejar parentesis. Por ejemplo, tenemos una expresion: ((a + b) * (c - d)) y tenemos que revisar si los parentesis estan balanceados o no.

Como va a funcionar, es que vamos a comparar cada uno de los caracteres de la expresion si es un ( dado el caso que si lo sea, se va a pushear ese caracter al stack. Cuando el caracter actual sea un ) vamos a eliminar un elemento del stack.

Al llegar al final de la expresion vamos a revisar que el stack este vacio y que no intentemos eliminar un elemento cuando no hayan, si estas condiciones se cumplen, quiere decir que los parentesis estan balanceados.

_Bool
esta_balanceado (const char *exp)
{
  if (!exp)
    return 0;

  struct stack s = stack_create (strlen (exp));


  for (int i = 0; exp[i] != '\0'; i++)
    {
      if (exp[i] == '(')
        stack_push ((int)exp[i], &s);
      else if (exp[i] == ')')
        {
          if (stack_is_empty (&s))
            {
              stack_destroy (&s);
              return 0;
            }

          stack_pop (&s);
        }
    }

  _Bool empty = stack_is_empty (&s);

  stack_destroy (&s);
  return empty;
}

Convertir de Infijos a Sufijos ATTACH

Nosotros podemos representar de 3 formas diferentes una expresion matematica:

1. Infijo: Operando - Operador - Operando (a + b)
2. Prefijo: Operador - Operando - Operando (+ a b)
3. Sufijo: Operando - Operando - Operador (a b +)

Para estas conversiones, lo primero que haremos sera agregarles parentesis a la expresion basados en la siguiente (muy basica) tabla de precedencia:

Por ejemplo, si tenemos la expresion: a + b * c, en base a esa precedencia quedaria de la siguiente forma (a + (b * c)).

Si convertimos la expresion con parentesis en prefijos quedaria + a * b c, y en sufijos a b c * +.

Como va a funcionar la conversion usando stacks es que vamos a tener dos variables: un stack y un string que seria la expresion final. Escanearemos caracter por caracter la expresion con los infijos y cada operando lo vamos a agregar a la expresion que estamos generando, y por cada operador vamos a pushearlo al stack, si el elemento top del stack tiene menos o igual precedencia lo agregaremos a la expresion que estamos generando.

Al finalizar la expresion, vamos a agregar cualquier otro operador que tengamos en el stack a la expresion generada.

Por ejemplo, con la expresion: a + b * c - d / e:

Terminando con la expresion abc*+de/-

Podemos hacerlo de la misma manera si tomamos los operandos como los elementos de mayor precedencia.

La implementacion en C seria la siguiente:

_Bool
es_operando (char c)
{
  if (c == '+' || c == '-' || c == '*' || c == '/')
    return 0;
  return 1;
}

int
precedencia (char c)
{
  if (c == '+' || c == '-')
    return 1;
  else if (c == '*' || c == '/')
    return 2;
  return 0;
}

char *
convertir (char *infijo)
{
  if (!infijo)
    return NULL;

  size_t size = strlen (infijo);

  struct stack s = stack_create (size);
  char *sufijo = calloc (size, sizeof (char));

  int i = 0;
  int j = 0;
  while (infijo[i] != '\0')
    {
      if (es_operando (infijo[i]))
        {
          sufijo[j++] = infijo[i++]; // los operandos se agregan directamente.
          continue;
        }

      if (precedencia (infijo[i]) > precedencia (stack_top (&s)))
        stack_push (&s, infijo[i++]);
      else
        sufijo[j++] = stack_pop (&s);
    }

  while (!stack_is_empty (&s))
    sufijo[j++] = stack_pop (&s);
  sufijo[j] = '\0';

  stack_destroy (&s);
  return sufijo;
}

Ya teniendo la expresion en su forma de sufijo, podemos evaluarla pusheando todos los operandos al stack, y por cada operador que se encuentre se realiza la operacion con los operandos disponibles en el stack.

Por ejemplo, si tenemos 15 8 + 4 -, primero se pushearia 15, despues 8, como el proximo caracter es un operador se hace la operacion de suma entre 15 y 8, quedando 23 como unico elemento en el stack, se pushea 4, y como el proximo es un operador se efectua la resta quedando con 19.