Estrutura de dados: pilha

Artigo composto por uma apresentação no Prezi explicando os conceitos básicos da estrutura de dados de pilha e a implementação em C++ e Python do funcionamento disponibilizado na apresentação. Os códigos mostrados possuem um link para editores online e que permite o teste da execução e aplicação de alterações.

Link para a presentação: https://prezi.com/kc8opwslaedp/?token=b0b76f4ff8c48d733687f9ae269a25cc4808ea2c9839fb30fa62cf221142a6f8

Código em C++

#include <iostream>
#define tamanho 5
using namespace std;

//define a estrutura que será a pilha
//a estrutura armazena a indicação do topo da pilha e um vetor com os itens (valores) da pilha
typedef struct{
      int topo = 0;
      int item [tamanho] ;
} PILHA;

//retorna se a pilha está vazia ou não
bool pilhaVazia(PILHA p){
    if(p.topo == 0) {
        return true;
    } else {
        return false;
    }
}

//retorna se a pilha está cheia ou não
bool pilhaCheia(PILHA p) {
	int tam = sizeof(p.item)/sizeof(int); //determina o tamanho do vetor
	
    if (p.topo < tam) {
        return false;
    } else {
        return true;
    }
}

//adiciona valor na pilha
void empilha(PILHA &p, int x){
    p.item[p.topo++]=x;
}

//remove valor da pilha
int desempilha(PILHA &p){
    return (p.item[--p.topo]) ;
}

//mostra os valores armazenados na pilha
void mostraPilha(PILHA p) {
	cout << "Valores da pilha: ";
	for (int i = 0; i < p.topo; i++) {
		cout << p.item[i] << " ";
	}
	cout << "\n";
}

//Código para testar a implementação.
int main(){
    PILHA s; //criar a pilha
    
    //Verificar que a pilha está vazia
    if(pilhaVazia(s)) {
        cout<<"A pilha está vazia."<<endl;
    } else {
        cout<<"A pilha não está vazia."<<endl;
    }
    
    //Empilha valor e verifica se a pilha está vazia
    empilha(s,10);
    if(pilhaVazia(s)) {
        cout<<"A pilha está vazia."<<endl;
    } else {
        cout<<"A pilha não está vazia."<<endl;
    }
    
    //Empilhar 3 elementos
    empilha(s,20);
    empilha(s,30);
    empilha(s,40);

	//Mostra os valores da pilha
    mostraPilha(s);
    
    //Verifica que a pilha está cheia
    if(pilhaCheia(s)) {
        cout<<"A pilha está cheia."<<endl;
    } else {
        cout<<"A pilha não está cheia."<<endl;
    }
    
    //Empilha valor e verifica se a pilha está cheia
    empilha(s,50);
    mostraPilha(s);
    if(pilhaCheia(s)) {
        cout<<"A pilha está cheia."<<endl;
    } else {
        cout<<"A pilha não está cheia."<<endl;
    }
    
    //Desempilha e mostrar o valor desempilhado
    cout<<"Valor desempilhado: "<< desempilha(s) <<endl;

	mostraPilha(s);
	
    return 0;
}

Teste esse código: http://ideone.com/e.js/E5WrEt

Um detalha importante que utilizei na implementação e que pode não funcionar está relacionado com a inicialização da variável topo dentro da struct. Alguns compiladores não permitem essa inicialização. Nesse caso será necessário adicionar a função abaixo ao código e logo após criar a pilha para essa função.

//.....

void inicializaPilha(PILHA &p) {
    p.topo = 0;
}

//.....

int main() {
    PILHA s;
    inicializaPilha(s);

//.....

Código em Python

Na implementação em Python busquei manter o mais próximo possível da implementação mostrada em C++. Em Python seria possível utilizar uma lista em vez de vetor e não ter limite de elementos na pilha.

#define a estrutura que será a pilha
#como o Python não tem struct, fiz uma classe
#a estrutura armazena a indicação do topo da pilha e um vetor com os itens (valores) da pilha
TAMANHO = 5
class PILHA:
    def __init__(self):
        self.topo = 0
        self.item = [0]*TAMANHO

#retorna se a pilha está vazia ou não
def pilhaVazia(p):
    if p.topo == 0:
        return True;
    else:
        return False;

#retorna se a pilha está cheia ou não
def pilhaCheia(p):
    tam = len(p.item) #determina o tamanho do vetor
    
    if p.topo < tam:
        return False
    else:
        return True
    
#adiciona valor na pilha
def empilha(p, x):
    p.item[p.topo] = x
    p.topo = p.topo + 1

#remove valor da pilha
def desempilha(p):
    p.topo = p.topo - 1
    return p.item[p.topo]

#mostra os valores armazenados na pilha
def mostraPilha(p):
    print "Valores da pilha: "
    for i in range(p.topo):
        print p.item[i], " ",
    print "\n"

#Código para testar a implementação
s = PILHA(); #criar a pilha
    
#Verificar que a pilha está vazia
if pilhaVazia(s):
    print "A pilha está vazia.\n"
else:
    print "A pilha não está vazia.\n"
    
#Empilha valor e verifica se a pilha está vazia
empilha(s,10)
if pilhaVazia(s):
    print "A pilha está vazia.\n"
else:
    print "A pilha não está vazia.\n"
    
#Empilhar 3 elementos
empilha(s,20)
empilha(s,30)
empilha(s,40)

#Mostra os valores da pilha
mostraPilha(s)
    
#Verifica que a pilha está cheia
if pilhaCheia(s):
    print "A pilha está cheia.\n"
else:
    print "A pilha não está cheia.\n"
    
#Empilha valor e verifica se a pilha está cheia
empilha(s,50)
mostraPilha(s)
if pilhaCheia(s):
    print "A pilha está cheia.\n"
else:
    print "A pilha não está cheia.\n"
   
#Desempilha e mostrar o valor desempilhado
print "Valor desempilhado: ", desempilha(s), "\n"
mostraPilha(s)

Teste esse código: http://www.codeskulptor.org/#user40_vN80HJDaHi_0.py