Don't use a linked structure for a stack. It's much easier to use an array, and significantly faster -- much more cache friendly.
You can use
operator new[]
to create a block of memory, and push objects to the slot at index
i++
.
You can pop objects off the stack at index
--i
, and that's essentially it.
i
, of course, always refers to the next free spot on the stack.
If
i
is 0, your stack is empty.
When the stack gets too big, allocate a block of memory that's roughly twice as big and copy the old data over to the new block.
However, doing a truly generic data structure correctly is a little bit difficult.
Some questions you may want to ponder, either now or later, once you get this working:
"how do I store a type that can't be default constructed"?
"how do I store a type that can't be copied?"
"how do I store types that can throw exceptions when being moved from (and still provide a strong exception safety guarantee)"?
Maybe there are some more. I don't remember.
Edit: Here's a very rough sketch to get you started:
1 2 3 4 5 6 7 8 9 10 11
|
class my_stack {
private:
int data[1000] {};
int i {};
public:
void push(int const val) { data[i++] = val; }
int pop() { return data[--i]; }
int peek() const { if (is_empty()) throw "oh no"; else return data[i - 1]; }
bool is_empty() const { return i == 0; }
bool is_full() const { return i == 1000; }
};
|