Is this a reasonable way to implement a stack ?

[aneeshm]

Question for the techincally oriented around here - is the following a reasonable method of implementing a stack ?


class stack
{
int data;
stack* next;

public:

stack();
int pop();
void push(int);

};

stack::stack()
{
data=0;
next=NULL;
}

int stack:op()
{
if(next==NULL)
{
cout<<"Stack empty"< exit(0);
}

stack* p=this;

while(p->next->next!=NULL)
p=p->next;

int temp=p->next->data;
delete p->next;

return temp;

}

void push(int a)
{
stack* p=this;

while(p->next!=NULL)
p=p->next;

p->next=new stack;
p->next->data=a;

}


The code tags are , for some reason , mangling the code . I'll attach a file instead .

[aneeshm]

File attached .

[Kuciwalker]

No. It's never reasonable to write code without indents

[loinburger]

I'd use either an array or a doubly-linked list instead. It's not reasonable for the push and pop methods to be O(n).

Edit: At a bare minimum, keep a tail pointer so that the push method runs in constant time.

[Japher]

Robert Stack

[Provost Harrison]

Giant hay-stacks

[BlackCat]

As loinburger suggests, get yourself a last pointer and turn the pointers around.

push ()
{
p new stack;
p->prev = last;
last = p
}

pop ()
{
stack temp = last->prev;
delete last
last = temp;
}

[Harovan]

It's not a good implementation. A LIFO is a simple thing to do and should not need a search algorithm for push or pop operations - you just attach new items to the bottom, moving all else up, and take items to remove from there too.

I would recommend you 2 things:

1 - Introduce an item container and don't make your stack recursive
2 - Implement it as template, so it fits for any numeric type and even for classes with an operator =() implemented.

An implementation skeleton would be


#include <cassert>

template <typename T>
struct Item {
T Data;
Item<T>* Next;
};

template <typename T>
class Stack {
Item<T>* Bottom;

public:
Stack();
~Stack();

void Push(T item);
T Pop();
};

template <typename T>
Stack<T>::Stack()
: Bottom(NULL)
{
}

template <typename T>
Stack<T>::~Stack()
{
while (Bottom != NULL) // make sure the stack is empty before we destroy, to prevent leaks
Pop();
}

template <typename T>
void
Stack<T>::Push(T item)
{
Item<T>* newItem = new Item<T>;
newItem->Data = item;
newItem->Next = Bottom;
Bottom = newItem;
}

template <typename T>
T
Stack<T>::Pop()
{
assert(Bottom != NULL); // Or with an if() like in your example

Item<T>* oldItem = Bottom;
Bottom = oldItem->Next;
T oldData = oldItem->Data;
delete oldItem;
return oldData;
}

#include <iostream>

int main()
{
Stack<int> S;
S.Push(1);
S.Push(2);
std::cout << S.Pop() << std::endl;
std::cout << S.Pop() << std::endl;
return 0;
}


[Urban Ranger]

The simplest way is to use a fixed sized array. This way you will never get a stack overrun or underrrun.

[BlackCat]

Originally posted by Urban Ranger
The simplest way is to use a fixed sized array. This way you will never get a stack overrun or underrrun.

That really doesn't make sense.

[Urban Ranger]

What doesn't make sense?

Suppose you have an array S. A push operation would be just adding to the array. Suppose SP, the stack pointer, points to the current location. Checking SP against the maximum size of S before the push prevents overrun.

You can implement a pop in a similar, simple fashion.

[loinburger]

Originally posted by Urban Ranger
What doesn't make sense?

It unnecessarily bounds the size of your stack and introduces a lot of internal fragmentation.

A linked list of small (say, 4-12 elements) arrays reduces memory overhead, has minimal internal fragmentation, improves cache performance, and lets you do some loop transformations that aren't possible with a simple linked list (e.g., loop unrolling). Implementing the stack as one massive array doesn't gain you much over the linked list of arrays, and its disadvantages greatly outweigh its negligible advantages.

Yes, it's a simple way to code a stack. No, you should never code a stack this way.

[loinburger]

Originally posted by Sir Ralph
An implementation skeleton would be...

In addition, unless you're sure that your clients know what they're doing (which is always a dangerous assumption), make sure that anything your stack deletes (i.e., Item<T> *Bottom) is private. You don't want crap like that inadvertently escaping the stack's scope.

[Harovan]

Originally posted by loinburger

In addition, unless you're sure that your clients know what they're doing (which is always a dangerous assumption), make sure that anything your stack deletes (i.e., Item<T> *Bottom) is private. You don't want crap like that inadvertently escaping the stack's scope.

You might have a look at my destructor. And Item<T> *Bottom _is_ private.

[loinburger]

Is private the default?