Estruturas de Dados — Pilha
Na programação, temos que trabalhar com muitos e muitos dados. Portanto, precisamos armazenar e organizar os dados de maneira eficiente. É aqui que as estruturas de dados são úteis. Podemos usar estruturas de dados para armazenar, organizar, processar e recuperar dados. As estruturas de dados podem ser divididas em 2 categorias, dependendo de como os dados são organizados.
Neste artigo, falarei sobre estruturas lineares ( pilhas ). Em comparação com as estruturas não lineares, os conceitos por trás das estruturas lineares são relativamente mais fáceis de entender. Alguns exemplos dessas estruturas lineares são Stack, Queues, Deques e Lists. Passaremos por cada uma dessas estruturas de dados, uma por uma. Essas estruturas lineares podem ser consideradas como tendo 2 extremidades. (frente e traseira | esquerda e direita | superior e inferior) Algumas estruturas lineares permitem a inserção ou remoção de elementos em apenas uma extremidade, enquanto algumas estruturas permitem isso em qualquer uma das extremidades.
- Pilhas
- Então, basicamente, uma pilha é uma coleção ordenada de elementos onde a inserção e a remoção de itens ocorrem na mesma extremidade. Essa extremidade é comumente conhecida como “Top”. Além disso, a extremidade oposta ao topo é conhecida como “Bottom”
- Além disso, os itens mais novos estão próximos ao topo, enquanto os mais antigos estão próximos ao fundo. Portanto a ordem de retirada dos itens da pilha será a inversa da ordem de inserção dos itens na pilha.
- Agora que temos um bom entendimento do comportamento de uma pilha, vamos dar uma olhada em algumas operações importantes relacionadas à estrutura de dados da pilha.
- push (elemento) — O método push é usado para inserir um item no topo da pilha.
- pop ()- O método pop é usado para remover o topo — a maioria dos itens da pilha
- peek () — O método Peek é usado para ver o item atual no topo da pilha.
- size () — Retorna o número de itens que estão presentes na pilha
- is_empty () — Este método é útil para verificar se a pilha está vazia ou não
- Observe que aqui o final da lista é considerado o topo da pilha. (Complexidade de tempo — O(1)) Podemos considerar o início da lista como o topo da pilha, porém, isso não seria muito eficiente, pois a complexidade de tempo seria O(n) quando empurramos ou retiramos itens.
- Quando consideramos o final da lista como o topo da pilha
- Agora que sabemos como implementar uma pilha, vamos agora dar uma olhada em alguns cenários onde o uso da estrutura de dados da pilha se torna vital.
- Conversões do sistema numérico
- Em primeiro lugar, vamos ver como podemos converter um número decimal em binário usando uma pilha.
- Agora vamos estender o algoritmo acima para converter um número decimal em qualquer sistema numérico entre 2 e 16.
- No primeiro estágio deste problema, considerarei apenas um tipo de parênteses, digamos (). O que precisamos verificar é se o conjunto de parênteses está balanceado ou não. Se equilibrado, devemos retornar true, caso contrário, false.
- ( ) — equilibrado | ( ( ) ) — equilibrado | ( ( ( ) ( ) ) ) — equilibrado
- ( ( ) não balanceado | ( ) ( ) ( — não balanceado | ( ( ( ) ) ( ) — não balanceado
- ( [ ] ) — equilibrado | ( ( ) { } ) — equilibrado | ( ( [ { } [ ] ] ) ) — equilibrado
- ( ( ) não balanceado | ( ) { } ]— não balanceado | ( ( { } [ [ ) — não balanceado
- Notação infixa — Nesta notação, o operador é colocado entre os operandos. (<operando> <operador> <operando>)
- Se a expressão consistir em apenas um operador (ex: 2 + 3, 4 * 6) podemos resolver a expressão imediatamente. No entanto, se a expressão tiver mais de um operador, não poderemos resolvê-la diretamente devido à ambigüidade da expressão. Considere esta expressão 1 + 4 * 5. Se fizermos a adição primeiro, obtemos a resposta como [ ( 1 + 4 ) * 5 ] = 25 e se fizermos a multiplicação primeiro, obtemos a resposta como [1 + (4 * 5 )] = 21. Como você pode ver, há alguma ambigüidade nessa notação. Portanto, para resolver isso, usamos algo chamado “precedência do operador”. De acordo com a precedência do operador, a multiplicação deve ser feita antes da adição. Portanto, a resposta correta deve ser 21, não 25.
- Basicamente, para resolver uma expressão que está escrita em notação infixa temos que seguir um conjunto de regras, assim como também precisamos adicionar parênteses. Portanto, essa notação pode ocupar mais memória durante a resolução. Então, para superar esses desafios, os cientistas criaram duas outras notações, prefixo e posfixo.
- Na notação prefixada, o operador é colocado antes dos operandos, (<operador><operando> <operando>), enquanto na notação pós-fixada o operador é colocado após os operandos. (<operando> <operando><operador>)
- Em comparação com a notação infixa, as outras duas notações são bastante difíceis para um ser humano ler e entender. No entanto, como essas duas notações não possuem símbolos adicionais, como colchetes, e não contêm nenhuma ambigüidade, as expressões escritas nesses 2 formatos podem ser facilmente lidas por computadores.
- Avaliando uma expressão pós-fixada: Quando tivermos que avaliar uma expressão pós-fixada, devemos começar a varredura da esquerda até encontrar um operador. Uma vez que encontramos um operador, temos que realizar a operação algébrica relevante nos primeiros 2 operandos à esquerda do operador.
- Em primeiro lugar, precisamos remover todos os espaços em nossa entrada. Portanto, precisamos usar o método split. Então precisamos escanear nossa expressão da esquerda para a direita. Se encontrarmos um número, temos que colocá-lo na pilha. Se encontrarmos um operador, teremos que remover 2 dos itens mais altos de nossa pilha. Então temos que chamar nossa função auxiliar para fazer a operação aritmética. Depois disso, estaremos colocando o resultado na pilha. Assim que terminarmos a varredura, retornaremos o que resta em nossa pilha, que é a resposta para a expressão pós-fixada avaliada.
- Agora vamos ver como podemos converter uma expressão no formato infix para postfix usando Python.
Quase todas as linguagens de programação usam parênteses em sua sintaxe. Portanto, se não usarmos os parênteses de maneira balanceada, pode ocorrer um erro de sintaxe.
3. Inverta uma string usando uma pilha
4. Infixo | Notação pós-fixada e prefixada
Na ciência da computação, temos que lidar com muitas expressões aritméticas. Uma expressão consiste em operadores (+, -, *, / etc) operandos (A, B, c, d, 1, 2,… ) e símbolos como parênteses.





































![O que é uma lista vinculada, afinal? [Parte 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)