Menu

Estrutura de pilha de dados em C ++ com ilustração

stack data structure c with illustration

escrever casos de teste junit em java

Experimente Nosso Instrumento Para Eliminar Problemas

Tudo o que você precisa saber sobre Stack In C ++.

Stack é uma estrutura de dados fundamental que é usada para armazenar elementos de forma linear.

Stack segue LIFO (último a entrar, primeiro a sair) ordem ou abordagem em que as operações são realizadas. Isso significa que o elemento adicionado por último à pilha será o primeiro elemento a ser removido da pilha.

=> Visite aqui para ver toda a série de treinamento C ++ para todos.

PILHA

O que você aprenderá:

Empilhar em C ++

Uma pilha é semelhante à pilha da vida real ou uma pilha de coisas que empilhamos uma sobre a outra.

Dada a seguir é uma representação pictórica de Stack.

representação pictórica da pilha

Conforme mostrado acima, há uma pilha de pratos empilhados uns sobre os outros. Se quisermos adicionar outro item a ele, o adicionamos no topo da pilha, conforme mostrado na figura acima (lado esquerdo). Esta operação de adicionar um item à pilha é chamada de “ Empurre ”.

No lado direito, mostramos uma operação oposta, ou seja, removemos um item da pilha. Isso também é feito na mesma extremidade, ou seja, no topo da pilha. Esta operação é chamada de “ Pop ”.

Conforme mostrado na figura acima, vemos que push e pop são realizados a partir da mesma extremidade. Isso faz com que a pilha siga a ordem LIFO. A posição ou extremidade a partir da qual os itens são empurrados para dentro ou retirados para / da pilha é chamada de “ Topo da pilha ”.

Inicialmente, quando não há itens na pilha, o topo da pilha é definido como -1. Quando adicionamos um item à pilha, o topo da pilha é incrementado em 1, indicando que o item foi adicionado. Em oposição a isso, o topo da pilha diminui em 1 quando um item é retirado da pilha.

A seguir, veremos algumas das operações básicas da estrutura de dados da pilha que precisaremos ao implementar a pilha.

Operações básicas

A seguir estão as operações básicas que são suportadas pela pilha.

  • Empurre - Adiciona ou coloca um elemento na pilha.
  • pop - Remove ou retira um elemento da pilha.
  • olhadinha - Obtém o elemento superior da pilha, mas não o remove.
  • está cheio - Testa se a pilha está cheia.
  • está vazia - Testa se a pilha está vazia.

Ilustração

Ilustração da pilha

A ilustração acima mostra a seqüência de operações que são realizadas na pilha. Inicialmente, a pilha está vazia. Para uma pilha vazia, o topo da pilha é definido como -1.

Em seguida, colocamos o elemento 10 na pilha. Vemos que o topo da pilha agora aponta para o elemento 10.

Em seguida, executamos outra operação de push com o elemento 20, como resultado da qual o topo da pilha agora aponta para 20. Este estado é a terceira figura.

Agora, na última figura, realizamos uma operação pop (). Como resultado da operação pop, o elemento apontado para o topo da pilha é removido da pilha. Portanto, na figura, vemos que o elemento 20 é removido da pilha. Portanto, o topo da pilha agora aponta para 10.

Desta forma, podemos facilmente distinguir a abordagem LIFO usada por pilha.

Implementação

# 1) Usando matrizes

A seguir está a implementação C ++ da pilha usando matrizes:

#include using namespace std; #define MAX 1000 //max size for stack class Stack { int top; public: int myStack(MAX); //stack array Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //pushes element on to the stack bool Stack::push(int item) { if (top >= (MAX-1)) { cout << 'Stack Overflow!!!'; return false; } else { myStack(++top) = item; cout<

Resultado:

The Stack Push

dois

4

6

The Stack Pop:

6

4

dois

Na saída, podemos ver que os elementos são colocados na pilha em uma ordem e são retirados da pilha na ordem inversa. Isso exibe a abordagem LIFO (último a entrar, primeiro a sair) para a pilha.

Para a implementação do array da pilha acima, podemos concluir que é muito fácil de implementar, pois não há ponteiros envolvidos. Mas, ao mesmo tempo, o tamanho da pilha é estático e a pilha não pode aumentar ou diminuir dinamicamente.

A seguir, implementaremos a pilha usando matrizes na linguagem de programação Java.

class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack() = new int(MAX); boolean isEmpty() { return (top = (MAX-1)) { System.out.println('Stack Overflow'); return false; } else { myStack(++top) = item; System.out.println(item); return true; } } int pop() { if (top <0) { System.out.println('Stack Underflow'); return 0; } else { int item = myStack(top--); return item; } } } //Main class code class Main { public static void main(String args()) { Stack stack = new Stack(); System.out.println('Stack Push:'); stack.push(1); stack.push(3); stack.push(5); System.out.println('Stack Pop:'); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } }

Resultado:

Stack Push:

1

3

5

Stack Pop:

5

3

1

A lógica de implementação é a mesma que na implementação C ++. A saída mostra a técnica LIFO de empurrar para dentro e para fora dos elementos de / para a pilha.

Como já declarado, a implementação de pilha usando arrays é a implementação mais simples, mas é de natureza estática, pois não podemos aumentar ou diminuir dinamicamente a pilha.

# 2) Usando uma lista vinculada

A seguir, implementamos operações de pilha usando uma lista vinculada em C ++ e Java. Primeiro, vamos demonstrar a implementação do C ++.

#include using namespace std; // class to represent a stack node class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode *root) { return !root; } void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; } int main() { StackNode* root = NULL; cout<<'Stack Push:'<

Resultado:

Stack Push:

100

200

300

O elemento superior é 300

Stack Pop:

300

200

100

O elemento superior é -1

A seguir, apresentamos a implementação Java da pilha usando uma lista vinculada.

class LinkedListStack { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int new_data) { StackNode newNode = new StackNode(new_data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } } class Main{ public static void main(String() args) { LinkedListStack stack = new LinkedListStack(); System.out.println('Stack Push:'); stack.push(100); stack.push(200); stack.push(300); System.out.println('Top element is ' + stack.peek()); System.out.println('Stack Pop:'); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println('Top element is ' + stack.peek()); } }

Resultado:

Stack Push:

100

200

300

O elemento superior é 300

Stack Pop:

300

você pode fazer uma matriz de objetos em java

200

100

Pilha está vazia

O elemento superior é -2147483648

Acabamos de ver as implementações de C ++ e Java para uma pilha usando listas vinculadas. Representamos cada entrada da pilha como um nó da lista vinculada. A vantagem mais importante dessa implementação é que ela é dinâmica. Isso significa que podemos aumentar ou diminuir o tamanho da pilha de acordo com nossos requisitos.

Isso é diferente do caso de implementação de pilha usando matrizes em que temos que declarar o tamanho de antemão e não podemos alterá-lo dinamicamente.

A desvantagem dessa implementação é que, como usamos ponteiros em todos os lugares, ele ocupa muito espaço quando comparado à implementação de array.

Aplicações de Stack

Vamos discutir algumas das aplicações da estrutura de dados da pilha. A estrutura de dados da pilha é usada em uma variedade de aplicativos na programação de software, principalmente por causa de sua simplicidade e facilidade de implementação.

Descreveremos resumidamente algumas das aplicações da pilha abaixo:

# 1) Expressões Infix para Postfix

Qualquer expressão aritmética geral é da forma operando1 operando OP 2 .

Com base na posição do operador OP, temos os seguintes tipos de expressões:

  • Infixo - A forma geral de expressão do infixo é “ operando1 operando OP 2 ”. Esta é a forma básica da expressão e usamos em matemática o tempo todo.
  • Prefixo - Quando um operador é colocado antes dos operandos, é uma expressão de prefixo. A forma geral de expressão do infixo é “ OP operand1 operand2 ”.
  • Postfix - Em expressões pós-fixadas, os operandos são escritos primeiro, seguidos pelo operador. Possui a forma “operando1 operando2 OP”.

Considere a expressão “a + b * c ' . O compilador verifica a expressão da esquerda para a direita ou da direita para a esquerda. Cuidando da precedência e associatividade do operador, ele primeiro fará a varredura da expressão para avaliar a expressão b * c. Em seguida, ele terá que examinar novamente a expressão para adicionar o resultado de b * c a a.

À medida que as expressões ficam mais e mais complexas, esse tipo de abordagem de escanear repetidamente a expressão se torna ineficiente.

Para superar essa ineficiência, convertemos a expressão em postfix ou prefixo de forma que possam ser facilmente avaliados usando uma estrutura de dados em pilha.

# 2) Análise / Avaliação de Expressão

Usando pilha, também podemos realizar a avaliação da expressão real. Nesse caso, a expressão é varrida da esquerda para a direita e os operandos são colocados na pilha.

Sempre que um operador é encontrado, os operandos são exibidos e a operação é executada. O resultado da operação é novamente colocado na pilha. Dessa forma, a expressão é avaliada usando pilha e o resultado final da expressão geralmente é o topo atual da pilha.

# 3) Traversals de árvores

A estrutura de dados em árvore pode ser percorrida para visitar cada nó de várias maneiras e dependendo de quando o nó raiz que temos é visitado.

  • inOrder traversal
  • pré-encomenda Traversal
  • postOrder traversal

Para percorrer a árvore de forma eficiente, usamos a estrutura de dados da pilha para empurrar nós intermediários na pilha para que possamos manter a ordem de travessia.

# 4) Algoritmos de classificação

Algoritmos de classificação como quicksort podem se tornar mais eficientes usando as estruturas de dados da pilha.

# 5) Torres de Hanói

Este é um problema clássico envolvendo n número de discos e três torres e o problema envolve mover os discos de uma torre para outra com a terceira torre usada como intermediária.

Este problema pode ser resolvido com eficiência usando a pilha conforme empurramos os discos para serem movidos para a pilha, uma vez que a pilha basicamente age como uma torre usada para mover os discos.

Conclusão

A pilha é a estrutura de dados mais simples e mais fácil de implementar como um programa. Ele usou a abordagem LIFO (último a entrar, primeiro a sair), o que significa que o elemento inserido por último é o que é removido primeiro. Isso ocorre porque a pilha usa apenas uma extremidade para adicionar (empurrar) e remover (pop) elementos.

A estrutura de dados da pilha tem muitos usos na programação de software. O destaque entre eles são as avaliações de expressão. A avaliação da expressão também inclui a conversão da expressão de infixo em pós-fixo ou prefixo. Também envolve a avaliação da expressão para produzir o resultado final.

Neste tutorial, vimos a ilustração e a implementação da pilha, bem como suas várias operações.

Em nosso próximo tutorial, aprenderemos sobre a estrutura de dados da fila em detalhes.

=> Visite aqui para obter o curso C ++ completo com especialistas.

Leitura recomendada

^