Pilhas e filas são estruturas de dados comumente usadas em ciência da computação. São estruturas de dados lineares que seguem regras específicas para adicionar e remover elementos.

Pilhas

Vamos começar com Stacks. Uma stack é uma estrutura de dados Last-in, First-out (LIFO). Isso significa que o último elemento que foi adicionado à pilha é o primeiro a ser removido. As pilhas têm duas extremidades, que conhecemos como topo e base. Elementos são adicionados e removidos do topo da pilha. Você pode pensar em uma pilha como uma pilha de pratos, onde você só pode colocar pratos no topo da pilha e pegar pratos do topo da pilha. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-stacks-and-queues-work-1.png" alt="stack data structure visualization"> Essas operações de adicionar e remover elementos têm nomes especiais neste contexto. Adicionar um elemento a uma pilha é conhecido como uma operação de "push". Dizemos que "empurramos" um elemento para a pilha quando o adicionamos ao topo da pilha. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-stacks-and-queues-work-2.png" alt="stack push operation visualization"> Remover um elemento de uma pilha é conhecido como uma operação de "pop". Dizemos que "popamos" um elemento da pilha quando o removemos do topo da pilha. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-stacks-and-queues-work-3.png" alt="stack pop operation visualization"> Você pode ver que realmente não realizamos nenhuma operação na parte inferior da pilha mas a mantemos lá como referência. A complexidade de tempo das operações push e pop é tipicamente O(1), uma complexidade de tempo constante. Quando você empilha um elemento na pilha, o elemento é simplesmente adicionado ao topo. Quando você remove um elemento da pilha, o elemento no topo é removido. Portanto, o tempo necessário para executar essas operações permanece constante independentemente do tamanho da pilha. A complexidade espacial das operações push e pop geralmente é constante O(1). Isso significa que a quantidade de memória necessária para realizar essas operações permanece constante independentemente do tamanho da pilha.

Filas

Agora que você sabe mais sobre pilhas, vamos aprender sobre Filas. Uma fila é uma estrutura de dados linear First-in First-out (FIFO). Isso significa que o primeiro elemento adicionado à fila é o primeiro a ser removido. As filas têm duas extremidades: frente e trás. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-stacks-and-queues-work-4.webp" alt="queue data structure visualization"> Elementos são adicionados ao final da fila e eles são removidos do início da fila. Você pode pensar em uma fila como uma linha de pessoas esperando para pagar suas compras no supermercado. A primeira pessoa na fila é a primeira a ir para o caixa enquanto novas pessoas entram na fila no final. As operações de adicionar e remover elementos têm nomes especiais no contexto de uma fila. Adicionar um elemento ao final de uma fila é conhecido como uma operação de "enqueue". Em uma operação de enqueue, o novo elemento é adicionado ao final da fila, tornando-se o final da linha. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-stacks-and-queues-work-5.png" alt="queue enqueue operation visualization"> Remover um elemento do início da fila é conhecido como uma operação de "dequeue". Na operação de dequeue, o elemento na frente da fila é removido e o próximo elemento na linha se torna a nova frente. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-stacks-and-queues-work-6.png" alt="queue dequeue operation visualization"> A complexidade de tempo das operações de enqueue e dequeue é O(1), tempo constante. O tempo necessário para realizar essas operações permanece constante, independentemente do tamanho da fila. A complexidade de espaço das operações de enqueue e dequeue geralmente é constante O(1). Isso significa que a quantidade de memória necessária para realizar essas operações permanece constante independentemente do tamanho da fila. Pilhas e filas são estruturas de dados usadas em ciência da computação para organizar e gerenciar elementos. Entendê-los é essencial para construir algoritmos eficientes em várias aplicações de programação.