Информационни технологии & Интернет

В настоящата курсова работа ще бъде представена абстрактната структура опашка и ще бъде представена примерна нейна реализация. Кодът представен в този реферат е написан от автора и се компилира успешно с Dev-C++ 4.9.9.2.

Опашка в C++

Опашката е линейна структура от данни, чиито елементите са свързани последоватерно. Тя има начало и край. Елемнтите на опашката се въвеждат в нейния край, а се изваждат от нейното начало. При опашката се спазва правилото “пръв влязъл, пръв излязъл”. Тоест елемнтите ще бъдат извадени в реда, в който са въведени в опашката.

Реализация на опашка

Има два начина за реализиране на опашка – статичен и динамичен. При статичния опашката има ограничен брой елемнти, докато при динамичния може да има неограничен брой елементи в рамките на паметта. В настоящата курсова работа ще бъде реализилана статична опашка.
Статичната реализация ще бъде осъществена посредством масив, който ще съдържа елементите на опашката. Масивът ще е член на клас, който ще има и член данни за позицията на началото и края на опашката в масива. Ще има и булева член променлива, която ще носи информация за това дали опашката е празна.

Ето и кода:

#include <iostream>
using namespace std;
#define MAX 500

class Queue{
private:
int Elem[MAX];
int front,rear;
bool empty;
public:
Queue();
~Queue();
void PUT(int a);
int GET(void);
};

Queue::Queue()
{
front=rear=0;
empty = true;
}

Queue::~Queue()
{
front=rear=0;
empty = true;
}

void Queue::PUT(int a)
{
if(front==rear && !empty)
{
cout<<”Opashkata e prepylnena! Elementyt ne e dobaven!\n”;
return;
}
Elem[rear]=a;
rear++;
if(rear>=MAX)
rear = 0;
empty = false;
}

int Queue::GET()
{
int x;
if(empty)
{
cout<<”Opashkata e prazna !\n”;
return 0;
}
x = Elem[front];
front++;

if(front>=MAX)
front=0;

if(front == rear)
empty = true;

return x;
}

Въху опашка се извършват основно две операции: Put и Get съответно за добавяне на елемент и за изваждане на такъв. Когато се добавя елемент трябва да се провери дали опашката е препълнена. Това ще се случи, когато променливата rear стане равна на front. Първата проверка в функцията PUT отговаря за предупреждение при препълване на опашката. Ако опашката не е препълнена се добавя елемента и за да се използва целия масив, ако rear е достигнал края на масива му задаваме стойност нула, за да се върне в началото.
При функцията GET се прави проверка, която установява дали опашката е празна. Ако е празна се предупреждава и се връща стойност нула. Ако не е празна се извлича елемент и отново, за да се използва циялия масив front става нула ако е достигнал до края на масива. Прави се и проверка, с която се установява дали след изваждането на елемнт опашката не е празна. Ако е така се променя стойността на променливата empty, за да се покаже, че опашката е празна.

Заключение

Представената реализация на опашка може да бъде използвана за решаване на задачи. Създадени са всички основни специфични за тази структура.
Опашките намират широко приложение в информатиката. Много алгоритми свързани с графи използват опашки, както и техни разновидности – приоритетни опашки. Процесорите например образуват опашки, с които подреждат инструкциите, които чакат да бъдат изпълнени.

Сходни статии:

1. Свързана опашка. Основни операции в C++ Указателят F сочи особен елемент със същата структура като останалите елементи в опашката, като в полето му link се съдържа указател към първия елемент на опашката. Празна опашка – F...
2. Програмиране в C и C++ Кодирането или съставянето на програмата е реализация на алгоритмите чрез език за програмиране. Езиците за програмиране от високо ниво, какъвто е и програмният език C, се характеризират със задължителни синтактични...
3. Пример за обектно – ориентирана реализация на свързан списък В примера се използва шаблон на класа List за обработка на списък от данни от цял тип и списък от данни с плаваща точка. Програма driver дава възможност да се...
4. Свързан стек. Основни операции typedef int INFO_TYPE; struct stack_el{ INFO_TYPE info; stack_el *link; }; //Функция за добавяне на елемент void push(stack_el **t, INFO_TYPE x) //Указателят към върха на стека трябва да се промени, затова...
5. Пример за обектно ориентирана реализация на свързан стек Ще се възползваме от тясната връзка между св. списъци и стекове чрез повторно използване на класа на списъците. Ще приложим 2 разновидности на повторното използване. Отначало ще реализираме класа на...