Структуры данных. Стек и очередь. Реализация стека, дека и очереди с помощью массива и списка.
Стеки - это множество элементов, сложенных в стопку. Например, у нас есть коробка 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 …;
…
…
}
Отличие объединения от структуры – все элементы объединения занимают одну память, размер памяти выделенный под объект объединения выделяется самым большим элементом данного объединения.