Очередь

Очередь – структура данных с дисциплиной доступа к элементам «первый пришёл – первый вышел» (FIFO, First In – First Out). В очереди доступны два элемента (две позиции): начало и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала. Примером может служить обыкновенная очередь в магазине.

Рис. Очередь

Описание очереди выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле1;

адресное поле2;

};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

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

Например:

1 способ: адресное поле ссылается на объявляемую структуру.

struct list2 {

type pole1;

list2 *pole1, *pole2;

}

2 способ: адресное поле ссылается на ранее объявленную структуру.

struct list1 {

type pole1;

list1 *pole2;

}

struct ch3 {

list1 *beg, *next ;

}

В очереди добавление осуществляется в один конец, а удаление из другого конца. Для очереди можно определять функции:

· доступ к первому элементу;

· доступ к последнему элементу;

· добавление элемента в начало;

· удаление элемента из конца.

Пример 3. Основные функции над элементами очереди.

#include <iostream.h>

#include <stdlib.h>

struct Node {//описание структуры очереди

int number; //информационное поле

Node* last; //указатель на первый элемент

Node* next; //указатель на следующий элемент

};

void main() {

Node* head = NULL;

Node* tail = NULL;

Node* ptrLast = NULL;

short action = -1;

while(1) {

cout << "1. Добавить Элемент\n";

cout << "2. Просмотр Очереди\n";

cout << "3. Удалить Элемент\n";

cout << "4. Поиск Элемента\n";

cout << "0. Выход\n\n";

cout << "Ваш Выбор: ";

cin >> action;

if (action == 0) break;

if (action == 1) {//добавление элемента в начало очереди

int numb = -1;

cout << "Введите Число: ";

cin >> numb;

Node* ptr = new (Node);

ptr->number = numb;

ptr->next = NULL;

tail = ptr;

if (head == NULL) {

head = ptr;

ptrLast = ptr;

ptr->last = NULL;

continue;

}

ptr->last = ptrLast;

ptrLast->next = ptr;

ptrLast = ptr;

continue;

}

if (action == 2) { //просмотр очереди

Node* ptr = NULL;

if (head == NULL) {

cout << "\t!!! ОЧЕРЕДЬ ПУСТА !!!\n\n";

continue;

}

cout << "* * * * * ОЧЕРЕДЬ * * * * *\n\n";

ptr = tail;

while (1) {

cout << ptr->number<<" ";

if (ptr->last == 0)

break;

ptr = ptr->last;

}

cout << "\n\n";

continue;

}

if (action == 3) {//удаление элемента из хвоста очереди

Node* ptrDelete = NULL;

if (head == NULL) {

//из пустой очереди элемент не удалить

cout << "\t!!! ОЧЕРЕДЬ ПУСТА !!!\n\n";

continue;

}

if (head->next == NULL){

head = NULL;

tail = NULL;

delete (tail);

continue;

}

ptrDelete = head;

head = ptrDelete->next;

head->last = NULL;

delete (ptrDelete);

continue;

}

if (action == 4) {//поиск элемента в очереди

Node* ptr = NULL;

int key = -1;

if (head == NULL) {//в пустой очереди элементов нет

cout << "\t!!! СПИСОК ПУСТ !!!\n\n";

continue;

}

cout << "Введите Элемент Для Поиска: ";

cin >> key;

ptr = head;

while (1) {

if (key == ptr->number) {

cout << "\n\t!!! ЭЛЕМЕНТ НАЙДЕН !!!\n";

break;

}

if (ptr->next == NULL){

cout << "\n\t!!! ЭЛЕМЕНТ НЕ НАЙДЕН !!!\n";

break;

}

ptr = ptr->next;

}

continue;

}

if (action > 4){

cout << "\t!!! НЕВЕРНЫЙ ВЫБОР. ПОВТОРИТЕ ВВОД !!!\n\n";

continue;

}

}

}

Перед компиляцией кода в среде MSVC++ необходимо в меню Options/Project отключить режим Use Microsoft Foundation Classes.

Задания

1.Наберите коды программ из Примеров 2 и 3. Выполните компиляцию и запуск программ.

2.Опишите стек с целочисленным информационным полем. Заполните его длинами строк, считанных из файла. Распечатайте на экране содержимое стека. Укажите номер и длину последней самой короткой строки файла.

3.Разработайте программу, с помощью которой можно определить наибольший допустимый размер очереди с вещественным информационным полем. Найдите этот размер (число элементов в очереди).

Домашние задания

1.Наберите код программы из Примера 1. Выполните компиляцию и запуск программы.

2.Опишите очередь с вещественным информационным полем, и заполните ее элементами с клавиатуры. Выполните циклический сдвиг элементов в очереди так, чтобы в ее начале был расположен наибольший элемент.

3.Разработайте программу, с помощью которой можно определить наибольший допустимый размер стека с вещественным информационным полем. Найдите этот размер (число элементов в стеке). Сравните с наибольшим допустимым размером очереди с аналогичным информационным полем.