Куча
Одной из наиболее распространенных форм организации данных является упорядоченный список или линейный список. Это можно представить как 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