 |
|
Основные операции над стеком и его элементами.
- Добавление элемента в стек.
- Удаление элемента из стека.
- Проверка, пуст ли стек. (Стек считается "пустым", если указатель вершины совпадает с указателем нижней границы.)
- Просмотр элемента в вершине стека без удаления.
- Очистка стека.
Применение.
Динамическая структура Стек чаще всего используется при синтаксическом анализе всевозможных выражений.
Примечание:Кстати, каждое приложение имеет собственный стек. В нём компилятор создает локальные переменные. А, также, через стек происходит передача параметров в функцию.
| Предыдущая | Оглавление | Следующая |
| Предыдущая | Оглавление | Следующая |
Реализация - стек.
| #include <iostream>#include <string.h>#include <time.h>using namespace std; class Stack{ // Нижняя и верхняя границы стека enum {EMPTY = -1, FULL = 20}; // Массив для хранения данных char st[FULL + 1]; // Указатель на вершину стека int top; public: // Конструктор Stack(); // Добавление элемента void Push(char c); // Извлечение элемента char Pop(); // Очистка стека void Clear(); // Проверка существования элементов в стеке bool IsEmpty(); // Проверка на переполнение стека bool IsFull(); // Количество элементов в стеке int GetCount(); }; Stack::Stack(){ // Изначально стек пуст top = EMPTY;} void Stack::Clear(){ // Эффективная "очистка" стека // (данные в массиве все еще существуют, // но функции класса, ориентированные на работу с вершиной стека, // будут их игнорировать) top = EMPTY;} bool Stack::IsEmpty(){ // Пуст? return top == EMPTY;} bool Stack::IsFull(){ // Полон? return top == FULL;} int Stack::GetCount(){ // Количество присутствующих в стеке элементов return top + 1;} void Stack::Push(char c){ // Если в стеке есть место, то увеличиваем указатель // на вершину стека и вставляем новый элемент if(!IsFull()) st[++top] = c;} char Stack::Pop(){ // Если в стеке есть элементы, то возвращаем верхний и // уменьшаем указатель на вершину стека if(!IsEmpty()) return st[top--]; else // Если в стеке элементов нет return 0;} void main(){ srand(time(0)); Stack ST; char c; // пока стек не заполнится while(!ST.IsFull()){ c=rand()%4+2; ST.Push(c); } // пока стек не освободится while(c=ST.Pop()){ cout<<c<<" "; } cout<<"\n\n"; } |
| Предыдущая | Оглавление | Следующая |
| Предыдущая | Оглавление | Следующая |
Очередь.
Следующая динамическая структура, которую мы рассмотрим - простая очередь. Очередь, так же как и стек можно реализовывать на практике с помощью массива.
Очередь — это последовательный набор элементов с переменной длиной. При этом, добавление элементов в очередь происходит с одной стороны, а удаление — с другой стороны. Данная конструкция функционирует по идеологии FIFO (First In — First Out), то есть "первым пришел — первым вышел". Для очереди принято выделять конечную последовательность элементов, из которых в каждый текущий момент времени элементами очереди заняты лишь часть последовательных элементов.
В принципе, с простой очередью вы сталкиваетесь постоянно. Вот лишь некоторые из примеров:очередь в мавзолей, очередь печати принтера, даже действия линейного алгоритма выполняются по очереди.
| Предыдущая | Оглавление | Следующая |
| Предыдущая | Оглавление | Следующая |