Implementation of a C++ Integer Stack Class using Singly-Linked list.

In the previous post, stack was implemented using one-dimensional array. Another way to represent stack is by using linked lists or simply links.

Remarks:

• The use of links to represent a stack requires more storage than sequential array stack[0 : n-1] does.
• There is greater flexibility when using links, for many structures can simultaneously use the same pool of available space.
• Insertion and deletion using either representation are independent of the size of the stack.

Representation of four-element stack implemented using pointer based single linked list

Algorithm for Linked List representation of the Stack

// Linked List representation of a stack
// Type is any Data Type
// Node represents single data element of the stack.
node = record
{
    Type data;
    node *link;
}

Algorithm Add(item)
{
    // Get a new node.
    temp := new node;
    if(temp != 0) then
    {
        (temp -> data) := item;
        (temp -> link) := top;
        top := temp;
        return true;
    }
    else
    {
        // Out of space
        return false;
    }
}

Algorithm Delete(item)
{
    if(top = 0) then
    {
        // Stack is empty
        return false;
    }
    else
    {
        item := (top -> data);
        temp := top;
        top := (top -> link);
        delete temp;
        return true;
    }
}

C++ Program for the implementation of Integer Stack Class using singly linked list

Lets begin with simple implementation of Integer Stack in C++ using a pointer based single linked list.
Later we will extend this implementation to more Generic Stack using templates.

// Implementation of a Integer Stack class using singly-linked list.
#include <assert.h>

typedef int ItemType;

class Stack
{
private:
    struct Node {
        ItemType val;
        Node* next;

        Node(const ItemType& vv, Node* nn) : val(vv), next(nn) { }
        Node(const ItemType& vv) : val(vv), next(0) { }
 };

Node* head;

public:
    Stack();        // Creates an empty stack.
    Stack(const Stack& other);      // Copy constructor. Copies all the values of stack in the stack

    ~Stack();       // Destructor.

    bool IsEmpty() const;                   // Returns true if the stack is empty

    void Push(const ItemType& x);       // 'x' is put on the top of the stack
    ItemType Peek() const;                  // Returns a copy of the item on top of the stack. It does not remove the item from the stack
    void RemoveTop();                       // Deletes the top element of the stack
    ItemType Pop();                         // Removes the top item of the stack and returns it



};

// Creates an empty stack.
Stack::Stack() : head(nullptr) { }

// Makes a "deep" copy of another stack.
Stack::Stack(const Stack& other)
{
    if (other.IsEmpty()) {
        head = nullptr;
    }
    else
    {
        Node* p = other.head;               // points to current node on other
        Node* tmp = new Node(p->val);    // make a copy of the first node
        head = tmp;
        Node* tail = tmp;                   // points to last node of this list
        while (p->next != nullptr)
        {
            p = p->next;
            tmp = new Node(p->val);
            tail->next = tmp;
            tail = tmp;
        }
    }
}

// Completely destroys a stack.
Stack::~Stack()
{
    while (!IsEmpty()) RemoveTop();
}

// Returns true if this stack is empty, and false otherwise
bool Stack::IsEmpty() const
{
    return head == nullptr;
}

// 'x' is put on the top of the stack
void Stack::Push(const ItemType& x)
{
    Node* tmp = new Node(x, head);
    head = tmp;
}

// Returns a copy of the item on top of the stack; Does *not* remove the item from the stack
ItemType Stack::Peek() const
{
    // Error check: Make sure we aren't peeking inside an an empty stack
    assert(false == IsEmpty());
    return head->val;
}

// Deletes the top element of the stack
void Stack::RemoveTop()
{
    // Error check: Make sure we aren't deleting from an empty stack
    assert(false == IsEmpty());

    Node* tmp = head;
    head = head->next;
    delete tmp;
}

// Removes the top item of the stack and returns it
ItemType Stack::Pop()
{
    // Error check: Make sure we aren't popping from an empty stack
    assert(false == IsEmpty());

    ItemType result = Peek();
    RemoveTop();
    return result;
}

C++ Program for the implementation of Stack Class Template using singly linked list

Let us now expand our earlier implementation of Integer Stack class to more Generic Stack using templates.

// Implementation of Stack class Templates using singly-linked list.
#include <assert.h>

template <class ItemType>
class Stack
{
private:
    struct Node {
        ItemType val;
        Node* next;

        Node(const ItemType& vv, Node* nn) : val(vv), next(nn) { }
        Node(const ItemType& vv) : val(vv), next(0) { }
 };

 Node* head;

public:
    Stack();        // Creates an empty stack.
    Stack(const Stack& other);      // Copy constructor. Copies all the values of stack in the stack

    ~Stack();       // Destructor.

    bool IsEmpty() const;                   // Returns true if the stack is empty

    inline void Push(const ItemType& x);       // 'x' is put on the top of the stack
    inline ItemType Peek() const;                  // Returns a copy of the item on top of the stack. It does not remove the item from the stack
    inline void RemoveTop();                       // Deletes the top element of the stack
    inline ItemType Pop();                         // Removes the top item of the stack and returns it
};

// Implementation of Stack Class
// Creates an empty stack.
template<class ItemType>
Stack<ItemType>::Stack() : head(nullptr) { }

// Makes a "deep" copy of another stack.
template<class ItemType>
Stack<ItemType>::Stack(const Stack& other)
{
    if (other.IsEmpty()) {
        head = nullptr;
    }
    else
    {
        Node* p = other.head;               // points to current node on other
        Node* tmp = new Node(p->val);    // make a copy of the first node
        head = tmp;
        Node* tail = tmp;                   // points to last node of this list
        while (p->next != nullptr)
        {
            p = p->next;
            tmp = new Node(p->val);
            tail->next = tmp;
            tail = tmp;
        }
    }
}

// Completely destroys a stack.
template<class ItemType>
Stack<ItemType>::~Stack()
{
    while (!IsEmpty()) RemoveTop();
}

// Returns true if this stack is empty, and false otherwise
template<class ItemType>
bool Stack<ItemType>::IsEmpty() const
{
    return head == nullptr;
}

// 'x' is put on the top of the stack
template<class ItemType>
inline void Stack<ItemType>::Push(const ItemType& x)
{
    Node* tmp = new Node(x, head);
    head = tmp;
}

// Returns a copy of the item on top of the stack; Does *not* remove the item from the stack
template<class ItemType>
inline ItemType Stack<ItemType>::Peek() const
{
    // Error check: Make sure we aren't peeking inside an an empty stack
    assert(false == IsEmpty());
    return head->val;
}

// Deletes the top element of the stack
template<class ItemType>
inline void Stack<ItemType>::RemoveTop()
{
    // Error check: Make sure we aren't deleting from an empty stack
    assert(false == IsEmpty());

    Node* tmp = head;
    head = head->next;
    delete tmp;
}

// Removes the top item of the stack and returns it
template<class ItemType>
ItemType Stack<ItemType>::Pop()
{
    // Error check: Make sure we aren't popping from an empty stack
    assert(false == IsEmpty());

    ItemType result = Peek();
    RemoveTop();
    return result;
}