Структуры данных. Стек и очередь. Реализация стека, дека и очереди с помощью массива и списка.

 

Стеки - это множество элементов, сложенных в стопку. Например, у нас есть коробка 3х5. Мы кладем в нее доски такого же размера с различными узорами. У нас получается стек. Достать из него мы можем только начинаяя с последнего элемента, поэтому первый положенные элемент вынут будет последним. В стеках реализуется принцип firstinlastout (FILO).

Для создания стека нужно подключить <stack> и в коде программы его объявить:

stack<type>name, где type - тип стека, а name - имя стека.

У стека есть немного функций:

push() - добавить элемент

pop() - удалить верхний элемент

top() - получить верхний элемент

size() - размер стека

empty() - true, если стек пуст

 

Стек довольно прост в реализации:

 

classstack

{

private:

inttop; // вершинастека

int s[10]; // массив в котором хранится стек

 

public:

stack (): top(0) // конструктор без параметров

{}

 

voidpush(intvar); // функция для проталкивания элементов в стек

intpop(); // функция выталкивания элементов из стека

};

 

void stack::push(intvar)

{

top++; // Увеличение вершины.

s[top] = var; // Добавление значения в элемент

} // на который указывает вершина.

 

 

intstack::pop()

{

intvar = s[top]; // Получаем значение элемента на который

top--; // указывает вершина и уменьшаем вершину.

returnvar;

}

Здесь представлен самый примитивный вариант стека. Стек представлен массивом s. Данная реализация стека может работать только с переменными типа int. К тому же, максимальный размер стека мы ограничили десятью элементами.

 

Использовать такой стек в реальной программе очень опасно! Потому что нет механизмов по предотвращению переполнения и опустошения стека.

 

Ваша задача немножко доработать стек. Добавьте проверку на переполнение и опустошение стека. Для этого создайте две функции: empty() (пустой) и full() (полный). Данные функции нужно вызывать в push() или pop().

 

 

Очереди, как следует из название, используют принцип firstinfirstout (FIFO). То есть, тот, кого мы первым запихнули в очередь, первым из нее и выйдет (хотя в реальной жизни не всегда так....)

Реализуются очереди также просто.

 

classqueue

{

private:

inthead, tail; // переменные хранящие начальный и конечный индексы

int q[10]; // очередь содержащая десять элементов

 

public:

queue(): head(0),tail(0) // конструктор

{}

voidenqueue(intnumber) // добавление в очередь

{

q[tail] = number;

tail = (tail+1) % 10;

}

intdequeue () // удаление из очереди

{

int temp = q[head];

head = (head+1) % 10;

returntemp;

}

};

 

Queue - очередь.

Enqueue - поместить в очередь.

Dequeue - вывести из очереди.

Head - начало.

Tail - конец.

Temp - временный.

head - позиция первого элемента в очереди

 

tail - позиция в которую будет добавляться элемент.

 

При условии head = tail, очередь пуста.

 

В данном примере очередь хранится в массиве q из десяти элементов.

 

За добавление/удаление из очереди отвечают две функции enqueue() и dequeue().

 

В функцию enqueue() передаётся значение, которое присваивается последнему элементу очереди. Затем индекс последнего элемента (tail) увеличивается. Обратите внимание, что если индекс достигнет последнего значения - в нашем примере 9, то индекс переносится в начало. Достигается это использованием операции взятия остатка от деления (%). Например: допустим что в данный момент tail = 9, мы вызываем функцию enqueue(3), в десятый элемент массива (q[9]) заносится значение 3. Затем происходит увеличение tail на единицу.теперь оно равно 10. Теперь получившееся значения делится на 10 и берётся остаток. 10 % 10 = 0. Соответственно теперь tail = 0.

 

Функция dequeue() работает следующим образом: мы сохраняем значения элемента на который указывает индекс head во временной переменной temp. Затем увеличиваем head. Здесь также используем операцию взятия остатка, для переноса head в начало массива. Затем возвращаем temp.

 

Структуры и объединения как тип данных. Объявление и описание объектов структурного типа. Доступ к данным структур и объединений с помощью указателей.

 

Структура – объединенное в единое целое множество поименнованных элементов в общем случае разных типов. Определение структурного типа начинается с ключевого слова struct.

 

Structname

{

Char …;

Int …;

…

…

…

}A,B[10],f*; // элементы структурного типа объявляются так

Или

….

.

.

.

};

NameA,B[10],*pB; //или так

 

Все элементы структуры располагаются в памяти последовательно друг за другом. Для обращения испольщуется операция. или ->

 

Union – объединение

Unionname

{

Char …;

Int …;

…

…

}

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