Pilhas (Stacks) in C++: Spezifikation, dynamische und statische Implementierung

Spezifikation der Pilhas (Stapel) der Inteiros

Typ: C++
Geschlecht: Pilha

Operações Construtoras

• Nova: Pilha → Pilha;
• Sobrepõe / ACR: int × Pilha → Pilha;

Acessórios

• Topo: Pilha → int;
• Remove: Pilha → Pilha;
• Vazia: Pilha → bool;
• Inverte: Pilha → Pilha;
• Menor: Pilha → int;
• Retiramenor: Pilha → Pilha;
• Junta: Pilha × Pilha → Pilha;
• Ordena: Pilha → Pilha;

Axiome

∀ P, P1, P2 ∈ Pilha, ∀ I, I1, I2 ∈ int:

• topo(ACR(nova, I)) = nova;
• topo(ACR(P, I)) = P;
• mol(ACR(nova, I)) = I;
• mol(ACR(P, I)) = I;
• vazia(nova) = true;
• vazia(ACR(P, I)) = false;
• menor(ACR(nova, I)) = I;
• menor(ACR(ACR(P, I1), I2)) = I1 < I2 ? menor(ACR(P, I1)) : ...;
• retiramenor(ACR(nova, I1)) = nova;
• retiramenor(ACR(ACR(P, I1), I2)) = menor(ACR(P, I1)) < I2 ? ACR(retiramenor(ACR(P, I1)), I2) : ACR(P, I1);
• junta(nova, P) = P;
• junta(P1, ACR(P2, I)) = ACR(junta(P1, P2), I);
• ordena(ACR(nova, I)) = ACR(nova, I);
• ordena(ACR(P, I)) = junta(ACR(nova, menor(P, I)), ordena(retiramenor(ACR(nova, I))));
• inverte(ACR(nova, I)) = ACR(nova, I);
• inverte(ACR(P, I)) = junta(ACR(nova, I), inverte(P));

Pré-Condições

∀ P ∈ Pilha:

• remove requer !vazia(P);
• topo requer !vazia(P);
• inverte requer !vazia(P);
• menor requer !vazia(P);
• retiramenor requer !vazia(P);

Implementação Dinâmica

class Pilha {
private:
    struct NO {
        int val;
        NO *s;
    };
    NO *top;
    int item_not_found;
public:
    void nova();
    void sobrepoe(int n);
    void remove();
    int topo();
    bool vazia();
    void retiramenor(Pilha p);
    void junta(Pilha p, Pilha r);
};

void Pilha::nova() {
    top = NULL;
}

void Pilha::sobrepoe(int n) {
    NO *aux = new NO();
    aux->val = n;
    aux->s = top;
    top = aux;
}

void Pilha::remove() {
    NO *aux = NULL;
    if (top != NULL) {
        aux = top;
        top = top->s;
        delete aux;
    } else {
        cout << "Erro: Pilha vazia!" << endl;
    }
}

int Pilha::topo() {
    if (top != NULL)
        return top->val;
    else {
        cout << "Erro: Pilha vazia!" << endl;
        return item_not_found;
    }
}

bool Pilha::vazia() {
    return top == NULL;
}

void Pilha::retiramenor(Pilha p) {
    if (p.top != NULL) {
        NO *aux = p.top, *prev = NULL, *posmenor = p.top, *antmenor = NULL;
        while (aux->s != NULL) {
            if (aux->s->val < posmenor->val) {
                antmenor = aux;
                posmenor = aux->s;
            }
            aux = aux->s;
        }
        if (antmenor == NULL)
            p.top = posmenor->s;
        else
            antmenor->s = posmenor->s;
        delete posmenor;
    } else {
        cout << "Erro-retiramenor: Pilha vazia!" << endl;
    }
}

void Pilha::junta(Pilha p, Pilha r) {
    Pilha x;
    x.nova();
    NO *aux = p.top;
    while (aux != NULL) {
        x.sobrepoe(aux->val);
        aux = aux->s;
    }
    aux = r.top;
    while (aux != NULL) {
        x.sobrepoe(aux->val);
        aux = aux->s;
    }
}

Statische Implementierung

class Pilha {
private:
    static const int lim = 100;
    int vet[lim];
    int es;
    int item_not_found;
public:
    void nova();
    void sobrepoe(int n);
    void remove();
    int topo();
    bool vazia();
    void retiramenor(Pilha p);
    void junta(Pilha p, Pilha r);
};

void Pilha::nova() {
    es = -1;
}

void Pilha::sobrepoe(int n) {
    if (es != lim - 1)
        vet[++es] = n;
    else
        cout << "Erro-sobrepoe: Pilha cheia!\n";
}

void Pilha::remove() {
    if (es != -1)
        es--;
    else
        cout << "Erro-remove: Pilha vazia!\n";
}

int Pilha::topo() {
    if (es != -1)
        return vet[es];
    else {
        cout << "Erro: Pilha vazia!\n";
        return item_not_found;
    }
}

bool Pilha::vazia() {
    return es == -1;
}

void Pilha::retiramenor(Pilha p) {
    int menor = 0;
    if (es != -1) {
        for (int i = 1; i <= es; i++)
            if (vet[i] < vet[menor])
                menor = i;
        for (int j = menor; j < es; j++)
            vet[j] = vet[j + 1];
        es--;
    }
}