Introdução
Uma pilha é uma estrutura de dados linear que segue uma ordem específica na qual as operações são executadas. A ordem pode ser LIFO (Last In First Out) ou FILO (First In Last Out). LIFO implica que o elemento inserido por último sai primeiro e FILO implica que o elemento inserido primeiro sai por último.
stack
Uma pilha pode ser visualizada como uma pilha de objetos, como pratos, livros ou cartões. O objeto colocado no topo da pilha é o primeiro a ser removido, e o objeto colocado no fundo da pilha é o último a ser removido. O topo da pilha é a única posição onde podemos acessar, inserir ou deletar um elemento.
As pilhas são úteis para muitos aplicativos, como avaliação de expressões, chamadas de função, retrocesso e operações de desfazer/refazer. Esses aplicativos requerem armazenamento e recuperação de dados em ordem inversa, o que pode ser facilmente obtido usando pilhas.
Operações básicas
Uma pilha suporta quatro operações básicas: push, pop, peek e isEmpty. Algumas implementações também podem suportar uma quinta operação: isFull. Essas operações são definidas da seguinte forma:
Empurrar: Esta operação adiciona um elemento ao topo da pilha. Se a pilha estiver cheia, diz-se que há uma condição de estouro.
Pop: Esta operação remove e retorna o elemento do topo da pilha. Se a pilha estiver vazia, diz-se que há uma condição de subfluxo.
Olhadinha: Esta operação retorna o elemento do topo da pilha sem removê-lo. Ele pode ser usado para verificar o elemento atual na pilha.
Está vazia: Esta operação retorna true se a pilha estiver vazia, senão false. Ele pode ser usado para verificar se há algum elemento na pilha ou não.
Está cheio: Esta operação retorna true se a pilha estiver cheia, senão false. Ele pode ser usado para verificar se há algum espaço restante na pilha ou não.
Implementação
Uma pilha pode ser implementada usando diferentes estruturas de dados, como arrays ou listas encadeadas. A escolha da estrutura de dados depende de vários fatores, como uso de memória, desempenho e facilidade de implementação. Aqui discutiremos duas formas comuns de implementar uma pilha: usando array e usando lista encadeada.
Usando matriz
Uma matriz é um contêiner de tamanho fixo que armazena elementos em um bloco contíguo de memória. Para implementar uma pilha usando um array, precisamos manter duas variáveis: um array para armazenar os elementos e um inteiro para acompanhar o índice superior da pilha. O índice superior aponta inicialmente para -1, indicando que a pilha está vazia. Quando colocamos um elemento na pilha, incrementamos o índice superior e armazenamos o elemento naquela posição no array. Quando extraímos um elemento da pilha, retornamos o elemento no índice superior e o decrementamos. A operação peek simplesmente retorna o elemento no índice superior sem alterá-lo. A operação isEmpty verifica se o índice superior é -1 ou não. A operação isFull verifica se o índice superior é igual ao tamanho do array menos um ou não.
A vantagem de usar um array para implementar uma pilha é que é simples e rápido. A desvantagem é que tem um tamanho fixo e não pode crescer ou encolher dinamicamente. Se tentarmos colocar um elemento em uma pilha completa ou remover um elemento de uma pilha vazia, encontraremos um erro de estouro ou estouro, respectivamente.
Usando lista encadeada
Uma lista vinculada é um contêiner de tamanho dinâmico que armazena elementos em nós que são vinculados por ponteiros Uma lista vinculada é um contêiner de tamanho dinâmico que armazena elementos em nós vinculados por ponteiros. Para implementar uma pilha usando uma lista vinculada, precisamos manter um ponteiro para o nó principal da lista, que representa o topo da pilha. O ponteiro de cabeçalho inicialmente aponta para nulo, indicando que a pilha está vazia.Quando colocamos um elemento na pilha, criamos um novo nó com o elemento como seus dados e o ponteiro do cabeçalho como seu próximo ponteiro e, em seguida, atualizamos o ponteiro do cabeçalho para apontar para o novo nó. Quando retiramos um elemento da pilha, retornamos os dados do nó principal e atualizamos o ponteiro do cabeçalho para apontar para o próximo nó. A operação peek simplesmente retorna os dados do nó principal sem alterá-los. A operação isEmpty verifica se o ponteiro da cabeça é nulo ou não. A operação isFull não é aplicável para uma implementação de lista encadeada, pois pode crescer ou diminuir dinamicamente dependendo da memória disponível.
A vantagem de usar uma lista encadeada para implementar uma pilha é que ela não tem tamanho fixo e pode acomodar qualquer número de elementos. A desvantagem é que ele requer espaço extra para armazenar os ponteiros e pode ser mais lento do que uma implementação de array devido à manipulação de ponteiros e alocação/desalocação de memória.
Exemplos
Agora que aprendemos como implementar uma pilha usando diferentes estruturas de dados, vamos ver alguns exemplos de como as pilhas podem ser usadas para resolver vários problemas.
Avaliação de expressões
Uma aplicação comum de pilhas é avaliar expressões aritméticas que envolvem operadores e operandos. Por exemplo, dada uma expressão como "2 + 3 * 4 - 5 / (6 + 7)", como podemos calcular seu valor? Uma maneira é usar duas pilhas: uma para armazenar operandos e outra para armazenar operadores. Podemos escanear a expressão da esquerda para a direita e realizar os seguintes passos:
Se encontrarmos um operando, nós o colocamos na pilha de operandos.
Se encontrarmos um operador, comparamos sua precedência com o operador superior na pilha de operadores. Se o operador atual tiver maior precedência, nós o colocamos na pilha de operadores. Se o operador atual tiver precedência menor ou igual, extraímos dois operandos da pilha de operandos e um operador da pilha de operadores, aplicamos o operador aos operandos e colocamos o resultado de volta na pilha de operandos.Repetimos esta etapa até que a pilha de operadores esteja vazia ou o operador atual tenha precedência maior do que o operador superior na pilha de operadores.
Se encontrarmos um parêntese de abertura '(', nós o colocamos na pilha de operadores.
Se encontrarmos um parêntese de fechamento ')', retiramos os operadores da pilha de operadores e os aplicamos aos operandos da pilha de operandos até chegarmos a um parêntese de abertura '('. Em seguida, removemos e descartamos o parêntese de abertura da pilha de operadores.
Quando chegamos ao final da expressão, removemos os operadores da pilha de operadores e os aplicamos aos operandos da pilha de operandos até que a pilha de operadores esteja vazia. O valor final na pilha de operandos é o resultado da expressão.
Por exemplo, vamos avaliar a expressão "2 + 3 * 4 - 5 / (6 + 7)" usando este método. Usaremos duas pilhas: S1 para operandos e S2 para operadores. A tabela abaixo mostra as etapas e o estado das pilhas em cada etapa.
Passo Expressão S1 S2 Ação --- --- --- --- --- 1 2 + 3 * 4 - 5 / (6 + 7) Digitalizar da esquerda para a direita 2 2 + 3 * 4 - 5 / (6 + 7) 2 Empurre o operando para S1 3 2 + 3 * 4 - 5 / (6 + 7) 2 + Empurre o operador para S2 4 2 + 3 * 4 - 5 / (6 + 7) 2,3 + Empurre o operando para S1 5 2 + 3 * 4 - 5 / (6 + 7) 2,3 +,* Empurre o operador para S2 6 2 + 3 * 4 - 5 / (6 + 7) 2,3,4 +,* Empurre o operando para S1 7 2 + 3 * 4 - 5 / (6 + 7) 2,12 - Retirar dois operandos e um operador das pilhas, aplicar *, inserir o resultado em S1, inserir o operador em S2 8 2 + 3 * 4 - 5 / (6 + 7) 2,12,5 - / Empurre o operando para S1, empurre o operador para S2 92+3*4-5/(6+7)2,12,5-,/,(Empurre o operador para S2 102+3*4-5/(6+7)2,12,5,6-,/,(,+Insira o operando em S1, insira o operador em S2 112+3*4-5/(6+7)2,12,5,6-,/,(,+Sem ação 122+3*4-5/(6+7)2,12,5,6,7-,/,(,+Insira operando em S1 132+3*4-5/(6+7)2,12,5,13-,/Extrai dois operandos e um operador das pilhas, aplica +, coloca o resultado em S1, retira e descarta ( de S2 142+3*4-5/(6+7)10-Extrair dois operandos e um operador das pilhas, aplicar /, colocar o resultado em S1 1514,+-Extrai dois operandos e um operador das pilhas, aplica -, coloca o resultado em S1 1610Extrai dois operandos e um operador das pilhas, aplica +, coloca o resultado em S1 O valor final na pilha de operandos é o resultado da expressão. Neste caso, é 10.
Chamadas de função e recursão
Uma pilha também pode ser usada para rastrear chamadas de função e recursão. Quando uma função é chamada por outra função ou por ela mesma (recursão), o programa precisa armazenar algumas informações sobre o estado atual da execução, como o endereço de retorno, as variáveis locais e os parâmetros. Essas informações são armazenadas em uma estrutura de dados chamada pilha de chamadas ou pilha de funções. Cada chamada de função cria uma nova entrada ou um quadro na pilha de chamadas que contém as informações relacionadas a essa chamada. Quando uma função retorna ou termina, seu quadro é retirado da pilha de chamadas e o controle é transferido para a função anterior na pilha de chamadas.
A pilha de chamadas ajuda a manter a ordem de execução e a retomar a execução após uma chamada de função. Também ajuda a implementar a recursão, que é uma técnica de resolver um problema dividindo-o em subproblemas menores do mesmo tipo. Uma função recursiva chama a si mesma com diferentes argumentos até atingir um caso base ou uma condição de terminação. A pilha de chamadas armazena os resultados e parâmetros intermediários de cada chamada recursiva até atingir o caso base. Em seguida, ele desenrola e retorna o resultado final retirando os quadros da pilha de chamadas.
Por exemplo, vamos considerar uma função recursiva que calcula o fatorial de um determinado número. O fatorial de um número n é definido como o produto de todos os inteiros positivos de 1 a n. Pode ser expresso como:
fatorial(n) = n * fatorial(n-1) se n > 0
fatorial(n) = 1 se n = 0
O caso base desta função recursiva é quando n é igual a 0, caso em que retorna 1. Caso contrário, ela chama a si mesma com n-1 como argumento e multiplica o resultado por n. A pilha de chamadas armazena os valores de n e o endereço de retorno para cada chamada recursiva até atingir o caso base. Em seguida, ele retorna o resultado final retirando os quadros da pilha de chamadas.
Por exemplo, vamos calcular o fatorial de 5 usando esta função recursiva. Usaremos uma pilha de chamadas para acompanhar as chamadas de função e seus parâmetros. A tabela abaixo mostra as etapas e o estado da pilha de chamadas em cada etapa.
Passo chamada de função Pilha de chamadas Ação --- --- --- --- 1 fatorial(5) Chamada fatorial(5) 2 fatorial(5) fatorial(5) Empurre fatorial(5) para a pilha de chamadas 3 fatorial(4) fatorial(5),fatorial(4) Chame fatorial(4) e coloque-o na pilha de chamadas 4 fatorial(3) fatorial(5),fatorial(4),fatorial(3) Chame fatorial(3) e coloque-o na pilha de chamadas 5 fatorial(2) fatorial(5),fatorial(4),fatorial(3),fatorial(2) Chame fatorial(2) e coloque-o na pilha de chamadas 6 fatorial(1) fatorial(5),fatorial(4),fatorial(3),fatorial(2),fatorial(1) Chame fatorial(1) e coloque-o na pilha de chamadas 7 fatorial(0) fatorial(5),fatorial(4),fatorial(3),fatorial(2),fatorial(1),fatorial(0) Chame fatorial(0) e coloque-o na pilha de chamadas 8 retornar 1 fatorial(5),fatorial(4),fatorial(3),fatorial(2),fatorial(1) Retorne 1 e pop fatorial(0) da pilha de chamadas 9 retorna 1 * 1 = 1 fatorial(5),fatorial(4),fatorial(3),fatorial(2) Retorne 1 * 1 = 1 e pop fatorial(1) da pilha de chamadas 10retorna 2 * 1 = 2fatorial(5),fatorial(4),fatorial(3)Retorna 2 * 1 = 2 e retira fatorial(2) da pilha de chamadas 11retorno 3 * 2 = 6fatorial(5),fatorial(4)Retorno 3 * 2 = 6 e pop fatorial (3) da pilha de chamadas 12 retornar 4 * 6 = 24 fatorial(5) Retorne 4 * 6 = 24 e pop fatorial(4) da pilha de chamadas 13 retornar 5 * 24 = 120 Retorne 5 * 24 = 120 e pop fatorial(5) da pilha de chamadas O valor final retornado pela função recursiva é o resultado do fatorial de 5. Nesse caso, é 120.
retrocesso
Outra aplicação das pilhas é implementar o backtracking, que é uma técnica de explorar todas as soluções possíveis para um problema e escolher a melhor. Backtracking envolve fazer uma série de escolhas e, em seguida, desfazê-las se elas levarem a um beco sem saída ou a uma solução abaixo do ideal. Uma pilha pode ser usada para armazenar o estado atual do problema e as escolhas feitas até o momento.Quando uma escolha leva a um beco sem saída ou a uma solução abaixo do ideal, podemos abrir a pilha e voltar ao estado anterior e tentar uma escolha diferente.
Um exemplo de problema que pode ser resolvido usando backtracking é o problema das N-Queens. O problema das N-Rainhas é colocar N rainhas em um tabuleiro de xadrez N x N de modo que duas rainhas não se ataquem. Uma rainha pode atacar outra rainha se estiverem na mesma linha, coluna ou diagonal. Para resolver esse problema usando backtracking, podemos usar uma pilha para armazenar as posições das rainhas colocadas até o momento. Podemos começar colocando uma rainha na primeira linha e depois passar para a próxima linha. Para cada linha, podemos tentar todas as colunas possíveis e verificar se a posição atual é segura ou não. Se for seguro, nós o colocamos na pilha e passamos para a próxima linha. Se não for seguro, tentamos uma coluna diferente. Se chegarmos a uma linha onde nenhuma coluna é segura, desempilhamos a pilha e voltamos para a linha anterior e tentamos uma coluna diferente. Repetimos esse processo até colocarmos N rainhas no tabuleiro ou esgotarmos todas as escolhas possíveis.
Por exemplo, vamos resolver o problema das 4 Rainhas usando este método. Usaremos uma pilha para armazenar as posições das rainhas colocadas até o momento. A tabela abaixo mostra as etapas e o estado da pilha em cada etapa.
Passo Pilha Placa Ação --- --- --- --- 1 . . . .. . . .. . . .. . . . Coloque uma rainha na primeira linha e na primeira coluna 2 (0,0) Q. . .. . . .. . . .. . . . Empurre (0,0) para a pilha e mova para a segunda linha 3 (0,0) Q. . .. Q. .. . . .. . . . Tente colocar uma rainha na segunda linha e na primeira coluna 4 (0,0) Q. . .. Q. .. . Q.. . . . Tente colocar uma rainha na terceira linha e na segunda coluna 5 (0,0) Q. . .. Q.. Q. .. . . . Tente colocar uma rainha na quarta linha e na primeira coluna 6 (0,0) Q. . .. Q. .. . Q.. . Q. Verifique se a posição atual é segura ou não 7 (0,0) Q. . .. Q. .. . Q.. . Q. Não, não é seguro, pois é atacado pela rainha na primeira coluna 8 (0,0) Q. . .. Q. .. . Q.. . . P Tente colocar uma rainha na quarta linha e na segunda coluna 9 (0,0) Q. . .. Q. .. . Q.. . . P Verifique se a posição atual é segura ou não 10 (0,0) Q. . .. Q. .. . Q.. . . P Não, não é seguro, pois é atacado pela rainha na segunda coluna 11 (0,0) Q. . .. Q.. . Q.. . . . Tente colocar uma rainha na quarta linha e na terceira coluna 12 (0,0) Q. . .. Q. .. . Q.. . . . P Verifique se a posição atual é segura ou não 13 (0,0) Q. . .. Q. .. . Q.. . . . P Não, não é seguro, pois é atacado pela rainha na terceira coluna 14 (0,0) Q. . .. Q. .. . Q.. Q. . . Tente colocar uma rainha na quarta linha e na quarta coluna 15 (0,0) Q. . .. Q.. Q.. Q. . . Verifique se a posição atual é segura ou não 16 (0,0) Q. . .. Q.. Q.. Q. Não, não é seguro, pois é atacado pela rainha na primeira fila 17 (0,0) Q.. Q.. Q.. Abra a pilha e volte para a terceira linha 18 (0,0),(1,1) Q.. . Q.. . . . .. Tente colocar uma rainha na terceira linha e na terceira coluna 19 (0,0),(1,1),(2,2) Q.. . Q.. . . Q.. . . . Empurre (2,2) para a pilha e mova para a quarta linha 20 (0,0),(1,1),(2,2) Q.. . Q.. . . Q.. Q. . Tente colocar uma rainha na quarta linha e na primeira coluna 21 (0,0),(1,1),(2,2) Q.. . Q.. . . Q.. Q. . Verifique se a posição atual é segura ou não 22 (0,0),(1,1),(2,2) Q.. . Q.. . . Q.. Q. . Não, não é seguro, pois é atacado pela rainha na segunda coluna 23 (0,0),(1,1),(2,2) Q.. . Q.. . . Q.. . Q. Tente colocar uma rainha na quarta linha e na segunda coluna 24 (0,0),(1,1),(2,2) Q.. . Q.. . . Q.. . Q. Verifique se a posição atual é segura ou não 25 (0,0),(1,1),(2,2) Q.. . Q.. . . Q.. . Q. Não, não é seguro, pois é atacado pela rainha na primeira coluna 26 (0,0),(1,1),(2,2) Q.. . Q.. . . Q.. . . P Tente colocar uma rainha na quarta linha e na terceira coluna 27 (0,0),(1,1),(2,2) Q
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)
.usuário(Q)Conclusão
Neste artigo, aprendemos sobre pilhas, um tipo de estrutura de dados que segue o princípio LIFO ou FILO. Vimos como implementar uma pilha usando diferentes estruturas de dados, como arrays ou listas encadeadas. Também vimos alguns exemplos de como as pilhas podem ser usadas para resolver vários problemas, como avaliação de expressões, chamadas de função e recursão e retrocesso.
As pilhas são úteis para muitos aplicativos que requerem armazenamento e recuperação de dados em ordem inversa. Eles podem nos ajudar a simplificar problemas complexos e otimizar o desempenho de nossos programas.
perguntas frequentes
Quais são algumas vantagens e desvantagens do uso de pilhas?
Algumas vantagens de usar o princípio FILO, o que significa que o elemento que é inserido por último sai primeiro. Uma fila segue o princípio FIFO ou LILO, o que significa que o elemento que é inserido primeiro sai primeiro. Uma pilha pode ser visualizada como uma pilha de objetos, onde o topo da pilha é a única posição onde podemos acessar, inserir ou deletar um elemento. Uma fila pode ser visualizada como uma linha de objetos, onde a frente da fila é a posição onde podemos deletar um elemento e a parte de trás da fila é a posição onde podemos inserir um elemento.
Como podemos implementar uma fila usando duas pilhas?
Podemos implementar uma fila usando duas pilhas usando uma pilha para armazenar os elementos na fila e outra pilha para inverter a ordem dos elementos. Quando queremos enfileirar um elemento, simplesmente o colocamos na primeira pilha.Quando queremos desenfileirar um elemento, verificamos se a segunda pilha está vazia ou não. Se estiver vazio, retiramos todos os elementos da primeira pilha e os empurramos para a segunda pilha. Em seguida, desempilhamos e retornamos o elemento superior da segunda pilha. Se não estiver vazio, apenas desempilhamos e retornamos o elemento superior da segunda pilha.
Como podemos implementar uma pilha usando uma fila?
Podemos implementar uma pilha usando uma fila usando um truque para inverter a ordem dos elementos na fila. Quando queremos colocar um elemento na pilha, primeiro o enfileiramos na fila. Em seguida, desenfileiramos e enfileiramos todos os elementos na fila, exceto o último. Dessa forma, o último elemento passa a ser o primeiro elemento da fila, que representa o topo da pilha. Quando queremos retirar um elemento da pilha, simplesmente desenfileiramos e retornamos o primeiro elemento da fila.
0517a86e26
コメント