Доброго времени суток! Сегодня мы посмотрим на реализацию совсем простой вещи — собственного стека на базе массива и на базе линейного списка. Код был мной написан на втором курсе, достаточно давно, перед написанием статьи я сдул с него пыль и немного подкорректировал страшные названия переменных, навел марафет. Теперь его можно показывать, хоть и осторожно.
Кратко о том, что такое стек. Это такой тип данных, в котором они организованны по принципу LIFO(last in — first out). По русски говоря, последним пришел, первым вышел. Отличный пример для визуализации это книжная стопка, верхняя книга последняя пришла и, если вы не собираетесь пугать кошку грохотом, первая ушла.
Реализация простейших структур данных — это отличный способ их изучить. Можно прочитать сотню книг про стек, но пока вы его не напишите самостоятельно, вы не подружитесь. Я писал реализацию на языке программирования С++, используя классы. Два стека — два класса и при большом желании можно запаковать их в отдельный файл и подключать к другим проектам.
Дорогие читатели, давайте заводить дружбу со стеком, поехали!
Функции работы со стеком
push — положить элемент на вершину стека;
pop — убрать элемент с вершины;
top — вернуть элемент на вершине, не убирая его оттуда;
size — вернуть размер стека.
Реализация стека на базе массива
Смысл в том, что данные хранятся в обычном массиве, но доступ к ним строго регулируется нами с помощью функций. Огромный недостаток в том, что размер стека ограничен. Она решается с помощью расширяемых массивов. Когда место в массиве кончается, просто выделяется новый участок памяти большего размера и все копируется туда. Насколько мне известно, в библиотеке STL стек реализован именно на расширяемых массивах.
Исходный код на C++
template <typename TElement>
class stackInArray {
private:
unsigned int sizeOfStack;
TElement *array;
public:
stackInArray(const unsigned int maxSize) {
sizeOfStack = 0;
array = new TElement [maxSize];
}
~stackInArray() {
delete[] array;
}
void push(const TElement newElement) {
array[sizeOfStack] = newElement;
sizeOfStack++;
}
void pop() {
sizeOfStack--;
}
TElement top() {
return array[sizeOfStack-1];
}
unsigned int size() {
return sizeOfStack;
}
};
Реализация стека на базе линейного списка
Линейный список это очень популярная структура данных, даже не смотря на то, что не очень быстрая. Очень часто встречается в реализации системных функций. Скорость работы компенсируется гибкостью. Список используем односвязный, реализуем минимальный набор функций, о которых я говорил ранее. Неоспоримое преимущество перед массивом — максимальный размер стека не ограничен.
Исходный код на C++
template <typename TElement>
struct TNode {
TElement data;
TNode <TElement> *next;
TNode (TElement newData, TNode <TElement> *nextNode) {
data = newData;
next = nextNode;
}
};
template <typename TElement>
class stackInList {
private:
unsigned int sizeOfStack;
TNode <TElement> *currentTop;
public:
stackInList() {
sizeOfStack = 0;
currentTop = NULL;
}
~stackInList() {
while (size())
pop();
}
void push (const TElement element) {
TNode <TElement> *node = new TNode <TElement> (element, currentTop);
sizeOfStack++;
currentTop = node;
}
void pop() {
sizeOfStack--;
TNode <TElement> *node = currentTop;
currentTop = currentTop->next;
delete node;
}
TElement top () {
return currentTop->data;
}
unsigned int size() {
return sizeOfStack;
}
};
Тестирование производительности
Реализовали два стека, грех с ними не побаловаться. Давайте посмотрим, какой из них работает быстрее. И сравним скорость их работы со стеком из STL, а вдруг нам удалось реализовать быстрее?
Функция тестирования
void testFunctionForStack() {
srand (time(NULL));
unsigned int testStackSize = 90000000;
stackInArray<int> arrayStack(testStackSize);
stackInList<int> listStack;
stack<int> stlStack;
clock_t time;
cout << "Stack size: " << testStackSize << endl;
cout << "Test for stack in array:" << endl;
time = clock();
for(unsigned int i = 0; i < testStackSize; i++) {
arrayStack.push(rand() % RAND_MAX);
}
time = clock() - time;
cout << "push for stack in array end: " << (double)time / CLOCKS_PER_SEC << "sec." << endl;
time = clock();
while(arrayStack.size()) {
arrayStack.pop();
}
time = clock() - time;
cout << "pop for stack in array end: " << (double)time / CLOCKS_PER_SEC << "sec." << endl;
cout << "Test for stack in array end." << endl;
cout << "---------------------------------------------------------------" << endl;
cout << "Test for stack in list:" << endl;
time = clock();
for(unsigned int i = 0; i < testStackSize; i++) {
listStack.push(rand() % RAND_MAX);
}
time = clock() - time;
cout << "push for stack in list end: " << (double)time / CLOCKS_PER_SEC << "sec." << endl;
time = clock();
while(listStack.size()) {
listStack.pop();
}
time = clock() - time;
cout << "pop for stack in list end: " << (double)time / CLOCKS_PER_SEC << "sec." << endl;
cout << "Test for stack in list end." << endl;
cout << "---------------------------------------------------------------" << endl;
cout << "Test for STL stack:" << endl;
time = clock();
for(unsigned int i = 0; i < testStackSize; i++) {
stlStack.push(rand() % RAND_MAX);
}
time = clock() - time;
cout << "push for STL stack end: " << (double)time / CLOCKS_PER_SEC << "sec." << endl;
time = clock();
while(stlStack.size()) {
stlStack.pop();
}
time = clock() - time;
cout << "pop for STL stack end: " << (double)time / CLOCKS_PER_SEC << "sec." << endl;
cout << "Test for STL stack end." << endl;
}
Результат
Заключение
Такой размер стека был выбран экспериментально, при большем размере моя система просто падала, весь системный ресурс уходил в тест(подозреваю, что это косяк убунты). Что мы видим? Наш стек на базе массива всех уделал, и это не удивительно, ведь STL-стек расширяемый, и бог знает, сколько ресурсов он потратил на расширения в этом тесте. Наш стек на массиве оказался самым быстрым, но совершенно не гибким. В принципе, если размер входных данных заранее известен и неизменяем, можно воспользоваться и этой реализацией.
Тема избита и стара, как мир, но я внес свою лепту. Не пропадать же коду, верно? Надеюсь, что кому нибудь пригодится мой опыт, спасибо за внимание!