Стек, очередь

Массив.

Массив - упорядоченная линейная совокупность однородных данных. Другими словами это пронумерованная, равноправная совокупность данных или массивов одного типа.

Если элементами данного массива являются массивы данных, тогда они должны иметь одинаковую структуру и размер.

Количество индексов, определяющих положение элемента в массиве, называется мерностью массива.

Если индекс единственный (m(i) или m [i]) массив называется одномер­ным (вектор, строка, столбец).

Массив, элементы которого имеют два индекса ( G [i, j]) называется двумерным или матрицей. Первый индекс является номером строки, а второй индекс - номе­ром столбца, на пересечении которых находится данный элемент. Максимальная мерность массива может быть ограничена синтак­сисом некоторых языков программирования, либо не иметь таких ограничений.

Максимальное значение индексов определяет размер массива. Размер массива указывается в блоке описания программы, т.к. для хранения элементов массива резервируется необходимый объем памяти. Если в процессе исполне­ния программы размер массива не может быть изменен - это массив фиксированного размера. Если изменение размеров массива происходит по ходу работы программы - это динамический массив.

Допустимый набор операций над элементами массива определяется типом элементарных или структурированных данных, из которых массив сформирован.

Особое место занимают символьные массивы - они называют­ся строками или строковыми данными (например, тип String в PASCAL'e). С ними возможен целый набор операций, неопреде­ленных для одиночных символьных данных. В первую очередь, это операция конкатенации (объединения) строк с формированием новой строки. Помимо этого имеются операции замещения части строки, а также определения ее числовых характеристик.

Стек (магазин) и очередь являются упорядоченными, линей­ными, неоднородными структурами. Реализуются в виде специальным образом организованных областей ОЗУ либо в качестве самостоятельных блоков памяти. Ячейки памяти стека (или регистры стековой памяти) соединяются друг с другом таким образом, что ввод данных возможен только в первую ячейку со сдвигом всех ранее записанных данных. При счи­тывании - содержимое всех ячеек памяти стека сдвигается и выталкивает содержимое первой ячейки. Другими словами, вход в стек возможен только через первую ячейку (вершину стека), поэтому извлекаться первой будет та информация, которая была занесена последней, подобно пас­сажиру переполненного автобуса.

Ячейки стека

Ввод Вывод

данных данных

Отличие очереди от стека только в том, что извлечение инфор­мации производится в порядке «первым вошел - первым вышел», т.е. со дна стека.

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

Дата добавления: 2014-01-06