Опашка

1. Програмна реализация на опашка

2. Понятие за опашка

2.0. Реализация чрез масив

2.1. Реализация чрез линеен списък

1. Понятие за опашка

Опашката е крайно, линейно, наредено множество от елементи, при което елементите се добавят само в единият край, а се четат(изключват) само от другият край. Това означава,че се обработва на принципа FIFO(First Input First Output).

Подобно на стека прочетената стойност се изключва от опашката.

При работа с опашка се нуждаем от две променливи; едната да сочи началото(FE) и втора, която да сочи края (LE) на опашката.

2. Програмна реализация на опашка

2.1. Реализация чрез масив

Трябва да дефинираме масив А от N елемента и две променливи FE – която да сочи индекса на първият елемент(този, който ще се чете) от опашката и LE, която да сочи индекса на елемента от масива, където ще се записва(елемента след последния).

Тук възниква един проблем – след записване на N елемента в опашката, масивът ще се напълни и дори да прочетем всички записани елементи, FE и LE ще имат стойност N-1 и ще сочат последния елемент.

Този проблем се решава само посредством едно условие: Предполагаме, че след елемента A[N-1] следва елементът A[0]. На практика масивът се зацикля и в опашката може да се прави безкрайно четене и записване, стига броя на елементите в един момент да не е по-голям от N(размера на масива).

Когато индексът FE застигне индекса LE, то опашката е празна.

Когато индексът LE застигне индексът FE, то опашката е препълнена.

Имаме нужда от следните функции:

Ø Функция за четене;

Ø Функция за запис;

Ø Помощна функция за определяне на следващият индекс за четене;

Ø Помощна функция за определяне на следващата функция за запис;

Ø Функция за изпразване на опашката;

Опашка реализирана с масив

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#define N 100 //размер на масива

float A[N]; //дефиниция на масива

int Flag_Empty=1; //флаг за празен списък ( 1 - празен, 0 - не е празен )

int Flag_Full=0; //флаг за препълнен списък ( 1 - препълнен, 0 - не е препълнен )

int FE=0, //индекс на първия елемент от опашката

LE=0; //индекс на последния елемент от опашката

//ф-я, която изчислява следващия индекс за последен елемент в опашката

void next_LE()

{

if(LE==N-1) LE=0; //ако LE сочи последния елемент от масива,

//то следващата му стойност е първия (индекс 0)

else LE++; //в противен случай просто си увеличава стойността с 1

if (LE==FE) Flag_Full=1; //ако LE настигне FE - препълване на опашката

else Flag_Full=0;

Flag_Empty=0; //опашката не е празна

}

//ф-я, която изчислява следващия индекс за първи елемент в опашката

void next_FE()

{

if(FE==N-1) FE=0; //ако FE сочи последния елемент от масива,

//то следващата му стойност е първия (индекс 0)

else FE++; //в противен случай просто си увеличава стойността с 1

if (FE==LE) Flag_Empty=1; //ако FE настигне LE - опашката става празна

else Flag_Empty=0; //опашката не е препълнена

}

//ф-я, за записване на стойност х в опашката

void WriteQueue (float x)

{

if(Flag_Full) cout <<"Опашката е препълнена\n";

else { A[LE]=x; //добавя се (записва се) новият елемент към опашката

next_LE(); //изчислява следващата стойност за LE

}

}

//ф-я, за четене на стойност от опашката

void ReadQueue ()

{

if(Flag_Empty) cout<<"\nОпашката е празна\n ";

else { cout<<"x="<<A[FE]<<'\n'; //извежда съдържанието на първия елемент от опаката

next_FE(); //изчислява следващата стойност за FE

}

}

//ф-я, която изпразва опашката

void EmptyQueue ()

{

FE=LE=0; //индексите за първи и последен елемент сочат 0-вия

// елемент на масива

Flag_Empty=1; //флага за празна опашка има стойност 1( да)

Flag_Full=0; //флага за препълване на опашката има стойност 0( не )

}

//ф-я, която показва съдържанието на опашката

void ShowQueue ()

{ int i;

cout<<" В опашката са записани следните стойности:\t";

if(LE>=FE) //ако индекса на последния елемент е по-голам от

//индекса на първия -

for(i=FE;i<LE;i++) //извеждат се елементите от FE до LE

cout<<A[i]<<' ';

else //в противен случай

{

for(i=FE;i<N;i++) // се извеждат елементите от FE до края на масива

cout<<A[i]<<' ';

for(i=0;i<LE;i++) // и след това от началото на масива до LE

cout<<A[i]<<' ';

}

}

//главна ф-я на програмата

void main(void)

{

int i;

float x;

for(;;)

{

cout<<"1.Запис в опашката\n";

cout<<"2.Четене от опашката\n";

cout<<"3.Изпразване на опашката\n";

cout<<"4.Край\n";

cout<<"Изберете команда (от 1 до 4) ";cin>>i;

switch(i)

{

case 1: cout<<"x=";cin>>x;

WriteQueue (x);

break;

case 2: ReadQueue ();

break;

case 3: EmptyQueue ();

break;

case 4: exit(0);

}

ShowQueue ();

}

}

2.2.Реализация чрез линеен списък

Имаме нужда от два указателя: FE(към първият елемент от списъка) и LE(към последният елемент от списъка).

Неждаем се само от функция за добавяне на елемент в края на списъка и от функция за изключване на елемент от началото на списъка.

В този случай опашката не може да се препълни, т.к. тя няма ограничен обем. Но е възможно да се изчерпи оперативната памет.

Опашката е празна, когато нито един елемент в линейният списък, т.е. FE=NULL и LE=NULL.

За реализацията на този тип опашка се нуждаем още от :

Ø Структура, която да описва един елемент от опашката.

Опашка реализирана с линеен списък

Клас Queue

Опашката е динамична структура от данни, изградена на принципа FIFO (първи влязъл, първи излязъл). Тя може да бъде реализирана с помощта на линеен едносвързан списък, като се използват само член-функциите за добавяне в началото и изключване в края на списъка. За реализиране на структурата опашка съм създала класа Queue, наследник на класа LList. В него, като лични данни съм дефинирала указателите First и End, съответно за първи и последен елемент на опашката. В конструктора тези указатели се нулират. В деструктора се извиква член-функцията Clear(), която унищожава цялата опашка, освобождава заетата от нея памет и нулира указателите First и End.

Член-функцията Add() реализира добавяне на елемент към опашката. Тя има един аргумент от тип Node (указател към елемента, който ще се добавя). Тя извиква член-функцията на базовия клас Add_star()t, като й подава за аргументи указателят към новия елемент и адресите на указателите First и End.

Член функцията Remove изключва поредния елемент от опашката. В нея се извеждат данните на последния елемент и се извиква член-функцията Del_end() на базовия клас, за да унищожи този елемент. В случай, че опашката е празна (End=NULL), се извежда съобщение.

Програмната реализация е следната:

void Queue::Remove()

{

if(End)

{

End->output();

Del_end(&First,&End);

}

else cout<<"The Queue is empty.\n";

}

Член-функцията Clear() унищожава цялата опашка, освобождава заетата от елементите й памет и нулира указателите First и End.

Член-функцията OutList () извиква съответната член-функция на базовия клас за да изведе съдържанието на цялата опашка.

Дефиниция на класа Queue.

class Queue : public LList

{

Node *First,*End;

public:

Queue();

virtual ~Queue();

void Add(Node *el);

void Remove();

void Clear();

void OutList();

};

Дефиницията на класа Queue е съхранена във файл с името Queue.h, а дефинициите на член-функциите - във файл с името Queue.cpp.

QueueDemo

Програмата QueueDemo демонстрира възможностите на класа Queue. За целта съм създала главна функция main, в която съм дефинирала 2 обекта А и B от тип Stack. Във възлите на опашката А са разположени обекти от тип MyFloatList, а във възлите на опашката B са разположени обекти от тип MyCharList. Указателят elA е от тип MyFloatList, а elB – от тип MyCharList и се използват за съхраняване на адресите на новосъздадените елементи. Целочислената променлива k се използва за избор на точка от менюто.

В тялото на тази функция се извежда меню, състоящо се от 7 команди. Всяка една от командите се избира чрез нейния номер. Оператор switch осигурява изпълнението на избраното действие.

Безкраен цикъл for осигурява многократното извеждане на менюто. От програмата се излиза, като се въведе номера на командата End. За по-добра нагледност при всяко завъртане на цикъла се показва съдържанието на опашките.

Програмната реализация е следната:

void main()

{

Queue A,B;

MyFloatList *elA;

MyCharList *elB;

int k;

for(;;)

{

cout<<"\n1.Add to Queue A\n";

cout<<"2.Remove from Queue A\n";

cout<<"3.Add to Queue B\n";

cout<<"4.Remove from Queue B\n";

cout<<"5.Clear A\n";

cout<<"6.Clear B\n";

cout<<"7.End\n";

cout<<"Choice (1-5):";cin>>k;

switch(k)

{

case 1:elA=new MyFloatList; elA->input(); A.Add(elA); break;

case 2:cout<<"A: ";A.Remove();cout<<'\n'; break;

case 3:elB=new MyCharList; elB->input(); B.Add(elB); break;

case 4:cout<<"B: ";B.Remove();cout<<'\n'; break;

case 5:A.Clear(); break;

case 6:B.Clear(); break;

case 7:exit(0); break;

default:cout<<"Error!";

}

cout<<"A: ";A.OutList();

cout<<"B: ";B.OutList();

}

}

Главната функция е съхранена във файл с името QueueDemo.cpp. За да се компилира програмата е необходимо да се създаде файл-проект, в който да се включат файловете:

· QueueDemo.cpp

· List.cpp

· MyFloatList.cpp

· MyCharList.cpp.

Целият сорс можете да изтеглите от тук.