Pilha em C++ STL com exemplo

O que é std::stack?

Uma pilha é uma estrutura de dados que opera com base na técnica LIFO (Last In First Out). O std::stack permite que elementos sejam adicionados e removidos apenas de uma extremidade.

A classe std::stack é um adaptador de contêiner. Os objetos contêiner contêm dados de um tipo de dados semelhante. Você pode criar uma pilha a partir de vários contêineres de sequência. Se nenhum contêiner for fornecido, o deque container será usado por padrão. Os adaptadores de contêiner não oferecem suporte a iteradores, portanto, não podem ser usados ​​para manipular dados.

Sintaxe de pilha

Para criar uma pilha, devemos incluir o arquivo de cabeçalho em nosso código. Em seguida, usamos esta sintaxe para definir std::stack:

template <class Type, class Container = deque<Type> > class stack;
  • Formato – é o tipo de elemento contido em std::stack. Pode ser qualquer tipo C++ válido ou até mesmo um tipo definido pelo usuário.
  • Recipiente – é o tipo do objeto contêiner subjacente.

Tipos de membros

Aqui estão os tipos de membros da pilha:

  • value_type- O primeiro parâmetro do modelo, T. Ele denota os tipos de elementos.
  • container_type- O segundo parâmetro do modelo, Container. Denota o tipo de contêiner subjacente.
  • size_type- Tipo integral não assinado.

Operações na pilha

A C + + pilha suporta o seguintewing operações básicas:

  • push – Adiciona/empurra um item para a pilha.
  • pop – Remove/retira um item da pilha.
  • peek – Retorna o item do topo da pilha sem removê-lo.
  • isFull – Verifica se uma pilha está cheia.
  • isEmpty – Verifica se uma pilha está vazia.

Implementação de pilha

Implementação de pilha

Passo 1) Inicialmente temos uma pilha vazia. O topo de uma pilha vazia é definido como -1.

Passo 2) A seguir, colocamos o elemento 5 na pilha. O topo da pilha apontará para o elemento 5.

Passo 3) A seguir, colocamos o elemento 50 na pilha. O topo da pilha muda e aponta para o elemento 50.

Passo 4) Em seguida, executamos uma operação pop, removendo o elemento superior da pilha. O elemento 50 é retirado da pilha. O topo da pilha agora aponta para o elemento 5.

push() e pop()

As funções stack::push() adicionam um novo item ao topo da pilha. O tamanho da pilha é aumentado em 1 após a inserção. A função assume esta sintaxe:

stack.push(value)

O valor é o item a ser inserido na pilha.

A função stack::pop() remove o elemento superior da pilha. Este é o item mais novo da pilha. O tamanho da pilha é reduzido em 1 após a remoção. Aqui está a sintaxe da função:

stack.pop()

A função não aceita parâmetros.

1 exemplo:

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);
	
         st.pop();
	st.pop();

	while (!st.empty()) {
		cout << ' ' << st.top();
		st.pop();
	}
}

Saída:

push() e pop()

Aqui está uma captura de tela do código:

push() e pop()

Explicação do código:

  1. Inclua o arquivo de cabeçalho iostream em nosso código para usar suas funções.
  2. Inclua o arquivo de cabeçalho da pilha em nosso código para usar suas funções.
  3. Inclua o namespace std em nosso código para usar suas classes sem chamá-lo.
  4. Chame a função main(). A lógica do programa deve ser adicionada nesta função.
  5. Crie uma pilha st para armazenar valores inteiros.
  6. Use a função push() para inserir o valor 10 na pilha.
  7. Use a função push() para inserir o valor 20 na pilha.
  8. Use a função push() para inserir o valor 30 na pilha.
  9. Use a função push() para inserir o valor 40 na pilha.
  10. Use a função pop() para remover o elemento superior da pilha, ou seja, 40. O elemento superior agora se torna 30.
  11. Use a função pop() para remover o elemento superior da pilha, ou seja, 30. O elemento superior agora se torna 20.
  12. Use um loop while e uma função vazia() para verificar se a pilha NÃO está vazia. O ! é o operador NOT.
  13. Imprimindo o conteúdo atual da pilha no console.
  14. Chame a função pop() na pilha.
  15. Fim do corpo do loop while.
  16. Fim do corpo da função main().

vazio(), tamanho(), topo()

As pilhas possuem funções integradas que você pode usar para brincar com a pilha e seus valores. Esses incluem:

  • vazio()- verifica se uma pilha está vazia ou não.
  • size()- retorna o tamanho da pilha, ou seja, o número de elementos em uma pilha.
  • top() - acessa o elemento da pilha no topo.

2 exemplo:

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> st;
	st.push(32);
	st.push(21);
	st.push(39);
	st.push(89);
	st.push(25);

	cout << "The stack st is: ";
	createStack(st);
	cout << "\n st.size() : " << st.size();
	cout << "\n st.top() : " << st.top();
	cout << "\n st.pop() : ";
	st.pop();
	createStack(st);
	return 0;
}

Saída:

vazio(),tamanho(),topo()

Aqui está uma captura de tela do código:

vazio(),tamanho(),topo()

Explicação do código:

  1. Inclua o arquivo de cabeçalho iostream em nosso código para usar suas funções.
  2. Inclua o arquivo de cabeçalho da pilha em nosso código para usar suas funções.
  3. Inclua o namespace std em nosso programa para usar suas classes sem chamá-lo.
  4. Crie a função createStack que podemos usar para criar a pilha mystack. A pilha conterá um conjunto de inteiros.
  5. O início do corpo da função createStack.
  6. Crie uma instância do tipo de dados mystack e dê a ela o nome ms.
  7. Use o loop while e a função vazia() para verificar se a pilha está vazia.
  8. O início do corpo do loop while.
  9. Use a função top() armazenada no topo da pilha. O caractere \t criará uma nova aba.
  10. Use a função pop() para excluir o elemento no topo da pilha.
  11. Fim do corpo do loop while.
  12. Imprima uma linha em branco no console.
  13. Fim do corpo da função createStack.
  14. Chame a função main(). A lógica do programa deve ser adicionada ao corpo da função main().
  15. O início do corpo da função main().
  16. Crie um objeto de pilha st.
  17. Use a função push() para inserir o elemento 32 na pilha.
  18. Use a função push() para inserir o elemento 21 na pilha.
  19. Use a função push() para inserir o elemento 39 na pilha.
  20. Use a função push() para inserir o elemento 89 na pilha.
  21. Use a função push() para inserir o elemento 25 na pilha.
  22. Imprima algum texto no console.
  23. Chame a função createStack para executar as operações de inserção acima na pilha.
  24. Imprima o tamanho da pilha no console junto com outro texto.
  25. Imprima o elemento no topo da pilha no console.
  26. Imprima algum texto no console.
  27. Exclua o elemento no topo da pilha. Em seguida, ele retornará os elementos restantes na pilha.
  28. Chame a função createStack para executar as operações acima.
  29. O programa deve retornar o valor após a conclusão bem-sucedida.
  30. Fim do corpo da função main().

emplace() e swap()

Estas são outras funções de pilha integradas:

  • emplace()- constrói e insere um novo elemento no topo da pilha.
  • swap()- troca o conteúdo da pilha com o conteúdo de outra pilha.

3 exemplo:

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> st2;

	st1.emplace(12);
	st1.emplace(19);

	st2.emplace(20);
	st2.emplace(23);

	st1.swap(st2);

	cout << "st1 = ";
	while (!st1.empty()) {
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl << "st2 = ";
	while (!st2.empty()) {
		cout << st2.top() << " ";
		st2.pop();
	}
}

Saída:

substituir()& trocar()

Aqui está uma captura de tela do código:

substituir()& trocar()

Explicação do código:

  1. Inclua o arquivo de cabeçalho iostream em nosso código para usar suas funções.
  2. Inclua o arquivo de cabeçalho da pilha em nosso código para usar suas funções.
  3. Inclua o arquivo de cabeçalho cstdlib em nosso código para usar suas funções.
  4. Inclua o namespace std em nosso código para usar suas classes sem chamá-lo.
  5. Chame a função main(). A lógica do programa será adicionada ao corpo desta função.
  6. Declare uma pilha chamada st1 para armazenar valores inteiros.
  7. Declare uma pilha chamada st2 para armazenar valores inteiros.
  8. Use a função emplace() para inserir o inteiro 12 na pilha chamada st1.
  9. Use a função emplace() para inserir o inteiro 19 na pilha chamada st1.
  10. Use a função emplace() para inserir o inteiro 20 na pilha chamada st2.
  11. Use a função emplace() para inserir o inteiro 23 na pilha chamada st2.
  12. Use a função swap() para trocar o conteúdo das duas pilhas, st1 e st2. O conteúdo da pilha st1 deve ser movido para a pilha st2. O conteúdo da pilha st2 deve ser movido para a pilha st1.
  13. Imprima algum texto no console.
  14. Use a instrução while e a função vazia() para verificar se a pilha st1 não está vazia.
  15. Imprima o conteúdo da pilha st1 no console. O ” ” adiciona espaço entre os elementos da pilha ao imprimi-los no console.
  16. Execute a função pop() na pilha st1 para remover o elemento superior.
  17. Fim do corpo da instrução while.
  18. Imprima algum texto no console. O endl é uma palavra-chave C++ para linha final. Ele move o cursor do mouse para a próxima linha para começar a imprimir a partir daí.
  19. Use a instrução while e a função vazia() para verificar se a pilha st2 não está vazia.
  20. Imprima o conteúdo da pilha st2 no console. O ” ” adiciona espaço entre os elementos da pilha ao imprimi-los no console.
  21. Execute a função pop() na pilha st2 para remover o elemento superior.
  22. Fim do corpo da instrução while.
  23. Fim do corpo da função main().

Pilha em STL

A STL (Standard Template Library) vem com classes de modelo que fornecem estruturas de dados C++ comuns. Portanto, uma pilha também pode ser implementada em STL. Simplesmente incluímos esta biblioteca em nosso código e a usamos para definir uma pilha.

stack<T> st; 

A sintaxe acima declares uma pilha st para elementos do tipo de dados T.

4 exemplo:

#include <iostream>      
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st;
	st.push(12);
	st.push(19);
	st.push(20);
	cout << st.top();   
	cout << st.size();  
}

Saída:

Pilha em STL

Aqui está uma captura de tela do código:

Pilha em STL

Explicação do código:

  1. Inclua o arquivo de cabeçalho iostream em nosso código para usar suas funções.
  2. Inclua o arquivo de cabeçalho da pilha em nosso código para usar suas funções.
  3. Inclua o arquivo de cabeçalho cstdlib em nosso código para usar suas funções.
  4. Inclua o namespace std em nosso código para usar suas classes sem chamá-lo.
  5. Chame a função main(). A lógica do programa deve ser adicionada ao corpo desta função.
  6. Declare uma pilha st para armazenar dados inteiros.
  7. Adicione o elemento 12 à pilha.
  8. Adicione o elemento 19 à pilha.
  9. Adicione o elemento 20 à pilha.
  10. Imprima o elemento no topo da pilha no console.
  11. Imprima o tamanho da pilha no console.
  12. Fim do corpo da função main().

Resumo

  • Uma pilha é uma estrutura de dados que opera com base na técnica LIFO (Last In first Out).
  • O std::stack permite apenas que itens sejam adicionados e removidos de uma extremidade.
  • A classe std::stack é um adaptador de contêiner, contendo itens de tipo de dados semelhante.
  • Uma pilha pode ser criada a partir de vários contêineres de sequência.
  • Se você não fornecer um contêiner, o contêiner deque será usado por padrão.
  • A função push() serve para inserir itens na pilha.
  • A função pop() serve para remover o item superior da etapa.
  • A função vazia() serve para verificar se uma pilha está vazia ou não.