Полустатические cтруктуры данных.

Стеки.

Полустатические структуры данных характеризуются следующими признаками:

►они имеют переменную длину и простые процедуры ее изменения;

►изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного)

значения.

►Доступ к элементу может осуществляться по его порядковому номеру.

Стек

►Упорядоченный набор элементов в котором размещение новых элементов и удаление существующих производится с одного конца

►одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом LIFO (Last In First Out)

Стек

Операции над стеком

►Добавление в стек - push ►Удаление из стека – pop

►Прочитать элемент с вершины стека ( не извлекая) – peek

►Элементы в стеке любые

Список функций на языке С++ для работы со стеком:

►push() – добавить элемент; ►pop() – удалить элемент;

►top() – получить верхний элемент; ►size() – размер стека;

►empty () – проверить стек на наличие элементов.

Эти функции входят в стандартную

библиотеку C++ (STL), а именно в контейнер stack.

Cостояния стека

Реализация стека

►Статический - на базе массивов ►Динамический - на базе списков

Представление стека массивом

#include <iostream>
using namespace std;	//размер
const int ms = 100;
стека	//данные
char St[ms];
стека	//вершина
int top = -1;
стека

Проверить стек на наличие элементов

bool isStackEmpty(int top) //стек пуст?

{ return (top < 0);

}