Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Структуры данных типа стек. Реализация стека как отображения на массив и односвязный список. Примеры применения.




Стек – это последовательность, в которой включение и исключение элемента осуществляется с одной стороны последовательности (вершины стека). Так же осуществляется и операция доступа. Структура функционирует по принципу LIFO (последний пришедший обслуживается первым). Условные обозначения стека:

 

 

       
   
 

 

 


При реализации стека рассматриваются стек как отображение на массив и стек как отображение на список.

Совокупность операций, определяющих структуру типа стек:

1. Операция инициализации.

2. Операция включения элемента в стек.

3. Операция исключения элемента из стека.

4. Операция проверки: стек пуст / стек не пуст.

5. Операция проверки: стек переполнен / стек не переполнен (данная операция характерна для стека как отображения на массив).

6. Операция чтения элемента (доступ к элементу).

Все операции не зависят от размерности стека, т.е. порядок временной сложности – О(1).

Имеется две модификации стека:

· Указатель находится на вершине стека, показывая на первый пустой элемент.

· Указатель указывает на первый заполненный элемент.

 

 
 
слот

 


Стек в последовательной памяти (схема на физическом уровне):

S
Дескриптор:

Условные обозначения Название стека
Нижний адрес стека
Верхний адрес стека
Адрес указателя
Описание элемента

 


Поделиться:

Дата добавления: 2015-04-18; просмотров: 84; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты