Implementação de uma pilha – struct array C++

Uma pilha é uma estrutura de dados que implementa a filosofia LIFO(Last In, First Out), ou seja, o último item a ser inserido na pilha é o primeiro a poder ser retirado, pois é o que se encontra por “cima”.

Uma analogia que pode ser feita consiste em pensar em termos de uma pilha de livros.

Se apenas conseguir manipular um livro de cada vez, como é que faço para obter o livro de baixo?

Sim, a resposta é ir desempilhando os livros de cima, um a um, até o livro pretendido ficar acessível.

São muitas as formas de implementação de pilhas e nas mais variadas linguagens de programação.

A que aqui vou abordar implementa uma pilha sobre uma estrutura com dois membros, um dois quais é um array que irá armazenar a pilha propriamente dita.

topo: É um inteiro que me indica a posição do topo da pilha. O valor -1 significa que a pilha está vazia.

item: É um array de inteiros de tamanho determinado por #define tamanho 5.

A imagem seguinte tenta ilustrar as operações que foram executadas na função main.

Por questões de simplificação as funções empilhar e desempilhar não efectuam por si só o teste às situações “pilha vazia” e “pilha cheia”, pelo que deverão ser invocadas em conjunto com as funções aqui disponibilizadas para esse efeito.

O que quero eu dizer?

  • Só se pode empilhar numa pilha que não está cheia.
  • Só se pode desempilhar numa pilha que não está vazia.

Código fonte:

#include <iostream>
#define tamanho 5
using namespace std;
typedef struct{
      int topo ;
      int item [tamanho] ;
}PILHA;
void iniciaPilha (PILHA &p) {
     p.topo = -1 ;
}
bool pilhaVazia(PILHA p){
	if(p.topo == -1 )
		return true;
	else
		return false;
}
bool pilhaCheia(PILHA p){
	if (p.topo == tamanho-1)
		return true;
	else
		return false;
}
void empilha(PILHA &p, int x){
	p.item[++p.topo]=x;
}
int desempilha(PILHA &p){
	return (p.item[p.topo--]) ;
}
//O mais importante já passou.
//Este código agora é só para testar.
int main(){
	PILHA s ;
	//criar a pilha
	iniciaPilha (s);
	//Verificar que a pilha está vazia
	if(pilhaVazia(s))
		cout<<"A pilha está vazia."<<endl;
	else
		cout<<"A pilha não está vazia."<<endl;
	//empilhar três elementos
	empilha(s,12);
	empilha(s,33);
	empilha(s,7);
	empilha(s,11);
	//Verificar que a pilha está cheia
	if(pilhaCheia(s))
		cout<<"A pilha está cheia."<<endl;
	else
		cout<<"A pilha não está cheia.\n"<<endl;
	//desempilhar e mostrar um elemento
	cout<<"Item desempilhado: "<<desempilha(s)<<endl;
	//terminar

	return 0;
}
Anúncios

8 thoughts on “Implementação de uma pilha – struct array C++

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s