Стек характерен тем, что получить доступ к его элементам можно лишь с одного конца, называемого вершиной стека; иначе говоря: стек – структура данных типа «список», функционирующая по принципу LIFO (last in — first out, «последним пришёл — первым вышел»).
Графически его удобно изобразить в виде вертикального списка (см. рис.), например, стопки книг, где чтобы воспользоваться одной из них, и не нарушить установленный порядок, нужно поднять все те книги, что лежат выше нее, а положить книгу можно лишь поверх всех остальных.
Впервые стек был предложен в 1946 году Аланом Тьюрингом, как средство возвращения из подпрограмм. В 1955 году немцы Клаус Самельсон и Фридрих Бауэр из Технического университета Мюнхена использовали стек для перевода языков программирования и запатентовали идею в 1957 году. Но международное признание пришло к ним лишь в 1988 году.
На рисунке показан стек, операции над элементами которого, происходят строго с одного конца: для включения нужного элемента в n-ую ячейку, необходимо сдвинуть n-1 элементов, и исключить тот элемент, который занимает n-ую позицию.
Стек, чаще всего, реализуется на основе обычных массивов, односвязных и двусвязных списков. В зависимости от конкретных условий, выбирается одна из этих структур данных.
Основными операциями над стеками являются:
- добавление элемента;
- удаление элемента;
- чтение верхнего элемента.
В языках программирования эти три операции, обычно дополняются и некоторыми другими.
Вот, например, список функций C++ для работы со стеком:
- push() – добавить элемент;
- pop() – удалить элемент;
- top() – получить верхний элемент;
- size() – размер стека;
- empty() – проверить стек на наличие элементов.
Данные функции входят в стандартную библиотеку шаблонов C++ – STL, а именно в контейнер stack. Далее будет рассмотрен пример работы с контейнером stack, а пока разберем стек, реализованный на основе массива.
Программа, имитирующая интерфейс стека, основанного на базе статического массива, будет состоять из следующих операций, реализованных в виде функций:
- Creation() – создание пустого стека;
- Full() – проверка стека на пустоту;
- Add() – добавление элемента;
- Delete() – удаление элемента;
- Top() – вывод верхнего элемента;
- Size() – вывод размера стека.
Как таковых пользовательских операций тут всего четыре: Add, Delete, Top, Size. Они доступны из консоли. Функция Creation – создает пустой стек сразу после запуска программы, а Full проверяет возможность выполнения пользовательских операций.
#include "stdafx.h" #include <iostream> using namespace std; const int n=3; struct Stack { int A[n]; int count; }; //создание стека void Creation(Stack *p) { p->count=0; } //проверка стека на пустоту int Full(Stack *p) { if (p->count==0) return 1; else if (p->count==n) return -1; else return 0; } //добавление элемента void Add(Stack *p) { int value; cout<<"Введите элемент > "; cin>>value; p->A[p->count]=value; p->count++; } //удаление элемента void Delete(Stack *p) { p->count--; } //вывод верхнего элемента int Top(Stack *p) { return p->A[p->count-1]; } //размер стека int Size(Stack *p) { return p->count; } //главная функция void main() { setlocale(LC_ALL,"Russian"); Stack s; Creation(&s); char number; do { cout<<"1. Добавить элемент"<<endl; cout<<"2. Удалить элемент"<<endl; cout<<"3. Вывести верхний элемент"<<endl; cout<<"4. Узнать размер стека"<<endl; cout<<"0. Выйти"<<endl; cout<<"Номер команды > "; cin>>number; switch (number) { case '1': if (Full(&s)==-1) cout<<endl<<"Стек заполнен\n\n"; else { Add(&s); cout<<endl<<"Элемент добавлен в стек\n\n"; } break; //----------------------------------------------- case '2': if (Full(&s)==1) cout<<endl<<"Стек пуст\n\n"; else { Delete(&s); cout<<endl<<"Элемент удален из стека\n\n"; } break; //----------------------------------------------- case '3': if (Full(&s)==1) cout<<endl<<"Стек пуст\n\n"; else cout<<"\nВерхний элемент: "<<Top(&s)<<"\n\n"; break; //----------------------------------------------- case '4': if (Full(&s)==1) cout<<endl<<"Стек пуст\n\n"; else cout<<"\nРазмер стека: "<<Size(&s)<<"\n\n"; break; //----------------------------------------------- case '0': break; default: cout<<endl<<"Команда не определена\n\n"; break; } } while(number!='0'); system("pause"); }
Как видно, часто встречающимся элементом программы является поле count структуры stack. Оно исполняет роль указателя на «голову» стека. Например, для удаления элемента достаточно сдвинуть указатель на одну ячейку назад. Основная часть программы зациклена, и чтобы выйти из нее, а, следовательно, и из приложения вообще, нужно указать 0 в качестве номера команды.
Многие языки программирования располагают встроенными средствами организации и обработки стеков. Одним из них, как подчеркивалось ранее, является C++. Разберем принципы функционирования контейнера stack стандартной библиотеки шаблонов STL. Во-первых, stack – контейнер, в котором добавление и удаление элементов осуществляется с одного конца, что свойственно непосредственно стеку. Использование стековых операций не требует их описания в программе, т. е. stack здесь предоставляет набор стандартных функций. Для начала работы со стеком в программе необходимо подключить библиотеку stack:
#include <stack>
и в функции описать его самого:
stack <тип данных> имя стека;
Обратите внимание, что скобки, обособляющие тип данных, указываются здесь не как подчеркивающие общую форму записи, а как обязательные при описании стека.
Теперь в программе можно использовать методы контейнера. Следующая программа является аналогом предыдущей, но вместо пользовательских функций в ней используются функции контейнера stack.
#include "stdafx.h" #include <iostream> #include <stack> using namespace std; //главная функция void main() { setlocale(LC_ALL,"Russian"); stack <int> S; //создание стека S типа int char number; int value; do { cout<<"1. Добавить элемент"<<endl; cout<<"2. Удалить элемент"<<endl; cout<<"3. Получить верхний элемент"<<endl; cout<<"4. Узнать размер стека"<<endl; cout<<"0. Выйти"<<endl; cout<<"Номер команды > "; cin>>number; switch (number) { case '1': //добавление элемента cout<<"Значение > "; cin>>value; S.push(value); cout<<endl<<"Элемент добавлен в стек\n\n"; break; //----------------------------------------------- case '2': //удаление элемента if (S.empty()==true) cout<<"\nСтек пуст\n\n"; else { S.pop(); cout<<endl<<"Элемент удален из стека\n\n"; } break; //----------------------------------------------- case '3': //вывод верхнего элемента if (S.empty()==true) cout<<"\nСтек пуст\n\n"; else cout<<"\nВерхний элемент стека: "<<S.top()<<"\n\n"; break; //----------------------------------------------- case '4': //вывод размера стека if (S.empty()==true) cout<<"\nСтек пуст\n\n"; else cout<<"\nРазмер стека: "<<S.size()<<"\n\n"; break; //----------------------------------------------- case '0': break; //выход default: cout<<endl<<"Команда не определенная\n\n"; break; } } while(number!='0'); system("pause"); }
Использование стандартных средств C++ позволило заметно сократить общий объем программы, и тем самым упростить листинг. По своему функционалу данная программа полностью аналогична предыдущей.