Поняття стеку. Операції над стеком. Приклад реалізації стеку у вигляді динамічного масиву

---

Зміст

• 1. Призначення динамічної структури даних типу “стек”. Способи реалізації стеку
• 2. Які операції можна виконувати над стеком та його елементами?
• 3. Приклад шаблонного класу, в якому стек представлений як динамічний масив

---

Пошук на інших ресурсах:

1. Призначення динамічної структури даних типу “стек”. Способи реалізації стеку

Стек – це динамічна структура зберігання даних, яка працює за принципом “останній прийшов – перший вийшов” (Last-In First-Out). У стеку додавання нових елементів та видалення існуючих відбувається з одного кінця, який називається вершиною стеку.

Організація даних з допомогою стеку ефективна коли потрібно реалізувати:

• обмін даними між методами додатку з допомогою параметрів;
• синтаксичний аналіз різноманітних виразів.

У програмуванні стек можна реалізовувати різними способами, наприклад:

• у вигляді статичного масиву
• у вигляді динамічного масиву;
• у вигляді однозв’язного списку;
• у вигляді двохзв’язного списку.

  ⇑

2. Які операції можна виконувати над стеком та його елементами?

Над стеком та його елементами можна виконувати наступні операції:

• додавання елементу в стек (push);
• витягування (видалення) елементу зі стеку (pop);
• перегляд елементу у вершині стеку без його витягування зі стеку;
• перевірка, чи стек пустий;
• визначення кількості елементів у стеку;
• відображення (перегляд) всього стеку.

  ⇑

---

---

3. Приклад шаблонного класу, в якому стек представлений як динамічний масив

У прикладі оголошується шаблонний клас STACK, який реалізує стек у вигляді динамічного масиву. Клас реалізує поля та базові функції (методи) для організації роботи стеку:

• внутрішній масив-покажчик на узагальнений тип T та змінну count, що визначає кількість елементів у стеку;
• конструктор за замовчуванням;
• метод push(), що поміщає елемент в стек;
• метод pop(), що витягує елемент зі стеку;
• метод Head(), що переглядає елемент, що розміщується у вершині стеку;
• конструктор копіювання, який використовується для ініціалізації об’єкту типу STACK;
• операторна функція operator=(), яка викликається при присвоюванні об’єктів типу STACK;
• деструктор;
• метод Count() – повертає кількість елементів у стеку;
• метод IsEmpty() – визначає, чи пустий стек;
• метод Print() – виводить стек на екран, використовується для тестування.

 

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

// клас, що реалізує стек у вигляді динамічного масиву
template <typename T>
class STACK
{
private:
  T* stack; // Динамічний масив-покажчик на стек
  int count; // Вершина стеку - к-сть елементів типу T в стеку

public:
  // конструктор за замовчуванням
  STACK()
  {
    stack = nullptr; // необов'язково
    count = 0; // к-сть елементів у стеку визначається за значенням count
  }

  // помістити елемент в стек
  void push(T item)
  {
    T* tmp; // тимчасовий покажчик

    // блок try необхідний для перехоплення виключення, якщо пам'ять не виділиться
    try {
      // покажчик показує на stack (щоб не загубити адресу покажчика stack)
      tmp = stack;

      // виділити пам'ять на 1 елемент більше, ніж було виділено перед цим в стеку
      stack = new T[count + 1];

      // збільшити кількість елементів в стеку на 1
      count++;

      // скопіювати дані з пам'яті, на яку вказує tmp в пам'ять,
      // на яку вказує stack
      for (int i = 0; i < count - 1; i++)
        stack[i] = tmp[i];

      // додати останній елемент
      stack[count - 1] = item;

      // звільнити пам'ять, яка була перед цим виділена для stack,
      // на цю пам'ять вказує tmp
      if (count > 1)
        delete[] tmp;
    }
    catch (bad_alloc e)
    {
      // якщо пам'ять не виділилась
      cout << e.what() << endl;
    }
  }

  // Витягнути елемент зі стеку
  // При витягуванні елементу зі стеку пам'ять не перевизначається
  T pop()
  {
    if (count == 0)
      return 0; // стек пустий
    count--;
    return stack[count];
  }

  // Перегляд елементу, що розміщується у вершині стеку
  T Head()
  {
    if (count == 0)
      return 0;
    return stack[count - 1];
  }

  // конструктор копіювання STACK(const STACK&) - необхідний для уникнення
  // недоліків побітового копіювання
  STACK(const STACK& st)
  {
    try {
      // 1. Виділити нову ділянку пам'яті для масиву stack
      stack = new T[st.count];

      // 2. Скопіювати дані з st в поточний об'єкт
      count = st.count;
      for (int i = 0; i < count; i++)
        stack[i] = st.stack[i];
    }
    catch (bad_alloc e)
    {
      // якщо пам'ять не виділилась, то вивести відповідне повідомлення
      cout << e.what() << endl;
    }
  }

  // операторна функція operator=(const STACK&) - необхідна для уникнення
  // недоліків побітового копіювання
  STACK operator=(const STACK& st)
  {
    // Потрібно скопіювати з st в поточний об'єкт
    // 1. Звільнити попередньо виділену пам'ять для поточного об'єкту
    if (count > 0)
    {
      count = 0;
      delete[] stack; // звільнити пам'ять під попередній масив
    }

    // 2. Виділити нову ділянку пам'яті для масиву stack
    try {
      // спроба виділити пам'ять
      stack = new T[st.count];

      // 3. Скопіювати дані з st в поточний об'єкт
      count = st.count;
      for (int i = 0; i < count; i++)
        stack[i] = st.stack[i];
    }
    catch (bad_alloc e)
    {
      // якщо не вдалось виділити пам'ять, то вивести відповідне повідомлення
      cout << e.what() << endl;
    }

    // 4. Повернути поточний об'єкт
    return *this;
  }

  // Деструктор - звільняє пам'ять
  ~STACK()
  {
    if (count > 0)
      delete[] stack;
  }

  // Кількість елементів у стеку
  int Count()
  {
    return count;
  }

  // Функція, яка визначає, чи пустий стек
  bool IsEmpty()
  {
    return count == 0;
  }

  // Функція, що виводить стек
  void Print()
  {
    T* p; // тимчасовий покажчик, рухається по елементах стеку

    // 1. Встановити покажчик p на вершину стеку
    p = stack;

    // 2. Вивід
    cout << "Stack: " << endl;
    if (count == 0)
      cout << "is empty." << endl;

    for (int i = 0; i < count; i++)
    {
      cout << "Item[" << i << "] = " << *p << endl;
      p++; // прокрутити покажчик на наступний елемент
    }
    cout << endl;
  }
};

void main()
{
  // оголосити стек з цілих чисел
  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; // виклик оператора копіювання
  STACK<int> st3 = st2; // виклик конструктора копіювання
  // ----------------------

  // -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();

  // виклик оператора копіювання у вигляді ланцюжка
  st1 = st3 = st2;
  st1.Print();
}

Результат роботи програми:

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

  ⇑

---