Очередь #4

Доброго всем вечера.

В этой статья, как и обещал, я опишу что есть из себя очередь, ей структуру и ее реализацию на С++ в конце статьи. Вот предыдущая статья о стеке.

По сути, очередь почти не отличается от стека — это все тот же односвязный список. Все его отличие заключается в способе добавления и удаления элемента.

Основной принцип очереди:»Первый пришёл — первый вышел» (или FIFO, First In — First Out). Проще всего себе представить очередь очередью (извините за тавтологию) в магазин:

Очередь, связный список

 

То есть, тот, кто пришел первым в магазин и уйдет из него первым (правда просто? 🙂 ). В этом и заключается смысл очереди.

Теперь поговорим о его представлении в памяти. Элементы очереди добавляются всегда! справа от хвоста (самый крайний правый элемент), а это значит, что каждый раз создается новый хвост.

А вот выталкивается (извлекается из списка, помним про pop?) элемент  всегда! с головы (элемент который находится «слева»). Наглядная структура очереди:

queue (2)

Вот и все. Теперь перейдем к реализации очереди средствами С++.

Код класса очереди содержит те же самые методы, что и класс стека: pop, push и peek. Однако, было добавлено одно поле tail (хвост). Это поле хранит адрес хвоста очереди. А вот и сам код:

#include<iostream>

using namespace std;

class queue //Класс очереди
{
private:
	struct queue_ob// Структура для хранения элементов очереди
	{
		int value;//Поле для хранения значения элемента очереди
		queue_ob *addr; // Поле для хранения слеющего элемента
	};

	queue_ob *head; // указатель, хранящий адресс головы очереди
	queue_ob *tail; // Указатель хранящий адрес хвоста
	int size; //Текущий размер очереди

public:
	queue(int x)// Конструктор класса
				//В параметр передается голова очереди
	{
		head=new(queue_ob); //Выделяем память под элемент
		tail=head; // При создании очереди хвост и голова являются одним и тем же элементом
		head->value=x; // Записываем значение
		head->addr=0; // Адрес ноль, так как следующего элемента пока нет
		size=1; // После выделения памяти и заполянения полей структуры очередь стала иметь размер 1
	}

	int stack_size()//Функция возвращает размер очереди(кол-во элеменетов)
	{
		return size;
	}

void push(int value)// Добавляет(вталкивает) элемент в очередь
{
	size++;// Кол-во элементов очереди увеличивается
	queue_ob *temp=new(queue_ob); // Выделяем память под новый хвост очереди
	temp->addr=0; // Записываем в поле адреса нового хвоста ноль, так как за ничего нету
	temp->value=value; //Заполняем поле значения нового хвоста
	tail->addr=temp; // Записываем в поле адреса старого хвоста адрес нового хвоста
	tail=temp; //Записываем в указель хвоста адрес действительного хвоста
}

void pop(int *ret)//Удаляет элемент(выталкивает) и возвращает его
				 // По адресу, хранящемся в ret, передается значение удаляемой головы
{
	if(size == 0)
	{
		cout<<"Очередь пуста - удалять нечего!"<<endl;
		return;
	}

	queue_ob *temp=head; // записываем адрес головы
	*ret=head->value; // записываем значени головы
	head=head->addr; // изменяем адрес головы
	delete temp;  // удаляем старую голову
	size--; // уменьшаем размер
}

void peek(int *ret)//Выгружает значение по адресу, передаваемому в парметре
{
	if(size == 0) // Если очередь пуста(size == 0), то ничего не выгружает
		{
			cout<<"Очередь пуста!"<<endl;
			return;
		}
	*ret=head->value;// Выгружаем значение головы
}

};// Конец класса очереди

Каждая строка кода комментирована, думаю,  что дополнительно описывать алгоритм смысла нет. Но если есть какие-то вопросы, то я обязательно на них отвечу.

А вот пример кода использования класса в мейне:

int main()
{
	system("chcp 1251");
	int b;
	queue a(1); //Создлаем очередь и загружаем в очередь 1
	a.push(2); //Загружаем 2
	a.push(3); //Загружаем 3
	a.pop(&b); // В b выгружается 1
	a.pop(&b);  //В b выгружается 2

	cout<<b<<endl; // На экран выведится 2
	system("pause");

	return 0;
}

Единственное, что здесь стоит отметить — это строка system(«chcp 1251»). Она изменяет текстовую кодировку консоли, что позволяет корректно отображать кириллицу (Статья о корректном отображении кириллицы).

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

До новых встреч.

Поддержать сайт и автора: Z208212694629
R429062753687
Яндекс деньги - https://money.yandex.ru/to/410013974912682

Подпишись:
На мой канал youtube
На рассылку свежих статей
На группу ВК
На группу в ОК

Понравилась статья? Поделись с друзьями)

Опубликовать в Google Buzz
Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники

Очередь #4: 1 комментарий

  1. Уведомление: Двусвязный список #5 | Всего наилучшего — 73!

Добавить комментарий