Development a template class that implements a stack in the form of a linked list

---

Contents

• 1. Advantages of implementing a stack as a singly linked list compared to a dynamic array
• 2. A NodeStack structure implementing the node
• 3. Implementation of the stack as a singly linked list (figure)
• 4. Program text
• 5. The result of the program
• 6. Features of the program implementation
  • 6.1. Memory allocation for the stack item
  • 6.2. Clearing the stack. Method Empty()
  • 6.3. Copy constructor and copy operator
• Related topics

---

Search other websites:

1. Advantages of implementing a stack as a singly linked list compared to a dynamic array

The implementation of a dynamic data structure stack in the form of a singly linked list has the following advantages:

• in the case of adding a new element there is a need for less memory. In a singly linked list, additional memory for an element is allocated only for that one element. In a dynamic array, you first need to allocate a new fragment (array) of memory for all elements, then copy the old array to the new one and only then free the memory allocated for the old array. With the increasing number of elements in the stack, this advantage becomes more pronounced;
• fewer additional operations in case of manipulating the stack (adding a new element, deleting an element).

Disadvantages:

• complexity of implementation. Processing a singly linked list is more difficult to implement (this is all conditional);
• to access the i-th element in a dynamic array, it is convenient to use access by index. In a singly linked list, you need to revise (rewind) the entire list from the beginning to the desired position.

  ⇑

2. A NodeStack structure implementing the node

Any simply connected (doubly connected) list is based on a special structure or class that implements a single node (Figure 1).

Figure 1. A node in the case of a singly linked list: item – data element, next – pointer to a structure of type NodeStack

In the node (structure), two elements are distinguished:

• an item element of some generalized type T;
• pointer to the next element of type NodeStack<T>.

In C ++, the declaration of the NodeStack structure is as follows

// The structure describing the node
template <typename T>
struct NodeStack
{
  T item;
  NodeStack<T>* next;
};

  ⇑

3. Implementation of the stack as a singly linked list (figure)

Figure 2 shows a stack in the form of a simply connected list.

Figure 2. Stack as a singly linked list

The top of the stack is the pTop pointer. In the last node of the stack, the value next = nullptr.

---

---

  ⇑

4. Program text

The program implements the template class StackList, which implements the stack in the form of a simply linked list. At the request of the class text, you can add other functions that expand its capabilities.

The following fields and methods are declared in the class:

• pointer pTop – top of the stack;
• default constructor;
• copy constructor StackList(const StackList&);
• destructor;
• the Push() method, which pushes an item onto the stack;
• method Pop() – extracting an element from the stack;
• method Count() – returns the number of elements in the stack;
• Empty() method – removes all items from the stack;
• copy operator operator=(const StackList&) – is necessary to implement the correct assignment of objects of the StackList class;
• the Print() method, which displays the contents of the stack on the screen.

The full text of the StackList class and NodeStack structure is as follows

#include <iostream>
using namespace std;

// The structure describing the node
template <typename T>
struct NodeStack
{
  T item;
  NodeStack<T>* next;
};

// Template class Stack based on a singly linked list
template <typename T>
class StackList
{
private:
  NodeStack<T>* pTop; // pointer to the top of the stack

public:
  // default constructor
  StackList() { pTop = nullptr; }

  // copy constructor
  StackList(const StackList& SL)
  {
    NodeStack<T>* p; // additional pointers
    NodeStack<T>* p2;
    NodeStack<T>* p3;

    // Initialize pTop
    pTop = nullptr;
    p3 = nullptr;

    p = SL.pTop; // pointer p moves through the list SL.pTop->...
    while (p != nullptr)
    {
      // 1. Form a node p2
      try {
        // attempt to allocate memory
        p2 = new NodeStack<T>;
      }
      catch (bad_alloc e)
      {
        // if no memory is allocated, then exit
        cout << e.what() << endl;
        return;
      }
      p2->item = p->item;
      p2->next = nullptr;

      // 2. pTop = pTop + p2
      if (pTop == nullptr)
      {
        pTop = p2;
        p3 = p2;
      }
      else
      {
        p3->next = p2;
        p3 = p3->next;
      }

      // 3. Go to next item
      p = p->next;
    }
  }

  // push an item onto the stack
  // the item is placed at the top of the list
  void Push(T item)
  {
    NodeStack<T>* p;

    // 1. Form an item.
    try {
      p = new NodeStack<T>; // attempt to allocate memory
    }
    catch(bad_alloc e)
    {
      // if memory is not allocated, then exit
      cout << e.what() << endl;
      return;
    }
    p->item = item;
    p->next = pTop; // p points to the 1st item

    // 2. Redirect pTop to p
    pTop = p;
  }

  // Number items in the stack
  int Count()
  {
    if (pTop == nullptr)
      return 0;
    else
    {
      NodeStack<T>* p = pTop;
      int count = 0;

      while (p != nullptr)
      {
        count++;
        p = p->next;
      }
    }
  }

  // clears the stack - removes all elements from the stack
  void Empty()
  {
    NodeStack<T>* p; // additional pointers
    NodeStack<T>* p2;

    p = pTop;
    while (p != nullptr)
    {
      p2 = p; // make a copy of p
      p = p->next; // go to the next element of the stack
      delete p2; // delete memory allocated for previous item
    }
    pTop = nullptr; // correct the top of the stack
  }

  // copy operator
  StackList<T>& operator=(const StackList<T>& LS)
  {
    // whether there are elements in the stack?
    if (pTop != nullptr) Empty();

    NodeStack<T>* p; // additional pointers
    NodeStack<T>* p2;
    NodeStack<T>* p3;

    // initialize pTop
    pTop = nullptr;
    p3 = nullptr;

    p = LS.pTop; // pointer p moves through the list SL.pTop->...
    while (p != nullptr)
    {
      // 1. Form a node p2
      try {
        // attempt to allocate memory
        p2 = new NodeStack<T>;
      }
      catch (bad_alloc e)
      {
        // if memory is not allocated, then exit
        cout << e.what() << endl;
        return *this;
      }
      p2->item = p->item;
      p2->next = nullptr;

      // 2. pTop = pTop + p2
      if (pTop == nullptr) // create the stack
      {
        pTop = p2;
        p3 = p2;
      }
      else
      {
        p3->next = p2;
        p3 = p3->next;
      }

      // 3. Go to the next item
      p = p->next;
    }
    return *this;
  }

  // Display the stack
  void Print(const char* objName)
  {
    cout << "Object: " << objName << endl;

    if (pTop == nullptr)
      cout << "stack is empty." << endl;
    else
    {
      NodeStack<T>* p; // additional pointer
      p = pTop;
      while (p != nullptr)
      {
        cout << p->item << "\t";
        p = p->next;
      }
      cout << endl;
    }
  }

  // destructor
  ~StackList()
  {
    Empty();
  }

  // method puller from the stack
  T Pop()
  {
    // check if the stack is empty?
    if (pTop == nullptr)
      return 0;

    NodeStack<T>* p2; // additional pointer
    T item;
    item = pTop->item;

    // redirect pointers pTop, p2
    p2 = pTop;
    pTop = pTop->next;

    // Free the memory allocated for the 1st item
    delete p2;

    return item;
  }
};

void main()
{
  StackList<int> SL;
  SL.Print("SL");

  SL.Push(8);
  SL.Push(5);
  SL.Push(10);
  SL.Push(7);
  SL.Print("SL");

  // copy constructor checking
  StackList<int> SL2 = SL;
  SL2.Print("SL2");

  SL.Empty();
  SL.Print("SL");

  SL = SL2;
  SL.Print("SL = SL2");

  StackList<int> SL3;
  SL3.Push(1);
  SL3.Push(2);
  SL3.Push(3);
  SL3.Print("SL3");

  SL = SL2 = SL3;
  SL.Print("SL");
  SL2.Print("SL2");

  int d = SL2.Pop();
  cout << "d = " << d << endl;
  SL2.Print("SL2-1");

  d = SL2.Pop();
  SL2.Print("SL2-2");

  d = SL2.Pop();
  SL2.Print("SL2-3");

  d = SL2.Pop();
  cout << "d = " << d << endl;
  SL2.Print("SL2----");
}

  ⇑

5. The result of the program

Object: SL
stack is empty.
Object: SL
7 10 5 8
Object: SL2
7 10 5 8
Object: SL
stack is empty.
Object: SL = SL2
7 10 5 8
Object: SL3
3 2 1
Object: SL
3 2 1
Object: SL2
3 2 1
d = 3
Object: SL2-1
2 1
Object: SL2-2
1
Object: SL2-3
stack is empty.
d = 0
Object: SL2----
stack is empty.

  ⇑

6. Features of the program implementation

6.1. Memory allocation for the stack item

Memory allocation for a node is performed using the new operator. However, it is possible that the memory will not be allocated. In this case, an exception of type bad_alloc will be thrown. The type bad_alloc is a class. The program uses the following try … catch block to handle this situation.

try {
  p = new NodeStack<T>; // attempt to allocate memory
}
catch (bad_alloc e)
{
  // if memory is not allocated, then exit
  cout << e.what() << endl;
  return;
}

If memory for pointer p has not been allocated, then the corresponding system message can be displayed using the what() method of the bad_alloc class.

  ⇑

6.2. Clearing the stack. Method Empty()

Clearing the stack is implemented in the Empty() method. To clear the stack, you need to free memory for each element of the stack in a loop as shown below

void Empty()
{
  NodeStack<T>* p; // additional pointers
  NodeStack<T>* p2;

  p = pTop;
  while (p != nullptr)
  {
    p2 = p; // make the copy od p
    p = p->next; // go to the next item of the stack
    delete p2; // delete memory allocated for the previous item
  }
  pTop = nullptr; // correct the top of stack
}

  ⇑

6.3. Copy constructor and copy operator

Since the memory in the StackList class is dynamically allocated, it is imperative to implement your own copy constructor and copy operator in this class to avoid the disadvantages of bitwise copying. For more information about the copy constructor can be read here. The copy operator is necessary for the proper assignment of objects of the StackList class.

  ⇑

---

Related topics

• Stack. Operations on the stack. An example implementation of the stack as a dynamic array
• Queue. General concepts. Ways to implement the queue. Implementing a queue as a dynamic array
• Priority Queue. Example of implementation for template class. Implementation as a dynamic array

  ⇑

---