The concept of stack. Operations on the stack. An example implementation of the stack as a dynamic array

---

Contents

• 1. Assignment of a dynamic data structure of the “stack” type. Ways to implement the stack
• 2. What operations can be performed on the stack and its elements?
• 3. An example of a template class in which the stack is represented as a dynamic array

---

Search other websites:

1. Assignment of a dynamic data structure of the “stack” type. Ways to implement the stack

Stack – a dynamic structure of data storage, which works on the principle of “last in – first out”. The addition of new elements stack and removing existing elements is made at one end, it called the top of the stack.

Organizing data using the stack is effective when you need to implement:

• data exchange between application methods using parameters;
• parsing a variety of expressions.

In programming, the stack can be implemented in various ways, for example:

• in the form of a dynamic array;
• in the form of a singly linked list;
• in the form of a doubly linked list.

  ⇑

2. What operations can be performed on the stack and its elements?

The following operations can be performed on the stack and its elements:

• adding an item to the stack (push);
• pulling (deleting) an item from the stack (pop);
• viewing an element at the top of the stack without removing it from the stack;
• checking if the stack is empty;
• determining the number of items in the stack;
• display (view) of the entire stack.

  ⇑

---

---

3. An example of a template class in which the stack is represented as a dynamic array

The example declares a template class STACK that implements the stack as a dynamic array. The class implements fields and basic functions (methods) for organizing the work of the stack:

• internal array-pointer to the generalized type T and the variable count, which determines the number of elements in the stack;
• default constructor;
• method push() that pushes an item on the stack;
• the pop() method, which pulls an item from the stack;
• Head() method, which views an item that is placed at the top of the stack;
• copy constructor, which is used to initialize an object of type STACK;
• operator function operator=(), which is called when assigning objects of type STACK;
• destructor;
• method Count() – returns the number of items in the stack;
• method IsEmpty() – determines whether the stack is empty;
• method Print() – displays the stack on the screen, used for testing.

 

#include <iostream>
#include <new>
using namespace std;

// class that implements the stack as a dynamic array
template <typename T>
class STACK
{
private:
  T* stack; // Dynamic array-pointer to stack
  int count; // The top of the stack - the number of elements in the stack type T

public:
  // default constructor
  STACK()
  {
    stack = nullptr; // not necessary
    count = 0; // the number of items on the stack is determined by the value of count
  }

  // Push the item onto the stack
  void push(T item)
  {
    T* tmp; // temporary pointer

    // block try is needed to catch an exception if memory is not allocated
    try {
      // pointer points to stack
      tmp = stack;

      // allocate memory 1 element more than was allocated before
      stack = new T[count + 1];

      // increase the number of elements in the stack by 1
      count++;

      // copy data
      for (int i = 0; i < count - 1; i++)
        stack[i] = tmp[i];

      // add the last item
      stack[count - 1] = item;

      // free the memory allocated before this for stack
      if (count > 1)
        delete[] tmp;
    }
    catch (bad_alloc e)
    {
      // if memory is not allocated
      cout << e.what() << endl;
    }
  }

  // Pop an item from the stack
  // When an item is pulled from the stack, the memory is not redefined
  T pop()
  {
    if (count == 0)
      return 0; // the stack is empty
    count--;
    return stack[count];
  }

  // View item at the top of the stack
  T Head()
  {
    if (count == 0)
      return 0;
    return stack[count - 1];
  }

  // copy constructor STACK(const STACK&)
  STACK(const STACK& st)
  {
    try {

      // 1. Allocate new memory for array stack
      stack = new T[st.count];

      // 2. Copy data from st to current object
      count = st.count;
      for (int i = 0; i < count; i++)
        stack[i] = st.stack[i];
    }
    catch (bad_alloc e)
    {
      // if the memory is not allocated, then display the corresponding message
      cout << e.what() << endl;
    }
  }

  // operator function operator=(const STACK&)
  STACK operator=(const STACK& st)
  {
    // Need to copy from st to current object
    // 1. It is needed to free preallocated memory for current object
    if (count > 0)
    {
      count = 0;
      delete[] stack;
    }

    // 2. Allocate new memory for array stack
    try {
      // attempt to allocate memory
      stack = new T[st.count];

      // 3. Copy data from st to current object
      count = st.count;
      for (int i = 0; i < count; i++)
        stack[i] = st.stack[i];
    }
    catch (bad_alloc e)
    {
      // if you can not allocate memory, then display an appropriate message
      cout << e.what() << endl;
    }

    // 4. Return the current object
    return *this;
  }

  // Destructor - frees memory
  ~STACK()
  {
    if (count > 0)
      delete[] stack;
  }

  // The number of elements in the stack
  int Count()
  {
    return count;
  }

  // Function that determines if the stack is empty.
  bool IsEmpty()
  {
    return count == 0;
  }

  // Function, which displays the stack
  void Print()
  {
    T* p; // temporary pointer, moves through the items of the stack

    // 1. Set pointer p to the top of the stack
p = stack;

    // 2. Output
    cout << "Stack: " << endl;
    if (count == 0)
      cout << "is empty." << endl;

    for (int i = 0; i < count; i++)
    {
      cout << "Item[" << i << "] = " << *p << endl;
      p++; // scroll pointer to the next item
    }
    cout << endl;
  }
};

void main()
{
  // declare a stack of integers
  STACK <int> st1;

  st1.Print(); // st1 = { }

  // +5
  st1.push(5); // st1 = { 5 }

  // +9
  st1.push(9); // st1 = { 5, 9 }

  // +13
  st1.push(13); // st1 = { 5, 9, 13 }

  // +7
  st1.push(7); // st1 = { 5, 9, 13, 7 }
  st1.Print();
  cout << "Count: " << st1.Count() << endl;

  // ----------------------
  STACK <int> st2;
  st2 = st1; // copy operator call
  STACK<int> st3 = st2; // copy constructor call
  // ----------------------

  // -1 item
  int t;
  t = st1.pop(); // t = 7
  cout << "Delete item: " << t << endl;
  st1.Print(); // 5, 9, 13
  cout << "Head: " << st1.Head() << endl;

  // -2 items
  st1.pop(); // st1 = { 5, 9 }
  st1.pop(); // st1 = { 5 }
  st1.Print();

  // -2 items
  st1.pop(); // st1 = { }
  st1.pop();
  st1.Print();

  if (st1.IsEmpty())
    cout << "Stack is empty." << endl;
  else
    cout << "Stack is not empty" << endl;

  cout << "Stack st2:" << endl;
  st2.Print();

  cout << "Stack st3:" << endl;
  st3.Print();

  // invoke the copy operator as a chain
  st1 = st3 = st2;
  st1.Print();
}

The result of the program:

Stack:
is empty.

Stack:
Item[0] = 5
Item[1] = 9
Item[2] = 13
Item[3] = 7

Count: 4
Delete item: 7
Stack:
Item[0] = 5
Item[1] = 9
Item[2] = 13

Head: 13
Stack:
Item[0] = 5

Stack:
is empty.

Stack is empty.
Stack st2:
Stack:
Item[0] = 5
Item[1] = 9
Item[2] = 13
Item[3] = 7

Stack st3:
Stack:
Item[0] = 5
Item[1] = 9
Item[2] = 13
Item[3] = 7

Stack:
Item[0] = 5
Item[1] = 9
Item[2] = 13
Item[3] = 7

  ⇑

---