Implementation of the stack as a singly linked list

This paper provides an example of a template class Stack<T> that implements a stack as a singly linked list. By following this instruction step by step, you can get a fully working stack class.

Before studying this topic, it is recommended that you familiarize yourself with the following topics:

Stack. Operations on the stack. An example implementation of the stack as a dynamic array
Linear singly linked list. General information. Basic operations on the list

Search other websites:

1. The Stack<T> class API. Client requirements

In this article, the stack is implemented in the Stack<T> template class. The following API is defined for this class:

For the correct operation of the class (copying, freeing memory, etc.), public additional functions are defined.

⇑

2. The program code of the Stack<T> class

2.1. Declaring an empty Stack<T> class

At the very beginning, you need to declare an empty template class Stack<T>, which operates with the generic type T:

#include <iostream>
using namespace std;

template <class T>
class Stack
{

};

⇑

2.2. Hidden Node<T> structure

The private section introduces a structure that describes one node on the stack. Figure 1 shows the structure view

Figure 1. The Node<T> structure

The program code of the structure in the class is as follows

template <class T>
class Stack
{
private:
  // Internal structure
  template <class T>
  struct Node
  {
    T data;
    Node<T>* next;
  };
};

⇑

2.3. Entering the internal fields head and size

In the private section of the class, internal fields are introduced that have the following purpose:

head – pointer to the top of the stack;
size – stack size.

The code snippet with the entered fields looks like this:

...

template <class T>
class Stack
{
private:

  ...

  Node<T>* head; // pointer to the top of the stack
  unsigned int size; // stack size
};

...

⇑

2.4. Internal function Copy()

In the copy constructor and copy operator, you must perform a stack copy operation from the outer object to the internal data structure pointed to by the head pointer (the top of the stack).

Therefore, in order to optimize the code in the private section of the class, you need to introduce the Copy() function

private:

  ...

  // The Copy() function is used if you want to get a copy of the stack into the internal data.
  void Copy(Node<T>* _head)
  {
    // 1. Checking
    if (_head == nullptr)
      return;

    // 2. Additional variables
    Node<T>* p = _head; // Set the pointer to the top of the stack
    bool f_first = true;
    Node<T>* p2 = nullptr;
    Node<T>* p3 = nullptr;

    // 2. Stack traversal loop
    size = 0; // number of items on the stack

    while (p != nullptr)
    {
      // 2.1. Allocate memory and fill it with values
      try
      {
        p2 = new Node<T>;
        p2->data = p->data;
        p2->next = nullptr;

        // 2.2. Checking if the first item is added
        if (f_first)
        {
          // 2.3. If the first item is added
          head = p2;
          p3 = p2;
          f_first = false;
        }
        else
        {
          // 2.4. If not the first one is added, then set the next pointer
          p3->next = p2;
          p3 = p3->next;
        }

        // 2.4. Increase the number of items
        size++;

        // 2.5. Move to the next item
        p = p->next;
      }
      catch (bad_alloc e)
      {
        cout << e.what();
      }
    }
  }

⇑

2.5. Freeing the memory allocated for the stack. The Free() method

An important operation is stack deallocation, which can be called by the copy assignment operator and the destructor. This operation is implemented using the Free() function.

...

private:

  ...

  // A method that releases memory for the stack
  void Free()
  {
    // 1. Set the pointer to the top of the stack
    Node<T>* p = head;

    // 2. Stack traversal and memory freeing
    while (p != nullptr)
    {
      head = head->next;
      delete p;
      p = head;
      size--; 
    }
  }

⇑

2.6. Constructor Stack()

A constructor is introduced into the public section, which creates the empty stack.

public:

  // Create the empty stack
  Stack()
  {
    head = nullptr;
    size = 0;
  }

⇑

2.7. Function Push(). Add item to the stack

To add an element to the stack, the Push() function is used. The element is added to the top of the stack. Accordingly, the head pointer is shifted.

public:

  ...

  // Add element to stack
  void Push(T item)
  {
    try
    {
      // 1. If the first element
      if (size == 0)
      {
        head = new Node<T>;
        head->next = nullptr;
        head->data = item;
      }
      else
      {
        // 2. If not the first element
        // 2.1. Create a new cell and fill it with data
        Node<T>* p2 = new Node<T>;
        p2->data = item;
        p2->next = nullptr;

        // 2.2. Set pointers
        p2->next = head;
        head = p2;
      }

      // Increase the number of elements on the stack
      size++;
    }
    catch (bad_alloc e)
    {
      cout << e.what();
    }
  }

⇑

2.8. Method Pop(). Pop the item from the stack

Removing an element from the stack is implemented using the Pop() method, which is described below.

public:

  ...

  // Pop an item from the stack
  T Pop()
  {
    // 1. Checking
    if (size == 0)
      return 0;

    // 2. Save the item that will be returned
    T item = head->data;

    // 3. Set additional pointer to the head
    Node<T>* p = head;

    // 4. Move the head
    head = head->next;

    // 5. Free the memory allocated for the top of the stack
    delete p;

    // 6. Decrease the number of elements on the stack
    size--;

    // 7. Return item
    return item;
  }

⇑

2.9. Displaying the stack on the screen. The Show() method

In order to control the correct execution of the program, the Show() method is introduced into the class, which displays the stack.

// Display the stack
void Show(string msg)
{
  Node<T>* p = head;
  cout << msg << " => ";
  while (p != nullptr)
  {
    cout << p->data << "  ";
    p = p->next;
  }
  cout << endl;
}

⇑

2.10. Destructor ~Stack()

The stack allocated for a class object is cleared in the destructor, which calls the Free() method described in paragraph 2.5.

// Freeing memory - destructor
~Stack()
{
  Free();
}

⇑

2.11. Determining if the stack is empty. The IsEmpty() method.

// Returns true, if stack is empty
bool IsEmpty()
{
  return size == 0;
}

⇑

2.12. Get the stack size. Method Size()

// Return the stack size
int Size() const { return size; }

⇑

2.13. Copy constructor Stack(const Stack<T>& obj)

The copy constructor copies the outer parameter object into the inner data structures. To do this, the Copy() function is called, the implementation of which is described in section 2.4.

// Copy constructor this<=obj
Stack(const Stack<T>& obj)
{
  // Traverse obj stack and make a copy
  Copy(obj.head);
}

The copy assignment operator checks whether there are items in the stack. If there are elements on the receiver stack, then this stack is freed by calling the Free() method. Copying the source stack to the destination stack is done using the Copy() method.

// Copy assignment operator
Stack<T>& operator=(const Stack<T>& obj)
{
  if (this != &obj)
  {
    if (size > 0)
      Free();
    Copy(obj.head);
  }
  return *this;
}

⇑

3. Abbreviated program code of the Stack<T> class.

An abbreviated class code with comments is shown below.

#include <iostream>
using namespace std;

template <class T>
class Stack
{
private:
  // internal structure
  template <class T>
  struct Node
  {
    T data;
    Node<T>* next;
  };

  Node<T>* head; // pointer to the head of the stack
  unsigned int size = 0;

  // The Copy() function is used if you need to get a copy of the stack into internal data.
  void Copy(Node<T>* _head)
  {
    ...
  }

  // Method that frees the memory allocated for the stack
  void Free()
  {
    ...
  }

public:
  // Create empty stack
  Stack()
  {
    ...
  }

  // Add item to the stack
  void Push(T item)
  {
    ...
  }

  // Display stack on the screen
  void Show(string msg)
  {
    ...
  }

  // Release memory
  ~Stack()
  {
    ...
  }

  // Returns true, if stack is empty
  bool IsEmpty()
  {
    ...
  }

  // Pop item from the stack
  T Pop()
  {
    ...
  }

  // Return the stack size
  int Size() const
  {
    ...
  }

  // Copy constructor this<=obj
  Stack(const Stack<T>& obj)
  {
    ...
  }

  // Copy assignment operator
  Stack<T>& operator=(const Stack<T>& obj)
  {
    ...
  }
};

⇑

4. Class performance test. The main() function

The main() function is used to test the operation of the stack class and may look arbitrary.

void main()
{
  Stack<int> S1;
  Stack<int> S3;
  S3 = S1;

  if (S3.IsEmpty())
    cout << "+";
  else
    cout << "-";

  S1.Push(10);
  S1.Push(15);
  S1.Push(20);
  cout << S1.Size() << endl;
  S1.Show("S1");

  Stack<int> S2 = S1;
  S2.Show("S2");

  S3 = S2;
  S3.Show("S3");

  if (S3.IsEmpty())
    cout << "+";
  else
    cout << "-";
}

BestProg

Programming: theory and practice