Stack ADT implementation using linked lists

Stack ADT implementation using linked lists is much simpler than that of a List ADT because we only have to support insertion and removal at one end. The implementation using linked lists is illustrated in the following figure:

Imgur

Figure 1. A stack where we pushed 5, 7, and 4.

Notice that the object itself only contains one pointer: top, which will point to the top of the element at the top of the stack. Since we only need fast access to that element, we don't even need to have a tail pointer or a length data member, as we did in the implementation of the List ADT using linked lists.

Imgur

Figure 2. A stack object that represents an empty stack.

Here is a declaration of such class with the classical stack operations of empty, push, pop and getTop (I had to call it getTop instead of top because I used top as a data member).

class StackLLInt {

private:
    Node *top;
public:
    StackLLInt(): top(NULL) {}
    bool empty() const;
    void push(int k);
    void pop();
    int getTop() const;
};