Структура данных типа «стек». Логическая структура стека. Программные реализации стека. Основные операции над стеком.

⇐ ПредыдущаяСтр 13 из 35Следующая ⇒

Стек — структура данных, представляющая собой список элементов, организованных по принципу LIFO.

Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.

Организация в памяти

Зачастую стек реализуется в виде однонаправленного списка (каждый элемент списка указывает только на следующий). Но в таком случае невозможно применить операцию обхода элементов. А доступ возможен только к верхнему элементу структуры. Для обхода такой проблемы можно взять за основу двусвязный список (каждый элемент указывает на обоих соседей справа и слева). Кроме того можно организовать его на обыкновенном массиве.

Значением переменной стека является указатель на вершину стека. Если стек пуст, то значение указателя равно NULL.

Пример реализации стека на языке Си:

struct stack{ char *data; struct stack *next;};

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

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek).

При проталкивании (push) указывается новый элемент, указывающий на элемент бывший до этого головой. Новый элемент теперь становится головным.

При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).

void push( STACK *ps, int x ) // Добавление в стек нового элемента{ if ( ps->size == STACKSIZE ) // Не переполнен ли стек? { fputs( "Error: stack overflow\n", stderr ); abort(); } else { ps->items[ps->size++] = x; }} int pop( STACK *ps ) // Удаление из стека{ if ( ps->size == 0 ) // Не опустел ли стек? { fputs( "Error: stack underflow\n", stderr ); abort(); } else { return ps->items[--ps->size]; }}

Простые линейные списки. Программные реализации создания и ведения простого линейного списка.

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка

Характеристика:

· Длина списка. Количество элементов в списке.

· Списки могут быть типизированными или нетипизированными. Если список типизирован, то тип его элементов задан, и все его элементы должны иметь типы, совместимые с заданным типом элементов списка. Обычно списки, реализованные при помощи массивов, являются типизированными.

· Список может быть сортированным или несортированным

· В зависимости от реализации может быть возможен произвольный доступ к элементам списка.

Структуры данных типа «очередь». Логическая структура очереди. Машинное представление очереди FIFO и реализация операций. Очереди с приоритетами.

⇐ Предыдущая 8 9 10 11 121314 15 16 17 Следующая ⇒

Последнее изменение этой страницы: 2018-04-12; просмотров: 285.

stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...