Pilhas e Filas

Em Ciência da Computação, uma estrutura de dados é uma forma particular de armazenamento e organização de dados em um computador de modo que possam ser usados de maneira eficiente. Os algoritmos que representam as estruturas de dados podem ser aplicados em diversas linguagens de programação. As estruturas básicas são a pilha, a fila, a lista e a árvore.

As pilhas são estruturas baseadas no princípio LIFO (last in, first out), na qual os dados que foram inseridos por último na pilha serão os primeiros a serem removidos. Existem duas funções que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove um dado do topo da pilha. As duas funções devem respeitar uma o limite de capacidade e a outra o estado vazio da pilha.

As filas são estruturas baseadas no princípio FIFO (first in, first out), em que os primeiros elementos que foram inseridos serão os primeiros a serem removidos. Uma fila possui duas funções básicas: INSERT, que adiciona um dado ao final da fila, e REMOVE, que remove um dado do início da fila. A mesma coisa para fila, as duas funções devem respeitar uma o limite de capacidade e a outra o estado vazio da fila.

Na estrutura de uma pilha devem conter as informações do limite, que indica a última posição disponível, e do topo, que indica a posição do último valor adicionado. E na estrutura de uma fila devem conter as informações do limite, que indica a última posição disponível, e do fim, que indica a posição do último valor adicionado. Em ambas as estruturas os valores são armazenados em vetores comuns.

Abaixo apresento um exemplo de código, na linguagem C, que traz as funções para as operações em pilhas e filas, contendo também uma interface para a escolha da operação. O código está preparado para o ambiente Linux, utilizando a biblioteca nCurses.

/*
 * pilhaefila.c
 *
 * Pequeno programa que demonstra as operações em uma pilha e uma fila.
 *
 * Compilar com o comando:
 * gcc -o pilhaefila pilhaefila.c -lncurses
 *
 */

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

#define ESC 27 /* constante ESC recebe o código da tecla Esc */

struct pilha{                /* pilha é LIFO, last in first out */
        int topo;            /* posição do último valor adicionado */
        int limite;          /* última posição disponível no vetor */
        int lista[10];       /* vetor de 0 a 9 */
};

struct fila{                 /* fila é FIFO, first in first out */
        int limite;          /* última posição disponível no vetor */
        int fim;             /* posição do último valor adicionado */
        int lista[10];       /* vetor de 0 a 9 */
};

int push(struct pilha* pi, int valor){ /* função que adiciona valor na pilha*/
    if(pi->limite == pi->topo){ /* se o topo já estiver no limite */
        printw("\nErro: Pilha cheia!");
        printw("\nPressione qualquer tecla para continuar...");
        getch();
    }
    else{
        pi->lista[pi->topo+1] = valor; /* o vetor da pilha recebe o valor na posição acima do topo */
        pi->topo++; /* o topo é incrementado para corresponder à posição do novo valor */
    }
}

int pop(struct pilha* pi){ /* função que retira um valor da pilha*/
    int AUX;
    if(pi->topo == -1){ /* se a pilha estiver vazia */
        printw("\n\nErro: Pilha vazia!");
        printw("\nPressione qualquer tecla para continuar...");
        getch();
    }
    else{
        AUX = pi->lista[pi->topo]; /* valor a ser retirado da pilha, o de cima */
        pi->lista[pi->topo] = 0; /* limpa a posição na qual estava o valor retirado */
        pi->topo--; /* decrementa o topo para a posição do valor abaixo */
        return AUX;
    }
}

int insert(struct fila* fi, int valor){ /* função que adiciona valor na fila*/
    if(fi->limite == fi->fim){ /* se o fim já estiver no limite */
        printw("\nErro: Fila cheia!");
        printw("\nPressione qualquer tecla para continuar...");
        getch();
    }
    else{
        fi->lista[fi->fim+1] = valor; /* o vetor da fila recebe o valor na posição atrás do último */
        fi->fim++; /* o fim é incrementado para corresponder à posição do novo valor */
    }
}

int remover(struct fila* fi){ /* função que retira um valor da fila*/
    int AUX, i;
    if(fi->fim == -1){ /* se a fila estiver vazia */
        printw("\n\nErro: Fila vazia!");
        printw("\nPressione qualquer tecla para continuar...");
        getch();
    }
    else{
        AUX = fi->lista[0]; /* valor a ser retirado da fila, o primeiro */
        for(i = 1; i <= fi->fim; i++){ /* do segundo valor até o último */
            fi->lista[i-1] = fi->lista[i]; /* transfere para uma posição à frente */
        }
        fi->lista[fi->fim] = 0; /* limpa a posição na qual estava o último valor */
        fi->fim--; /* decrementa o fim para atualizar a posição do último valor */
        return AUX;
    }
}

int main(){

    initscr();        /* inicialização do ncurses */
    cbreak();         /* desabilita o buffer do teclado */
    echo();           /* ativa o echo para os caracteres digitados */
    clear();          /* limpa a tela */

    char tecla; /* variável que recebe os comandos para as ações em pilha e fila */
    int valor, /* variável que recebe o valor para ser adicionado */
        i;

    struct pilha p1; /* estruturação das variáveis tipo pilha e fila */
    struct fila f1;

    /* inicialização dos valores para topo, fim e limite na pilha e na fila */
    p1.topo = -1; /* pilha vazia */
    p1.limite = 9; /* última posição no vetor */
    f1.fim = -1; /* fila vazia */
    f1.limite = 9; /* última posição no vetor */

    while (tecla != ESC){ /* enquanto não for pressionado Esc é executado o bloco a seguir */

        clear(); /* limpa a tela */
        printw("\nOperações em Pilha e Fila, o que deseja fazer? (ESC sair)"); /* menu inicial */
        printw("\n\nSintaxe:  (p)ilha (p)ush|p(o)p [valor]");
        printw("\n          (f)ila (i)nsert|(r)emove [valor]");
        printw("\n\nEx.:      pp45, fi9, po, fr.");
        printw("\n\nConteúdo da pilha: ");
        if(p1.topo >= 0){ /* se a pilha não estiver vazia */
            for(i = 0; i <= p1.topo; i++){ /* da posição 0 até a posição do topo */
                printw("%d ", p1.lista[i]); /* imprime todos os valores */
            }
        } else {
            printw("vazio");
        }
        printw("\nConteúdo da fila: ");
        if(f1.fim >= 0){ /* se a fila não estiver vazia */
            for(i = 0; i <= f1.fim; i++){ /* da posição 0 até a posição do fim */
                printw("%d ", f1.lista[i]); /* imprime todos os valores */
            }
        } else {
            printw("vazio");
        }
        printw("\n\n> "); /* prompt de linha comando */

        tecla = getch(); /* Lê a tecla pressionada, comando pilha ou fila */

        switch(tecla){
        case 'p': /* operação na pilha */
            tecla = getch(); /* Lê a tecla pressionada, comando push ou pop */
            switch(tecla){
            case 'p': /* chama a função que adiciona um valor */
                scanw("%d", &valor); /* recebe o valor */
                push(&p1, valor); /* executa a função */
                break;
            case 'o': /* chama a função que retira um valor */
                pop(&p1); /* executa a função */
                break;
            case ESC: /* operação de saída com confirmação */
                printw("\n\nDeseja sair? s/n ");
                if(getch() == 'n'){
                    tecla = 'n'; /* se não quiser sair então é retirado o Esc da tecla */
                }
                break;
            }
            break;
        case 'f': /* operação na fila */
            tecla = getch(); /* Lê a tecla pressionada, comando insert ou remove */
            switch(tecla){
            case 'i': /* chama a função que adiciona um valor */
                scanw("%d", &valor); /* recebe o valor */
                insert(&f1, valor); /* executa a função */
                break;
            case 'r': /* chama a função que retira um valor */
                remover(&f1); /* executa a função */
                break;
            case ESC: /* operação de saída com confirmação */
                printw("\n\nDeseja sair? s/n ");
                if(getch() == 'n'){
                    tecla = 'n'; /* se não quiser sair então é retirado o Esc da tecla */
                }
                break;
            }
            break;
        case ESC: /* operação de saída com confirmação */
            printw("\n\nDeseja sair? s/n ");
            if(getch() == 'n'){
                tecla = 'n'; /* se não quiser sair então é retirado o Esc da tecla */
            }
            break;
        }
    }

    endwin();    /* Finaliza o ncurses */
    return 0;
}