Implementando queues e stacks com arrays · letsaguiar

Introdução

Oie :D Queues e Stacks são estruturas de dados muito úteis no dia a dia de todo programador. Elas são estruturas lineares que suportam apenas operações de inserção e remoção. Ou seja, não são otimizadas para outros tipos de operações, como search ou sort. Ambas funcionam de modo muito similar, sendo sua principal diferença a regra que seguem para inserir e remover elementos do seu interior.

A ideia aqui é mostrar a forma mais simples e rápida de implementar essas duas estruturas: utilizando um array e alguns apontadores. Todos os códigos serão escritos em C, mas podem ser reproduzidos em qualquer outra linguagem. Se você quiser saber mais sobre essas estruturas (ou conhecer algumas outras) ao final deste artigo vou deixar alguns links bastante úteis e explicativos.

Queues

Queues (ou filas) são estruturas que realizam operações de inserção e remoção seguindo a regra FIFO (First In, First Out). Ou seja, sempre que quisermos remover um elemento, removeremos o elemento que está na estrutura há mais tempo. É comum chamarmos essas operações de enqueue (inserção) e dequeue (remoção).

Para implementar uma fila com um array, utilizaremos (além do array obviamente) dois apontadores. Um para o início e um para o fim da fila. Chamaremos eles de head e tail, respectivamente.

typedef struct {
    int arr[100];
    int head;
    int tail;
} queue;

Para poder manipular as filas, criaremos as funções getQueue, isEmpty e isFull.

/*
    Instancia uma nova queue e define
    o head e o tail para o valor padrão 0.
*/
queue *getQueue() {
    queue *new_queue;

    new_queue = malloc(sizeof (queue));
    new_queue->head = 0;
    new_queue->tail = 0;

    return new_queue;
}

/*
    A fila está vazia quando head == tail.
*/
int isEmpty(queue *q) {
    if (q->head == q->tail)
        return TRUE;

    return FALSE;
}

/*
    A fila está cheia quando o tail é maior ou
    igual a capacidade de armazenamento previamente
    definida.
*/
int isFull(queue *q) {
    if (q->tail >= 100)
        return TRUE;

    return FALSE;
}

Por fim, criamos nossas funções enqueue e dequeue.

void enqueue(queue *q, int x) {
    if (isFull(q) == FALSE) {
        q->arr[q->tail] = x;
        q->tail += 1;
    }
}

int dequeue(queue *q) {
    if (isEmpty(q) == FALSE) {
        int removed = q->arr[q->head];
        q->head += 1;

        return removed;
    }
}

Observações:

O tail sempre aponta para um slot vazio do array. Quando queremos, adicionamos um elemento na posição apontada pelo tail e em seguida o incrementamos.
O head sempre aponta para um slot preenchido. Quando não o faz, é porque head == tail e, neste caso, a fila está vazia.

Stacks

Stacks (ou pilhas) são estruturas que realizam operações de inserção e remoção seguindo a regra LIFO (Last In, First Out). Ou seja, sempre que quisermos remover um elemento, removeremos o elemento que está na estrutura há menos tempo. É comum chamarmos essas operações de push (inserção) e pop (remoção).

Para implementar uma pilha com um array, utilizaremos (além do array obviamente) um apontador que olha para o fim da pilha.

typedef struct {
    int arr[100];
    int tail;
} stack;

Também criaremos as funções getStack, isFull e isEmpty.

stack *getStack() {
    stack *new_stack;

    new_stack = malloc(sizeof(stack));
    new_stack->tail = 0;

    return new_stack;
}

int isEmpty(stack *s) {
    if (s->tail == 0)
        return TRUE;

    return FALSE;
}

int isFull(stack *s) {
    if (s->tail > 100) 
        return TRUE;

    return FALSE;
}

Por fim, criamos nossas funções push e pop.

void push(stack *s, int x) {
    if (isFull(s) == FALSE) {
        s->arr[s->tail] = x;
        s->tail += 1;
    }
}

int pop(stack *s) {
    if (isEmpty(s) == FALSE) {
        s->tail -= 1;
        return s->arr[s->tail];
    }
}

Observações:

O tail sempre aponta para um slot virtualmente vazio do array. Quando queremos, adicionamos ou sobrescrevemos o elemento na posição apontada pelo tail e o incrementamos.

Considerações Finais

Como disse acima, filas e pilhas são estruturas de dados bastante úteis no dia a dia de qualquer programador. Conhecer essas formas simples e diretas de implementação, podem te ajudar tanto nas tarefas diárias quanto em entrevistas de emprego (eu mesma já utilizei algumas vezes :D).

Qualquer dúvida sobre o código, estou à disposição para responder. Se quiserem se aprofundar mais no assunto, recomendo procurar mais sobre a implementação com listas ligadas e array circular. Além de alguns exemplos de aplicação.

Agora seguem alguns links para quem quiser ler e conhecer mais sobre filas, pilhas e outras estruturas de dados:

https://www.ime.usp.br/~pf/algoritmos/aulas/fila.html

https://www.geeksforgeeks.org/queue-data-structure/

https://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html

https://www.geeksforgeeks.org/stack-data-structure/

https://www.edx.org/professional-certificate/gtx-data-structures-and-algorithms