Съществува още една, по-рядко използвана, разновидност на списък, която се явява обобщение на стек и опашка едновременно – това е дек (DEQue, съкращение от английското Double Ended Queue – опашка с два края). Както подсказва името й, при тази структура елементи могат да се включват и изключват в двата й края. От своя страна декът също има някои разновидности – възможно е включването да бъде позволено само от едната страна, а изключването – от двете (дек с ограничен вход) или обратно: включване от двете страни и изключване – от едната (дек с ограничен изход). Като цяло дековете не намират широко приложение, въпреки че в някои специални случаи (например при многопроцесорните системи) е удобно да се използва дек за различни задачи (пресмятане стойността на изрази и др.)
Последователна (статична) реализация. Ще реализираме структурите стек и опашка статично чрез масив. В случая със стек ще въведем единствен индекс, който ще сочи адреса на върха на стека. При операцията включване елементът ще се записва на адреса, сочен от индекса, след което индексът ще се увеличава с единица. При изключване индексът ще се намалява с единица, след което ще се извлича елементът. Ето как изглежда реализацията в програмния език С, при използване на масив stack[] от тип int и променлива top, която сочи върха на стека:
#include <stdio.h>
#define MAX 10
int stack[MAX];
int top;
void init(void)
{
top=0;
}
void push ( int i )
{
if (MAX==top)
fprintf(stderr, “Prepylvane na steka! \n”);
else
stack [ top++ ] = i;
}int pop(void)
{
if (0==top)
{
fprintf(stderr, “Stekyt e prazen! \n”);
return 0;
}
else
return stack [ --top ];
}
int empty(void)
{
return (0 == top);
}int main (void)
{
int p, r;
init();
scanf(“%d”, &p);
while (0 != p)
{
push(p);
scanf(“%d”, &p);
}
while ( !empty() )
printf(” %d “, pop() );
printf(“\n”);
return 0;
}
Реализацията на опашка е малко по-сложна. За последователното реализиране на памет отново ще използваме масив, но индексите ще бъдат два: front, който сочи началото на опашката и rear, който сочи позицията след края й.
Включването и изключването на елементи се осъществява по следния начин:
Включване на елемент i: Записваме i на позицията, сочена от индекса rear, и го увеличаваме с 1. Изключване на елемент: Вземаме елемента на позиция front, след което увеличаваме индекса front с 1.
При реализацията на включването и изключването трябва да се справим с няколко проблема. Основният е свързан с това, че опашката “се движи” в паметта: Ако многократно включваме и изключваме елементи, то индексите front и rear ще се увеличават непрекъснато и бързо ще надхвърлят първоначално заделената за опашката памет. Например ако използваме масив queue [MAX] (с фиксиран брой елементи), размерът му бързо ще се окаже недостатъчен, въпреки че на практика опашката ще съдържа по-малко от МАХ елемента. Затова, ако някой от двата индекса front или rear стане равен на MAX, ще му се присвоява стойност 0. Така постигаме “цикличност” на масива queue[].
В началото индексите front и rear сочат нулевия елемент. По нататък, ако в даден момент те отново се окажат равни (сочат една и съща клетка), това означава едно от двете: Ако равентството се е получило след изключване на елемент (индексът front е застигнал rear), то опашката е останала празна след извършване на операцията. Ако равенството се е получило след включване на елемент (rear е застигнал front), то опашката е препълнена – съдържа MAX елемента и повече не могат да се добавят. За статуса на опашката (дали тя е пълна или празна) ще използваме допълнителна променлива empty, равна на 1 ако опашката е празна и на 0 – в противен случай. Променливата empty се инициализира с 1 (в началото опашката е празна) и приема стойност 0 веднага след първото включване на елемент.
#include <stdio.h>
#define MAX 10
int queue[MAX];
int front, rear, empty;
void init(void)
{
front=rear=0;
empty=1;
}
void put ( int i )
{
if ( front == rear && !empty )
{
fprintf(stderr, “Prepylvane! \n”);
return;
}
queue[rear++] = i;
if (rear > MAX)
rear = 0;
empty = 0;
}int get (void)
{
int x;
if (empty)
{
fprintf(stderr, “Opashkata e prazna! \n”);
return 0;
}
x=queue[front++];
if ( front >= MAX ) front = 0;
if ( front == rear ) empty=1;
return x;
}int main (void)
{
int p;
int i;
init();
for (i=0; i<2*MAX; i++ )
{
put(i);
p=get();
printf(” %d “, p);
}
printf(“\n”);
return 0;
}
Сходни статии:
- Свързване на съобщения и методи в C++. Механизъм на «ранното» свързване Стартирането на метод като реакция на определено съобщение трябва да се извършва в съответствие с природата на обекта-получател на съобщението, независимо от това, че този метод може многократно да е...
- Най-хубавата дума в българския език автор: Ц. Миткова Kоя дума кара един българин да се развълнува? Коя дума кара сърцето ти да се разтупти, а ръцете ти да изтръпнат? България… звучи толкова величествено и силно,...
