Problem z dynamicznym stosem w c++

Question

Witam, mam problem z utworzeniem stosu który przechowuje elementy w dynamicznej tabeli.
Jest to zadanie z książki Język c++ szkoła programowania wydanie VI dokłaknie zadanie 4 ze strony 620.
Treść:

Dany jest wariant klasy Stack z listingu 10.10:
 

// stack.h -- definicja klasy stosu (wg ADT)
#ifndef STACK_H_
#define STACK_H_

typedef unsigned long Item;

class Stack
{
    private:
        enum { MAX = 10};    // stała zasięgu klasy
        Item * pitems;     // przechowuje elementy stosu
        int size;
        int top;             // indeks szczytowego elementu stosu
    public:
        Stack(int n = MAX);
        Stack(const Stack & s);
        ~Stack();
        bool isempty() const;
        bool isfull() const;
        // push() zwraca false, jeśli stos jest już pełen (true w pozostałych przypadkach)
        bool push(const Item & item);    // odkłada element na stos
        // pop() zwraca false, jeśli stos jest już pusty (true w pozostałych przypadkach)
        bool pop(Item & item);           // zdejmuje element ze stosu
        Stack & operator=(const Stack & st);

};
#endif

Z zadeklarowanych składowych prywatnych wynika, że klasa wykorzystuje do przechowywania elementów stosu przydzielaną dynamicznie tablicę. Dostosuj implementacje metod klasy do nowej reprezentacji danych i napisz program który będzie demonstrował działanie wszystkich metod, w tym metod konstruktora kopiującego i operatora przypisania.

Oto moje niestety niedziałające rozwiązanie:

// stack.cpp -- metody klasy stosu
#include "stack.h"
#include <iostream>
Stack::Stack(int n)            // tworzy pusty stos
{
    size = n;
    top = 0;
    pitems = nullptr;
}

Stack::Stack(const Stack & s)
{
    pitems = new Item [s.top+1];
    for (int i = 0; i < sizeof(s.pitems) / sizeof(Item); ++i)
        pitems[i] = s.pitems[i];
    top = s.top + 1;
}

Stack::~Stack()
{
    delete [] pitems;
}

bool Stack::isempty() const
{
    return top == 0;
}

bool Stack::isfull() const
{
    return top == MAX;
}

bool Stack::push(const Item & item)
{
    if (top < size)
    {
        Item temp[top+1];
        for(int i = 0; i < top; ++i)
        {
            temp[i] = pitems[i];
        }
        delete [] pitems;
        pitems = new Item[top + 1];
        for(int i = 0; i < top; ++i)
        {
            pitems[i] = temp[i];
        }
        ++top;
        std::cout << top;
        pitems[top] = item;
        return true;
    }
    else
        return false;
}

bool Stack::pop(Item & item)
{
    if (top > 0)
    {
        item = pitems[top];
        Item temp[top];
        for(int i = 0; i < top; ++i)
        {
            temp[i] = pitems[i];
        }
        delete [] pitems;
        --top;
        pitems = new Item[top];
        for (int i = 0; i < top; ++i)
            pitems[i] = temp[i+1];
        return true;
    }
    else
    {
        delete [] pitems;
        return false;
    }
}

Stack & Stack::operator=(const Stack & s)
{
    if(this == &s)
        return *this;
    delete [] pitems;
    pitems = new Item [s.top+1];
    for (int i = 0; i < sizeof(s.pitems) / sizeof(Item); ++i)
        pitems[i] = s.pitems[i];
    top = s.top + 1;
    return *this;
}

#include <iostream>
#include "stack.h"

using namespace std;

int main()
{
    cout << "elo";
    Stack example;
    for (int i = 0; i < 10; ++i)
    {
        cout << example.push(i);
    }
    for (unsigned long item = 0; item < 10; ++item)
    {
        cout << example.pop(item);
    }
    return 0;
}

Kod kompiluje się, jednak program wypluwa to:

free(): invalid next size (fast): (jakis adres)

Memory map:
...
elo112131Aborted (core dumped)
process returned 134 (0x86)

Chciałbym się dowiedzieć co zrobiłem źle i jak poprawić metody pop i push tak abym nie musiał za każdym razem wrzucać tablicę do zmiennej tymczasowej, usuwał ją i inicjalizował wartościami. Mam nadzieję, że istnieje wydajniejszy sposób.

Answer 1

        ++top;
        std::cout << top;
        pitems[top] = item;

`++top` sprawia, że późniejsze `pitems[top]` wychodzi poza tablicę.

(tak ogólnie, skoro wiesz z góry jaki jest maksymalny rozmiar stosu, to nie widzę potrzeby ciągłego realokowania)

Comments

Ale wcześniej jest:

pitems = new Item[top + 1]; //! 
for(int i = 0; i < top; ++i) 
{ pitems[i] = temp[i]; } 
++top; //teraz jest to równe !

Więc ++top nie wychodzi za tablicę skoro pitems ma rozmiar top+1

Nie wiem czy rozumiem pytanie w nawiasie ale rozmiar stosu jest domyślnie równy MAX ale można go zmienić
Nie jestem tylko pewny czy tablica ma cały czas ma mieć rozmiar wystarczający na pomieszczenie bieżącej liczby elementów czy na maksymalną liczbę zawartą w parametrze konstruktora. Teraz sensowniejsza wydaje mi się druga opcja, ale jestem ciekaw czy da się to zrobić pierwszym sposobem bez kopiowania do zmiennej tymczasowej i z powrotem z vector lub bez (nie używałem jej jeszcze).

Answer 2

Rozwiązanie z jedną alokacją:
 

// stack.h -- definicja klasy stosu (wg ADT)
#ifndef STACK_H_
#define STACK_H_
#include <iostream>

typedef unsigned long Item;

class Stack
{
    private:
        enum { MAX = 10};    // stała zasięgu klasy
        Item * pitems;     // przechowuje elementy stosu
        int size;
        int top;             // indeks szczytowego elementu stosu
    public:
        Stack(int n = MAX);
        Stack(const Stack & s);
        ~Stack();
        bool isempty() const;
        bool isfull() const;
        // push() zwraca false, jeśli stos jest już pełen (true w pozostałych przypadkach)
        bool push(const Item & item);    // odkłada element na stos
        // pop() zwraca false, jeśli stos jest już pusty (true w pozostałych przypadkach)
        bool pop(Item & item);           // zdejmuje element ze stosu
        Stack & operator=(const Stack & st);
        friend std::ostream & operator<<(std::ostream & os, const Stack & st);
        int showSize() const;

};
#endif

// stack.cpp -- metody klasy stosu
#include "stack.h"
#include <iostream>
Stack::Stack(int n)            // tworzy pusty stos
{
    size = n;
    top = 0;
    pitems = new Item[n];
}

Stack::Stack(const Stack & s)
{
    pitems = new Item [size];
    size = s.size;
    for (int i = 0; i < sizeof(s.pitems) / sizeof(Item); ++i)
        pitems[i] = s.pitems[i];
    top = s.top + 1;
}

Stack::~Stack()
{
    delete [] pitems;
}

bool Stack::isempty() const
{
    return top == 0;
}

bool Stack::isfull() const
{
    return top == MAX;
}

bool Stack::push(const Item & item)
{
    if (top < size)
    {
        ++top;
        pitems[top] = item;
        return true;
    }
    else
        return false;
}

bool Stack::pop(Item & item)
{
    if (top > 0)
    {
        item = pitems[top];
        --top;
        return true;
    }
    else
    {
        delete [] pitems;
        return false;
    }
}

Stack & Stack::operator=(const Stack & s)
{
    if(this == &s)
        return *this;
    top = s.top;
    size = s.size;
    for (int i = 0; i < top; ++i)
    {
        pitems[i] = s.pitems[i];
    }
    return *this;
}

std::ostream & operator<<(std::ostream & os, const Stack & s)
{
    os << "Zawartosc kolejki (w kolejnosci zwalniania ze stosu): " << std::endl;
    for (int i = s.top; i > 0; --i)
    {
        os << s.pitems[i] << std::endl;
    }
    os << "Wolnych miejsc: ";
    if (s.size == s.top)
        os << "brak " << std::endl;
    else
        os << s.size - s.top << std::endl;

}

int Stack::showSize() const
{
    return size;
}

#include "stack.h"

using namespace std;

int main()
{
    int size;
    cout << "wielkosc stosu" << endl;
    cin >> size;
    Stack example(size);
    cout << "Dodaj do stosu: ";
    unsigned long add;
    unsigned long * ptrash = new unsigned long [example.showSize()];
    int trash_count = 0;
    for (int i = 0; i < example.showSize() && cout << "Dodaj do stosu: " && cin >> add; ++i)
    {
        example.push(add);
    }
    cin.clear();
    cout << example;
    cout << "Zdjac ze stosu? (wpisz cokolwiek): ";
    string pop;
    getline(std::cin,pop);
    for (int i = example.showSize(); i >= 0 && !pop.empty(); ++i)
    {
        example.pop(ptrash[i]);
        cout << "Zdjac ze stosu? (wpisz cokolwiek): ";
    }

    delete [] ptrash;
    return 0;
}