У рачунарској науци, ред је линеарна структура података у којој се компоненте стављају на један крај и уклањају са другог краја према принципу „први ушао, први изашао“ (ФИФО). Ова структура података се може користити за контролу низа акција или складиштење података. Ц је рачунарски језик са могућношћу чекања у реду укљученим у облику низова или повезаних листа.
греибацх нормална форма
карактеристике:
- Ред је врста линеарне структуре података која се може конструисати помоћу низа или повезане листе.
- Елементи се премештају у задњи део реда док се уклањају са предње стране.
- Стављање у ред (додавање елемента позади) и декуеуе (уклањање елемента са предње стране) су две операције реда.
- Када се елементи често додају и уклањају, ред се може изградити као кружни ред како би се спречило трошење меморије.
Коришћење низа:
Да бисте имплементирали ред у Ц користећи низ, прво дефинишите максималну величину реда и декларишете низ те величине. Предњи и задњи цели бројеви су постављени на 1. Предња променљива представља предњи елемент реда, а задња променљива представља задњи елемент.
Пре него што гурнемо нови елемент на коначну позицију реда, потребно је да повећамо променљиву уназад за 1. Ред је сада пун и ниједан други додатни елемент се не може додати када задња позиција достигне максимални капацитет реда. Додамо елемент на почетак реда и повећавамо променљиву фронта за један само да бисмо уклонили елемент из реда. Ако су предња и задња позиција једнаке и ниједна компонента се више не може избрисати, можемо рећи да је ред празан.
Испод је пример реда написаног у Ц-у који користи низ:
Ц програмски језик:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Излаз кода ће бити:
Излаз:
10 20 30 Queue is empty-1
Објашњење:
срећно
- Прво, стављамо у ред три елемента 10, 20 и 30.
- Затим уклањамо из реда и штампамо предњи елемент реда, а то је 10.
- Затим поново стављамо у ред и штампамо предњи елемент реда, а то је 20.
- Затим поново стављамо у ред и штампамо предњи елемент реда, а то је 30.
- Коначно, правимо декуеуе из празног реда који даје 'Ред је празан' и враћа -1.
Коришћење повезане листе:
Други алтернативни приступ конструисању реда у програмском језику Ц је коришћење повезане листе. Сваки од чворова у реду се изражава помоћу ове методе помоћу чвора који садржи вредност елемента и показивач на следећи чвор у реду. Да би се пратили први и последњи чворови у реду, користе се предњи и задњи показивачи.
вредност стринга јава
Успостављамо нови чвор са вредношћу елемента и постављамо његов следећи показивач на НУЛЛ да бисмо додали елемент у ред. На нови чвор постављамо предњи и задњи показивач ако је ред празан. Ако није, ажурирамо задњи показивач и постављамо следећи показивач старог задњег чвора да показује на нови чвор.
Приликом брисања чвора из реда, претходни чвор се прво брише, затим се предњи показивач ажурира на следећи чвор у реду, а на крају се ослобађа меморија коју је уклоњени чвор заузимао. Ако је предњи показивач НУЛЛ након уклањања, ред је празан.
Ево примера реда који је имплементиран у Ц помоћу повезане листе:
Ц програмски језик:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Излаз кода ће бити:
Излаз:
архитектура пролећне чизме
10 20 30 Queue is empty-1
Објашњење:
- Прво, стављамо у ред три елемента 10, 20 и 30.
- Затим уклањамо из реда и штампамо предњи елемент реда, а то је 10.
- Затим поново стављамо у ред и штампамо предњи елемент реда, а то је 20.
- Затим поново стављамо у ред и штампамо предњи елемент реда, а то је 30.
- Коначно, покушавамо да избацимо из реда из празног реда, што штампа поруку 'Ред је празан' и враћа -1.
Предности:
- Редови су посебно корисни за имплементацију алгоритама који захтевају да се елементи обрађују у прецизном низу, као што је претрага у ширину и распоређивање задатака.
- Пошто операције реда имају О(1) временску сложеност, могу се брзо извршити чак и на огромним редовима.
- Редови су посебно флексибилни јер се могу једноставно имплементирати помоћу низа или повезане листе.
Недостаци:
- Ред, за разлику од стека, не може се конструисати са једним показивачем, што чини имплементацију реда мало сложенијом.
- Ако је ред конструисан као низ, могао би се ускоро попунити ако се дода превише елемената, што доводи до проблема са перформансама или могућег пада.
- Када се користи повезана листа за имплементацију реда, меморија над сваким чвором може бити значајна, посебно за мале елементе.
Закључак:
Апликације које користе редове, кључну структуру података, укључују оперативне системе, умрежавање и игре, да споменемо само неке. Они су идеални за алгоритме који морају руковати елементима одређеним редоследом јер их је једноставно креирати помоћу низа или повезане листе. Међутим, редови имају недостатке које се морају узети у обзир када се бира структура података за одређену апликацију, као што су потрошња меморије и сложеност имплементације.