Pilhas - Remove (C++)

N0vato · 18 de junho de 2011

Olá gente, então, eu queria saber por que nessa implementação de pilha com vetor em C++ a função Pop faz uma referência a um inteiro (que é passada para essa função) receber um o elemento do topo da Stack. Eu entendi o teste para saber se a Stack está vazia e o if e o else e o decremento da variável que indica a "posição corrente" da pilha mas, não tenho nem noção por que que TopElem recebe o último elemento da pilha, pelo que eu entendi de pilha, Pop não era nem para receber parâmetro, quanto mais passar o valor do último elemento da pilha para uma variável recebida como parâmetro.

#ifndef INTSTAK_H 
#define INTSTAK_H
#include <iostream>
class intstack
{
protected:
  int StackSize;
  int *Element;
  int StackPointer;
public:
  bool Empty() const;
  bool Full() const;
  intstack(int stacksize = 10);
  virtual ~intstack();
  virtual bool Pop(int& TopElem);
  virtual bool Push(const int& NewElem);
};
#endif

esse foi o .h, onde StackSize é o tamanho ta pilha, StackPointer indica o elemento corrente (posição do último elemento da pilha) e Element um ponteiro que por alocação dinâmica "se torna" um vetor. Agora o .cpp

#include "intstack.h"
using namespace std;

intstack::intstack(int stacksize) :
  StackSize(stacksize),
  Element(new int[stacksize]),
  StackPointer(-1)
{}

intstack::~intstack()
{
  delete [] Element;
}
bool intstack::Empty() const
{
  return StackPointer == -1 ? true : false;
}

bool intstack::Full() const
{
  return StackPointer == StackSize - 1 ? true: false;
}

bool intstack::Pop(int& TopElem)
{
  if (!Empty()) {
    TopElem = Element[StackPointer--];
    return true;
  } else {
    cout << "Stack empty: pop failed.\n";
    return false;
  }
}

bool intstack::Push(const int& NewElem)
{
  if (!Full()) {
    Element[++StackPointer] = NewElem;
    return true;
  } else {
    cout << "Stack full: push failed.\n";
    return false;
  }
}

eu ia passar apenas a Pop mas, para ficar mais claro, passei tudo logo.

eu esqueci de dizer, tipo, esse programa tem alguns erros do tipo nome de variável coisa e tal, corrigindo os detalhes, funciona, mas o que eu queria entender é conceitualmente por que está escrito isso:

TopElem = Element[stackPointer--];

XP_hunter · 18 de junho de 2011

Sobre o parâmetro do método pop, ele é necessário para armazenar o valor removido, segundo essa implementação. Essa operação não é realmente necessária, tanto que na classe Stack da STL ela não existe.

Sobre o recuo do StackPointer, acontece que quando um elemento é removido, ele não é realmente apagado da memória. O ponteiro do topo recua, diminuindo o tamanho da pilha, e quando isso acontece não é possível saber se os elementos "acima" do topo são elementos que foram removidos ou lixo da memória. Na verdade, não é necessário saber, pois caso a pilha volte a ocupar esse espaço da memória, através de inserções, o elemento será reescrito de qualquer jeito.

Espero ter ajudado.

ZaZ