There are 2 implementations of Stack ADT
template <class Item>
class STACK
{
private:
Item *s; int N;
public:
STACK(int maxN)
{ s = new Item[maxN]; N=0;}
int empty() const
{ return N==0; }
void push(Item item)
{ s[N++] = item; }
Item pop()
{ return s[--N];}
}
we keep stack in reverse order from array implementation
To pop , we remove the node from front of list
To push , create a node and add to front of list
template <class Item>
class STACK
{
private:
struct node
{ Item item; node* next;
node(Item x, node* t)
{ item =x; next =t;}
};
typedef node *link;
link head;
public:
STACK(int)
{ head = 0;}
int empty() const
{ return head == 0;}
void push(Item x)
{ head = new node(x,head);}
Item pop()
{ Item v = head->item; link t = head->next;
delete head; head =t ; return v;}
};
Note both codes are not complete