<Direto ao Ponto 51> Estruturas de Dados - Pilhas
Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )
Olá, dev!
Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Ele vai tratar de uma das principais estruturas de dados, as pilhas.
Sumário
1. Introdução
2. As pilhas
3. Formas de implementação de pilhas
4. Exemplos de aplicações implementadas com pilhas
5. Considerações finais
6. Referências
1 – Introdução
Eu criei a série de artigos DIRETO AO PONTO com o objetivo de apresentar, de forma simples e direta, conhecimentos básicos da programação e de computação, principalmente, para os iniciantes.
Aqui, são tratados de temas como lógica de programação, linguagens, hardware dos computadores, história da computação e assuntos relacionados à plataforma da DIO, como a escrita de artigos e os desafios de código.
Neste artigo, eu vou falar sobre as pilhas e as aplicações que usam pilhas na implementação. Dentre estas aplicações, estão os servidores de impressão e servidores web.
2 – As pilhas
No mundo real, podemos associar a estrutura de dados pilha a uma pilha de objetos (pratos, livros, discos etc.), como na figura acima (pilha de meus CDs do Pink Floyd!!).
Da mesma forma que as filas, as pilhas também são um Tipo Abstrato de Dado (TAD), definição de um modelo matemático para tipos de dados. Basicamente, um TAD especifica um conjunto de dados e as operações que podem ser realizadas sobre eles, sem tratar da implementação destas operações.
A estrutura de dados pilha é usada para armazenar elementos de forma ordenada, seguindo o princípio LIFO (“Last In, First Out”), ou seja, o último elemento a entrar é o primeiro a sair.
Este comportamento é útil em várias situações, para gerenciar tarefas em ordem sequencial. Algumas aplicações são listadas a seguir:
· Gerenciamento de memória, em operações de alocação e liberação;
· Algoritmos de “backtracking”, para busca e otimização;
· Implementação de funções recursivas, garantindo o retorno dos dados nas chamadas às funções.
· Desfazer e refazer em Aplicações, os famosos “Undo” e “Redo”;
· Navegação em “browsers”, com o botão “Voltar”;
· Endereçamento de instruções em microprocessadores, para retorno de funções, por exemplo:
· Avaliação de expressões matemáticas, na conversão da notação infixa para pós-fixa (polonesa reversa);
· Análise de expressões aritméticas, por exemplo, na verificação de balanceamento de parênteses;
· Processamento de linguagens, em operações como análise sintática.
Uma pilha possui as seguintes características principais:
· Armazenamento de dados homogêneos;
· Seguem o princípio LIFO (“Last In, First Out”), onde o último elemento inserido é o primeiro a sair;
· Um elemento só pode ser inserido na última posição da pilha;
· Só o último elemento pode ser removido;
· Uma variável aponta para o último elemento da pilha;
· Cada elemento aponta apenas para o seu elemento anterior;
· Só pode ser varrida a partir do último elemento, voltando até o primeiro;
· Se implementada usando vetor estático, a pilha têm um tamanho limitado. Quando sua capacidade é excedida, ocorre um estouro de pilha (“stack overflow”).
As operações básicas que podem ser realizadas com uma pilha são (em pseudo-código, independentemente de alguma linguagem de programação específica:
Criação (ou declaração) – nomeia a variável, informa o tipo e reserva espaço para os elementos:
int pilha[10] – declara um vetor de inteiros com 10 posições
int topo - declara inteiro para o índice onde deve ser inserido um novo elemento, ou removido da pilha.
Inicialização – ao declarar a pilha, já informar os seus dados (elementos):
int pilha = [3, 4, 0, 1, -5, 6 ] – declara um vetor de inteiros com 6 posições. Para esta pilha, topo vale 5 (índice do valor 6);
int topo = -1 - declara inteiro com o índice (-1, nulo) do primeiro elemento a inserir
Acesso – Só pode ser acessado o valor armazenado na primeira posição da pilha, na operação de remoção do primeiro elemento:
elemento = pilha[topo]; // na pilha acima, o valor acessado é 6 (último elemento)
print(pilha[topo]) // imprime o valor 6, que era o último elemento da pilha acima
Atribuição – não se pode atribuir um valor para nenhuma posição da pilha. Além disso, novos elementos só podem ser inseridos no final da pilha, após o último elemento presente, numa operação de inserção:
pilha[topo] = 9; // atribui o valor 9 à última posição da pilha acima, que ficaria [4, 0, 1, -5, 6, 9 ].
Topo = topo + 1; // incrementa a variável que aponta para o topo da pilha
Pilha vazia – Se a pilha não possuir nenhum elemento armazenado, ela estará vazia e a operação de remoção não pode ser realizada.
pilha = [ ] – pilha sem nenhum elemento (vazia)
se topo = -1, a fila está vazia; // ou outro valor nulo (0, null), dependendo da implementação
Pila cheia – Se a pilha usar todo o espaço para inserção de elementos, ela estará cheia e a operação de inserção não pode ser realizada. Este caso pode ocorrer no caso estático de um vetor cheio ou, no caso dinâmico, sistema sem memória para alocação dinâmica.
Por exemplo, a pilha [4, 0, 1, -5, 6, 9 ], usando um vetor estático de 6 elementos, está cheia, sem caber novos elementos.
Se topo = MAX_ELEMENTOS, a pilha está cheia.
Algumas operações ainda podem ser realizadas com a pilha, mas são operações opcionais, não fazendo parte do comportamento obrigatório de uma estrutura do tipo pilha, pois elas acessam o vetor além das operações de empilhar e desempilhar:
Listar elementos da pilha – Esta operação varre todos os elementos da pilha e os lista, seguindo do último elemento para o primeiro.
Tamanho da pilha - Esta operação varre todos os elementos da pilha, do último até o primeiro, contando quantos estão armazenados nela.
Limpeza da pilha - Esta operação limpa, de uma vez só, o conteúdo de todos os elementos do vetor para um valor considerado nulo (0, string vazio, null etc.).
Por exemplo, pilha = [ ] – cria (ou atribui a uma) pilha sem elemento (vazia)
OBS – Note que estas operações opcionais acessam os elementos do vetor pelos seus índices, fugindo do comportamento tradicional de uma pilha. Embora elas resultem em informações interessantes, não fazem parte do comportamento esperado de uma pilha, mas apenas de um vetor. Devem ser desencorajadas para o uso de uma pilha tradicional.
3 - Formas de implementação de pilhas
Uma pilha pode ser implementada de várias maneiras: usando vetor estático, lista encadeada (com ponteiros), com um tipo lista (list) ou por um tipo específica (Stack). Vamos ver um resumo de cada uma delas.
I - IMPLEMENTAÇÃO COM LISTA
É bem parecida com aquela mostrada no artigo anterior, em que eu detalhei o uso de filas.
Uma pilha só pode ser percorrida do final para o início e um novo elemento só pode ser adicionado no final dela, além de só poder ser removido o seu último elemento (ver figura a seguir).
A pilha tem só um ponteiro (topo da pilha) que aponta para o seu elemento final. Se o ponteiro do topo da pilha apontar para o valor nulo, significa que a pilha está vazia, sem nenhum elemento armazenado.
Para inserir um novo elemento, basta fazer o novo elemento da pilha apontar (campo ant) para o último elemento (atual topo da pilha) e atualizar a variável de topo da pilha, que apontará para o novo elemento, como novo último da pilha (ver figura, pilha inicial).
Após a inserção do novo elemento, a pilha ficaria assim:
Só o último elemento da pilha poderá ser removido, significando que ele saiu para ser usado, passando o elemento anterior a ser o novo topo da pilha. Com base na figura da pilha inicial, abaixo é mostrada a operação de remoção do último elemento:
E a pilha ficará assim:
OBS: um elemento removido não é apagado, ele continua armazenado na estrutura do nó, no mesmo endereço alocado na sua criação, apenas não será mais acessado por nenhum ponteiro (campo ant) da pilha.
II - IMPLEMENTAÇÃO COM VETOR ESTÁTICO
Uma pilha de objetos (pratos, livros, discos etc.) é uma estrutura vertical e pode ser visualizada desta forma, como mostra a figura:
Para usar um vetor para simular uma pilha, vamos mudá-la para a posição horizontal, mais parecida com a estrutura vetor. Assim, ela segue o modelo mostrado no artigo sobre filas (anterior a este), com diferenças que vou mostrar agora (ver figura da pilha):
Basicamente, é preciso criar um vetor com um número determinado de posições, usar uma variável para determinar o índice do último elemento da pilha. No início, uma pilha que acabou de ser criada ficaria assim, vazia (a variável topo aponta para um valor nulo (-1 ou 0, dependendo do algoritmo usado):
Cada inserção de um novo elemento será feita na posição indicada pelo índice da variável de topo da pilha, que depois será incrementada de 1 posição. Ver figura com a inserção (empilhamento) de 1 elemento:
A figura a seguir mostra a inserção (empilhamento) de mais um elemento:
Cada remoção de elemento será feita na posição indicada pelo índice da variável de topo da pilha, que também será decrementada de 1. Vamos remover 1 elemento da pilha (desempilhar) da figura anterior:
A figura a seguir mostra a pilha após a remoção do elemento -1 (topo da pilha). Veja que a pilha voltou à situação em que só tinha 1 item (o elemento 8):
OBS: na verdade, um elemento removido não sai do vetor, ele continuará lá, na mesma posição, apenas não será mais acessado.
A partir da figura anterior, removendo mais 1 elemento, a pilha ficará vazia e nenhum elemento poderá ser removido. A situação de pilha vazia pode ser identificada quando o valor da variável de topo da pilha tiver um valor nulo (-1), que não pode ser usado como índice.
Após várias inserções (empilhamentos), todas as posições do vetor podem ser ocupadas, deixando a pilha cheia, não aceitando mais inserções de elementos. Inserindo mais elementos na pilha vazia da figura anterior, ela ficaria cheia, assim:
Se o código permitir a inserção de mais 1 elemento na pilha após ela estar cheia, ocorrerá o famoso estouro da pilha (“stack overflow”). Neste caso, será armazenado algum dado em posição de memória não autorizada (ou previamente alocada para o vetor), podendo causar muitos problemas. Inclusive, esta brecha de segurança é usada por hackers mal-intencionados para tentar invadir sistemas.
Pilhas implementadas com vetores são limitadas, mas são muito simples e didáticas para um ensino inicial do tema.
III - IMPLEMENTAÇÃO USANDO A ESTRUTURA LIST
Esta implementação segue as seguintes características:
Uma lista pode ser criada sem nenhum elemento, significando uma pilha vazia.
Ex: pilha = [ ]
A operação de atribuição de um valor (ou inserção de um elemento) na pilha se dá sempre na última posição da lista. Em Python, o método seria append():
Por exemplo, para lista = [ 8, -1, 4, 25, 0],
list.append(7) insere o valor 7 na última posição, ficando [ 8, -1, 4, 25, 0, 7]. (ver figura)
A operação de acesso a um valor (ou remoção de um elemento) da pilha também é realizada sempre na última posição da lista. Em Python, o método é pop( ).
Por exemplo, para lista = [ 8, -1, 4, 25, 0, 7 ], list.pop( ) exclui o valor (7) da última posição, resultando em [ 8, -1, 4, 25, 0 ] (ver figura)
IV - IMPLEMENTAÇÃO USANDO UM TIPO ESPECÍFICO PARA PILHA
Esta implementação segue as seguintes características:
Algumas linguagens oferecem um tipo específico para tratar de pilhas (stacks), com pelo menos 2 métodos para inserir e remover elementos.
Por exemplo, a linguagem C++ oferece o tipo std::stack, com os métodos básicos:
· push(valor), para adicionar um elemento (empilhar) no topo da pilha;
· pop( ), para remover o último elemento (desempilhar) do topo da pilha.
Este tipo (Stack) ainda oferece outros métodos específicos para manipulação de pilhas:
· top( ): Retorna o elemento no topo da pilha sem removê-lo;
· empty( ): Verifica se a pilha está vazia;
4 – Exemplos de aplicações implementadas com pilha
A seguir, seguem alguns programas básicos que implementam pilhas, em linguagens diferentes:
NA LINGUAGEM PASCAL – USANDO VETOR ESTÁTICO
program PilhaComVetor;
uses crt;
const
MAX = 4; // Tamanho máximo da pilha
type
TPilha = record
dados: array[1..MAX] of Integer;
topo: Integer;
end;
{ Inicializa a pilha }
procedure InicializarPilha(var pilha: TPilha);
begin
pilha.topo := 0; // Pilha vazia
end;
{ Verifica se a pilha está vazia }
function PilhaVazia(pilha: TPilha): Boolean;
begin
PilhaVazia := (pilha.topo = 0);
end;
{ Verifica se a pilha está cheia }
function PilhaCheia(pilha: TPilha): Boolean;
begin
PilhaCheia := (pilha.topo = MAX);
end;
{ Adiciona um elemento ao topo da pilha (Push) }
procedure Empilhar(var pilha: TPilha; elemento: Integer);
begin
if PilhaCheia(pilha) then
writeln('Erro: a pilha está cheia, não é possível empilhar.')
else
begin
pilha.topo := pilha.topo + 1;
pilha.dados[pilha.topo] := elemento;
writeln('Elemento ', elemento, ' empilhado com sucesso.');
end;
end;
{ Remove o elemento do topo da pilha (Pop) }
function Desempilhar(var pilha: TPilha): Integer;
begin
if PilhaVazia(pilha) then
begin
writeln('Erro: a pilha está vazia, não é possível desempilhar.');
Desempilhar := -1; // Retorna -1 para indicar erro
end
else
begin
Desempilhar := pilha.dados[pilha.topo];
pilha.topo := pilha.topo - 1;
end;
end;
{ Retorna o elemento do topo da pilha sem removê-lo }
function Topo(pilha: TPilha): Integer;
begin
if PilhaVazia(pilha) then
begin
writeln('Erro: a pilha está vazia.');
Topo := -1; // Retorna -1 para indicar erro
end
else
Topo := pilha.dados[pilha.topo];
end;
{ Programa principal }
var
pilha: TPilha;
elemento: Integer;
begin
clrscr;
InicializarPilha(pilha);
{ Empilhando elementos na pilha }
Empilhar(pilha, 10);
Empilhar(pilha, 20);
Empilhar(pilha, 30);
{ Exibindo o elemento do topo }
writeln('Elemento no topo: ', Topo(pilha));
{ Desempilhando um elemento }
elemento := Desempilhar(pilha);
writeln('Elemento desempilhado: ', elemento);
{ Exibindo o novo topo da pilha }
writeln('Novo elemento no topo: ', Topo(pilha));
{ Verificando se a pilha está vazia }
if PilhaVazia(pilha) then
writeln('A pilha está vazia.')
else
writeln('A pilha não está vazia.');
readln; // Espera o usuário pressionar uma tecla antes de sair
end.
Saída do programa
Elemento 10 empilhado com sucesso.
Elemento 20 empilhado com sucesso.
Elemento 30 empilhado com sucesso.
Elemento no topo: 30
Elemento desempilhado: 30
Novo elemento no topo: 20
A pilha não está vazia.
LINGUAGEM C – USANDO LISTA ENCADEADA COM PONTEIROS
#include <stdio.h>
#include <stdlib.h>
// Definição da estrutura de um nó da pilha
struct Node {
int data; // Valor do nó
struct Node* next; // Ponteiro para o próximo nó
};
// Função para empilhar um elemento na pilha
void push(struct Node** top, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Aloca memória para um novo nó
if (newNode == NULL) {
printf("Erro: Não foi possível alocar memória.\n");
return;
}
newNode->data = value; // Armazena o valor no nó
newNode->next = *top; // Aponta o novo nó para o topo atual
*top = newNode; // Atualiza o topo da pilha para o novo nó
printf("Elemento %d empilhado com sucesso.\n", value);
}
// Função para desempilhar um elemento da pilha
int pop(struct Node** top) {
if (*top == NULL) { // Verifica se a pilha está vazia
printf("Erro: A pilha está vazia, não é possível desempilhar.\n");
return -1; // Retorna -1 para indicar erro
}
struct Node* temp = *top; // Armazena o nó do topo para liberar depois
int value = temp->data; // Armazena o valor do topo para retornar
*top = (*top)->next; // Move o topo para o próximo nó
free(temp); // Libera a memória do nó removido
return value; // Retorna o valor do nó desempilhado
}
// Função para retornar o elemento do topo da pilha sem removê-lo
int peek(struct Node* top) {
if (top == NULL) { // Verifica se a pilha está vazia
printf("Erro: A pilha está vazia.\n");
return -1; // Retorna -1 para indicar erro
}
return top->data; // Retorna o valor do topo
}
// Função para verificar se a pilha está vazia
int isEmpty(struct Node* top) {
return (top == NULL); // Retorna 1 se a pilha estiver vazia, 0 caso contrário
}
// Programa principal para demonstrar as operações da pilha
int main() {
struct Node* pilha = NULL; // Inicializa a pilha como vazia
// Empilhando elementos na pilha
push(&pilha, 10);
push(&pilha, 20);
push(&pilha, 30);
// Exibindo o elemento no topo da pilha
printf("Elemento no topo: %d\n", peek(pilha));
// Desempilhando um elemento
int elemento = pop(&pilha);
printf("Elemento desempilhado: %d\n", elemento);
// Exibindo o novo topo da pilha
printf("Novo elemento no topo: %d\n", peek(pilha));
// Verificando se a pilha está vazia
if (isEmpty(pilha))
printf("A pilha está vazia.\n");
else
printf("A pilha não está vazia.\n");
return 0;
}
Saída do programa
Elemento 10 empilhado com sucesso.
Elemento 20 empilhado com sucesso.
Elemento 30 empilhado com sucesso.
Elemento no topo: 30
Elemento desempilhado: 30
Novo elemento no topo: 20
A pilha não está vazia.
NA LINGUAGEM PYTHON – USANDO O TIPO LIST
# Função para empilhar um elemento na pilha
def push(pilha, elemento):
pilha.append(elemento)
print(f'Elemento {elemento} empilhado com sucesso.')
# Função para desempilhar um elemento da pilha
def pop(pilha):
if len(pilha) == 0:
print('Erro: A pilha está vazia, não é possível desempilhar.')
return None # Retorna None para indicar erro
else:
return pilha.pop()
# Função para retornar o elemento no topo da pilha sem removê-lo
def peek(pilha):
if len(pilha) == 0:
print('Erro: A pilha está vazia.')
return None # Retorna None para indicar erro
else:
return pilha[-1]
# Função para verificar se a pilha está vazia
def is_empty(pilha):
return len(pilha) == 0
# Programa principal para demonstrar as operações da pilha
def main():
pilha = [] # Inicializa a pilha como uma lista vazia
# Empilhando elementos na pilha
push(pilha, 10)
push(pilha, 20)
push(pilha, 30)
# Exibindo o elemento no topo da pilha
print(f'Elemento no topo: {peek(pilha)}')
# Desempilhando um elemento
elemento = pop(pilha)
print(f'Elemento desempilhado: {elemento}')
# Exibindo o novo topo da pilha
print(f'Novo elemento no topo: {peek(pilha)}')
# Verificando se a pilha está vazia
if is_empty(pilha):
print('A pilha está vazia.')
else:
print('A pilha não está vazia.')
# Executa o programa principal
if __name__ == "__main__":
main()
Saída do programa
Elemento 10 empilhado com sucesso.
Elemento 20 empilhado com sucesso.
Elemento 30 empilhado com sucesso.
Elemento no topo: 30
Elemento desempilhado: 30
Novo elemento no topo: 20
A pilha não está vazia.
LINGUAGEM C++ – USANDO O TIPO ESPECÍFICO STACK;
#include <iostream>
#include <stack> // Biblioteca para usar a classe stack
int main() {
// Cria uma pilha usando a classe stack
std::stack<int> pilha;
// Empilhando elementos na pilha
pilha.push(10);
std::cout << "Elemento 10 empilhado com sucesso." << std::endl;
pilha.push(20);
std::cout << "Elemento 20 empilhado com sucesso." << std::endl;
pilha.push(30);
std::cout << "Elemento 30 empilhado com sucesso." << std::endl;
// Exibindo o elemento no topo da pilha
std::cout << "Elemento no topo: " << pilha.top() << std::endl;
// Desempilhando um elemento
int elemento = pilha.top();
pilha.pop();
std::cout << "Elemento desempilhado: " << elemento << std::endl;
// Exibindo o novo topo da pilha
std::cout << "Novo elemento no topo: " << pilha.top() << std::endl;
// Verificando se a pilha está vazia
if (pilha.empty()) {
std::cout << "A pilha está vazia." << std::endl;
} else {
std::cout << "A pilha não está vazia." << std::endl;
}
return 0;
}
Saída do programa
Elemento 10 empilhado com sucesso.
Elemento 20 empilhado com sucesso.
Elemento 30 empilhado com sucesso.
Elemento no topo: 30
Elemento desempilhado: 30
Novo elemento no topo: 20
A pilha não está vazia.
5 – Considerações finais
Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Neste artigo eu tratei das pilhas, mais um Tipo Abstrato de Dado (TAD), juntamente com as listas e filas.
Uma pilha é uma estrutura de dados, como a fila, usada para armazenar elementos de forma ordenada, mas com características de inserção e remoção de elementos. Ela segue o princípio LIFO (“Last In, First Out”), no qual o último elemento a entrar é o primeiro a sair.
Elas são apropriadas em aplicações que usam a característica de guardar um valor para usá-lo depois de processas outras operações relacionadas, postergando o seu uso.
As aplicações mais comuns que usam pilhas são o gerenciamento de memória, a implementação de funções recursivas, e na operação de desfazer ações, como em edição de texto ou copiar colar, por exemplo.
Uma pilha pode ser implementada de várias formas, usando vetores estáticos, ponteiros, listas ou estruturas específicas para manipulação de pilhas, como stack, da linguagem C#.
Algumas destas formas são bem antigas (vetores), mas continuam em uso por serem muito didáticas, principalmente para os iniciantes em programação, já outras são bem trabalhosas (com ponteiros), pois exigem completo gerenciamento da memória pelo programador.
As formas mais atuais de implementação são usando listas (como em Python) ou estruturas específicas, como a classe std::stack, da linguagem C++, ou Stack, de C#, por exemplo.
Neste artigo, foram mostrados os detalhes dos conceitos e das operações usadas para a implementação de pilhas usando vetores e ponteiros.
Também foram apresentados exemplos de códigos com a implementação de pilhas usando cada uma das 4 formas citadas anteriormente.
No próximo artigo, vamos falar das árvores, estruturas de dados hierárquicas muito usadas na programação.
6 – Referências
Praticamente todo o conteúdo deste artigo foi tirado do que eu aprendi (e me lembro) sobre o assunto desde o início da minha carreira como programador, desde os anos 80 até agora.
Para criar os códigos dos exemplos, eu consultei o ChatGPT e fiz algumas correções necessárias para sair do jeito que eu queria. Todos os códigos foram testados e rodaram sem problemas.
Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )
