Куча

Одной из наиболее распространенных форм организации данных является упорядоченный список или линейный список. Это можно представить как a = (a1, a2,…,an).

Стек — это упорядоченный список, в котором все вставки и удаления выполняются с одного конца, называемого верхним.

Операции со стеком подразумевают, что если элементы A, B, C, D и E вставлены в стек в указанном порядке, то первым извлекаемым (удаляемым) элементом должен быть элемент E. Или можно сказать, что последним элемент, который должен быть вставлен в стек, удаляется первым. По этой причине стеки иногда называют Lпоследними, In первыми выходными (LIFO). ) списки.

Представление стека с помощью массивов

Простейший способ представить стек — использовать одномерный массив, скажем, stackPtr[MaxSize], где MaxSize — максимально допустимое количество записей. Первый или нижний элемент стека хранится в stackPtr[0], второй — в stackPtr[1] и так далее.

С массивом связана переменная с именем top, которая указывает на верхний элемент в стеке. Чтобы проверить, пуст ли стек, мы спрашиваем -

if (top < 0)

Если нет, верхний элемент находится в stackPtr[top]. Проверить, заполнен ли стек, можно, спросив:

if (top >= (MaxSize - 1))

Еще две операции — вставка и удаление элементов. Каждое выполнение функции добавления или удаления занимает постоянное время и не зависит от количества элементов в стеке. Следовательно, сложность равна O(1).

#include <iostream>
using namespace std;
template<class Type>
class Stack
{
private:
  int MaxSize, top;
  Type* stackPtr;
public:
  Stack(int mSize) : MaxSize{mSize} {
    top = -1;
    stackPtr = new Type[MaxSize];
  }
  ~Stack() {
    delete [] stackPtr;
  }
  bool StackEmpty() {
    if (top < 0) return true;
    else return false;
  }
  bool StackFull() {
    if (top == MaxSize-1) return true;
    else return false;
  }
  bool Add(const Type &item) {
    if (StackFull()) {
      cout << "Stack is full\n";
      return false;
    }
    else {
      stackPtr[++top] = item;
      return true;
    }
  }
  bool Delete(Type &item) {
    if (StackEmpty()) {
      cout << "Stack is empty\n";
      return false;
    }
    else {
      item = stackPtr[top--];
      return true;
    }
  }
  void Show() {
    if (StackEmpty()) {
      cout << "Stack is empty\n";
      return;
    }
    for (int i=0; i<=top; i++) cout << stackPtr[i] << " ";
    cout << endl;
  }
};
int main(int argc, char const *argv[]) {
  Stack<int> s(5);
  s.Add(20);
  s.Add(21);
  s.Add(22);
  s.Show();
  int num;
  s.Delete(num);
  cout << "Popped out = " << num << endl;
  s.Show();
  return 0;
}

Вывод вышеуказанной программы

20 21 22
Popped out = 22
20 21