Структура данных - тип организации данных, позволяющий использовать эффективный доступ к модификации данных. Например, массив с константным размером является простейшей структурой данных. В данной статье мы рассмотрим несколько простейших структур данных: стек, очередь и дек.

Стек

Стек (stack - стопка), является простейшей структурой данных. Чтобы описать стек, приведем простой пример: представьте, что у вас есть стопка бумаг. Все, что вы можете сделать - это положить туда еще одну или взять последнюю. Про остальные листы мы ничего не знаем (на данный момент). Такой принцип реализации называется LIFO (Last In, First Out), подчёркивающая, что элемент, попавший в стек последним, первым будет из него извлечён. Также можно провести аналогию с лифтом - последний вошедший человек будет первым вышедшим из него.

В стандартной библиотеке С++ определен класс stack. Ниже приведен код, который реализует некоторые методы данного класса.

#include <iostream>
#include <stack>

using namespace std;

int main()
{
int n,temp;
stack<int> s;
cin >> n;
for (int i = 0; i < n; i++)
{
	cin >> temp;
	s.push(temp);
}
if (s.empty())
	cout << "Stack is empty" << endl;
else
{
	cout << "The top element of stack is: " << s.top() << endl;
	s.pop();
	cout << "Now the top element of stack is: " << s.top() << endl;
}
return 0;
}

Очередь

Очередь (queue) - это структура данных, которая построена по принципу LILO (last in — last out: последним пришел — последним вышел). В C++ уже есть готовый STL контейнер — queue. В очереди, если вы добавите элемент, который вошел самый первый, то он выйдет тоже самым первым. Получается, если вы добавите 4 элемента, то первый добавленный элемент выйдет первым. Для того, чтобы лучше понять принцип очереди, можно представить себе очередь в магазине. Чтобы вас обслужили, требуется, чтобы обслужили всех человек, которые находятся впереди вас. Важное замечание - в очереди невозможно обратиться к определенному элементу.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	int n, temp;
	queue <int> q;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		q.push(temp);
	}
	while (!q.empty())//пока очередь не пуста
	{
		cout << "Current element: " << q.front()<<endl;
		q.pop();
	}
	return 0;
}

Дек

Дек (deque) — это сокращенная фраза «double-ended-queue», что, в переводе с английского, означает — двусторонняя очередь. Контейнер дек похож на vector, разница состоит лишь в том, что в деках динамический массив открыт с двух сторон. Это и позволяет очень быстро добавлять новые элементы как в конец, так и в начало контейнера. В векторах элементы можно добавлять лишь в конец массива.

deque <int> d;
d.push_back(5);
d.push_front(1);
d.pop_back();
for (int i = 0; i < d.size(); i++)
	cout << d[i] << " ";

В приведенном выше коде мы создаем дек d и добавляем число 5 в конец, а число 1 - в начало. Затем мы удаляем последний элемент. Вывод очевиден - это число 1.

В данной статье мы рассмотрели самые простейшие структуры данных. В дальнейшем мы также познакомимся с более сложными структурами, такими, как графы, деревья и т.д.