Strutture dati: Stack e Code

Stack e code sono strutture dinamiche basate sui classici metodi di transito per gli elementi su una coda (FIFO, First In Fist Out) o in una pila/stack (LIFO, Last In Fist Out).


Stack

Per l'implementazione è sufficiente un array e una variabile che mantenga l'elemento in cui inserire il successivo elemento. Un'ulteriore variabile è utilizzata per il numero di elementi dell'array usato come stack, che rappresenta quindi il numero massimo di elementi che si possono inserire su tale stack.

Coda

Una coda ha una fine (tail) dove inserire gli elementi nuovi e un inizio (head) da dove prelevare gli elementi. Ad ogni elemento inserito tail viene aumentato di una posizione. Lo stesso accade ad head quando viene prelevato un elemento. Una coda è sia vuota che piena se head == tail e per differenziare questi due stati della coda si utilizzeranno delle variabili sentinella.

Se tail o head raggiungono l'indice massimo dell'array che rappresenta la coda, ripartono dall'indice 0.

/*Per facilitare la stesura, la lettura e la comprensione del codice si è volutamente deciso di 
utilizzare un mix di C/C++ cercando di restare il più possibile all'interno del sottoinsieme 
C del C++ e di utilizzare solo quei costrutti e funzionalità di base del C++ che permettono 
una maggiore semplificazione.*/
 
#include <stdio.h>
 
void print_vector(int *, int);
bool stack_empty(struct stack&);
void stack_push(struct stack&, int);
int stack_pop(struct stack&);
void queue_enqueue(struct queue&, int);
int queue_dequeue(struct queue&);
 
struct stack
{
 int top;
 int n;
 int arr[15];
};
 
struct queue
{
 int head;
 int tail;
 int n;
 bool full;
 bool empty;
 int arr[6];
};
 
int main(int argc, char *argv[], char *envp[])
{
 stack s1 = { 0, 15 };
 
 stack_pop(s1);
 
 stack_push(s1, 1);
 stack_push(s1, 2);
 stack_push(s1, 3);
 stack_push(s1, 4);
 stack_push(s1, 5);
 
 print_vector(s1.arr, s1.top);
 
 printf("Elemento prelevato dallo stack: %d %s\n", 
  stack_pop(s1), !stack_empty(s1) ? "" : "Non Valido! Stack vuoto!");
 printf("Elemento prelevato dallo stack: %d %s\n", 
  stack_pop(s1), !stack_empty(s1) ? "" : "Non Valido! Stack vuoto!");
 
 print_vector(s1.arr, s1.top);
 
 queue q1 = { 0, 0, 6, false, true };
 
 queue_dequeue(q1);
 
 queue_enqueue(q1, 1);
 queue_enqueue(q1, 2);
 
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 
 queue_enqueue(q1, 3);
 queue_enqueue(q1, 4);
 queue_enqueue(q1, 5);
 queue_enqueue(q1, 6);
 queue_enqueue(q1, 7);
 
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 
 queue_enqueue(q1, 8);
 queue_enqueue(q1, 9);
 
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 printf("Elemento prelevato dalla coda: %d %s\n", 
  queue_dequeue(q1), !(q1.empty) ? "" : "Non Valido! Coda vuota!");
 
 return 0;
}
 
bool stack_empty(stack &s)
{
 if (s.top == 0)
  return true;
 else
  return false;
}
 
void stack_push(stack &s, int x)
{
 if (s.top < s.n)
 {
  //if (s.top < 0)
   // s.top++;
 
  s.arr[s.top++] = x;
 }
 else
  printf("Stack pieno!\n");
}
 
int stack_pop(stack &s)
{
 if (!stack_empty(s))
 {
  return s.arr[--s.top];
 }
 else
  printf("Stack vuoto!\n");
}
 
void queue_enqueue(queue &q, int x)
{
 if (q.head != q.tail || q.empty)
 {
  q.arr[q.tail] = x;
  if (q.tail == (q.n - 1))
   q.tail = 0;
  else
   q.tail++;
 
  q.empty = false;
  if (q.head == q.tail)
  {
   q.full = true;
  }
 }
 else
  printf("Coda piena!\n");
}
 
int queue_dequeue(queue& q)
{
 int tmp;
 if (q.head != q.tail || q.full)
 {
  tmp = q.arr[q.head];
  if (q.head == (q.n - 1))
   q.head = 0;
  else
   q.head++;
 
  q.full = false;
  if (q.head == q.tail)
  {
   q.empty = true;
  }
 
  return tmp;
 }
 else
  printf("Coda vuota!\n");
}
 
void print_vector(int *m, int n)
{
 for (int i = 0; i < n; ++i)
 {
  printf("%d ", m[i]);
 }
 printf("\n");
}

Riferimenti:
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] Algoritmi in C - Sedgewick