Стекови и редови

Велики број реалних проблема захтева коришћење структура података као што су стекови и редови. Типичан пример коришћења стекова је стек који програмски језик користи да би имплементирао позивање функција и повратак из њих. Са друге стране, једна од најчешћих примена редова је ред за управљање редоследом процеса које је потребно извршити. Обе ове структуре података су у форми листе, тако да је за њихову имплементацију могуће искористити низове или повезане листе.

Стекови

Стекови (енглески stack) су листе елемената у којима је могуће додавање и одузимање елемената само на једном крају, који се назива врх стека. То практично значи да се елементи са стека уклањају обрнутим редоследом у односу на редослед којим су додавани на стек. Из тог разлога се ова структура података често назива и LIFO, што је скраћеница од енглеских речи Last In First Out (Последњи унутра први напоље). Операција додавања елеманта на стек се најчешће назива Push (гурнути), док се операција скидања елемента са стека назива Pop (скинути).

Стек можемо замислити као цев затворену на једном крају у коју се на другом крају додају куглице које представљају елементе (Slika 1). Приликом вађења куглица из цеви увек морамо прво извадити ону куглицу која је последња убачена у цев и тако редом. Куглица која је прва убачена у цев биће последња извађена.

Слика 1. Шематски приказ додавања и скидања елемената са стека

Слика 1. Шематски приказ додавања и скидања елемената са стека

С обзиром да су стекови у основи листе, они се могу реализовати коришћењем низова или повезаних листа.

Реализација стека помоћу низа

Када се за реализацију стека користи низ, операције додавања и скидања елемената са стека се реализују коришћењем основних операција над низом. Ограничење реализације помоћу низа је немогућност проширења и скраћења низа у зависности од броја елемената на стеку.

За реализацију стека користи се низ константе величине, која мора бити довољна да се у њу смести максималан број елемената који се у једном тренутку може наћи на стеку. Поред тога, у сваком тренутку је неопходно знати број елемената на стеку или индекс елемента на врху стека. Индекс -1 означава да је стек празан. Приликом додавања елемента на стек, повећава се индекс врха стека и на ту позицију у низу уписује нови елемент. Супротно, приликом скидања елемента са стека умањује се индекс врха стека.

Пример:

#include <stdio.h>
#define MAX 100 /* Maksimalna velicina steka */
#include <stdlib.h>
void push(int stack[], int *top, int value)
{
	if( *top < MAX )
	{		*top = *top + 1;		stack[*top] = value;	}
	else
	{printf("Stek je pun i ne moze da primi novu vrednost.\n");	exit(0);	}
}
void pop(int stack[], int *top, int *value)
{
	if( *top >= 0 )
	{		*value = stack[*top];		*top=*top-1;	}
	else
{printf("Stek je prazan i ne moze se skinuti vrednost sa njega.\n");exit(0);	}
}

void main()
{
	int stack[MAX];int top=-1;int n,value;
	do
	{
		do
		{
			printf("Unesite element koji zelite da dodate na stek:\n"); 
			scanf("%d",&value);
			push(stack,&top,value);
			printf("Unesite 1 za dodavanje novog elementa na stek:\n");
			scanf("%d",&n);
		} while(n == 1);
		printf("Unesite 1 za skidanje elementa sa steka:\n");
		scanf("%d",&n);
		while( n == 1)
		{
			pop(stack,&top,&value);
			printf("Skinuta vrednost je %d\n",value);
			printf("Unesite 1 za skidanje elementa sa steka:\n");
			scanf("%d",&n);
		}
		printf("Unesite 1 za dodavanje novog elementa na stek:\n");
		scanf("%d",&n);
	} while(n == 1);
}

Претходни пример садржи функције push и pop за додавање и скидање елемента са стека. У главном програму омогућено је додавање и скидање елемената са стека произвољан број пута одабиром одговарајућих команди. У овом случају стек је ограничене дужине.

Реализација стека помоћу листе

Стек се може веома ефикасно реализовати коришћењем повезаних листа тако што би се нови елемент додавао увек на почетак листе. Такође, у случају скидања елемента са стека скидао би се увек први елемент у листи, односно онај који је последњи додат.

На почетку, листа је празна, па је и показивач на почетак листе (top) једнак NULL. Функција push узима показивач на постојећу листу као први параметар и вредност коју треба додати као други параметар, креира нови елемент и додаје га на почетак листе. Функција pop узима показивач на почетак листе као први параметар и показивач на променљиву у коју ће сместити вредност скинутог елемента као други параметар. Након тога, функција враћа вредност првог елемента у листи и помера показивач top на следећи елемент у листи. На крају се уништава елемент који је био на почетку листе.

На Слици 2 приказан је изглед стека представљеног повезаном листом приликом додавања и скидања елемената следећим редоследом: Push(5), Push(8), Pop(), Push(2), Push(7), Pop().

Слика 2. Шематски приказ додавања и скидања елемената са стека представљеног повезаном листом

Слика 2. Шематски приказ додавања и скидања елемената са стека представљеног повезаном листом

Пример:

# include <stdio.h>
# include <stdlib.h>
struct node
{
	int data;
	struct node *link;
};
struct node* push(struct node *p, int value)
{
	struct node *temp;
	/* kreiranje novog cvora koriscenjem prosledjene vrednosti */
	temp=(struct node *)malloc(sizeof(struct node));
	if(temp==NULL)
	{		printf("Greska pri alociranju memorije.\n");		exit(0);}
	temp->data=value;
	temp->link=p;
	p = temp;
	return(p);
}
struct node* pop(struct node *p, int *value)
{
	struct node *temp;
	if(p==NULL)
	{		printf("Greska. Stek je prazan.\n");		exit(0);	}
	*value=p->data;
	temp = p;
	p=p->link;
	free(temp);
	return(p);
}

void main()
{
	struct node *top = NULL;
	int n,value;
	do
	{
		do
		{
		printf("Unesite element koji zelite da dodate na stek:\n");
		scanf("%d",&value);
		top = push(top,value);
		printf("Unesite 1 za dodavanje novog elementa na stek:\n");
		scanf("%d",&n);
		} while(n == 1);
		printf("Unesite 1 za skidanje elementa sa steka:\n");
		scanf("%d",&n);
		while( n == 1)
		{
			top = pop(top,&value);
			printf("Skinuta vrednost je %d\n",value);
			printf("Unesite 1 za skidanje elementa sa steka:\n");
			scanf("%d",&n);
		}
		printf("Unesite 1 za dodavanje novog elementa na stek:\n");
		scanf("%d",&n);
	} while(n == 1);
}

Редови

Редови (енглески queue) су листе елемената у којима се елементи додају на једном крају листе, који се назива крај реда, а одузимају се на другом крају листе, који се назива почетак реда. То практично значи да се елементи са реда уклањају истим редоследом као што су и додавани на ред. Из тог разлога се ова структура података често назива и FIFO, што је скраћеница од енглеских речи First In First Out (Први унутра први напоље). Операција додавања елеманта у ред се најчешће назива Insert (убацити), док се операција брисања елемента из реда назива Delete (обрисати). Ред можемо замислити као цев отворену на оба краја у коју се на једном крају убацују куглице које представљају елементе (Слика 3). Приликом вађења куглица из цеви увек се прво вади куглица која је прва убачена у цев и тако редом. Куглица која је последња убачена у цев биће последња извађена. Управо овој особини редови дугују свој назив, јер подсећају на чекање у реду где се прво услужују они који су први стигли.

Слика 3. Шематски приказ убацивања и брисања елемената из реда

Слика 3. Шематски приказ убацивања и брисања елемената из реда

С обзиром да су стекови у основи листе, они се могу реализовати коришћењем низова или повезаних листа.

Реализација реда помоћу низа

Када се за реализацију реда користи низ, операције додавања и брисања елемената из реда се реализују коришћењем основних операција над низом. Ограничење реализације помоћу низа је немогућност проширења и скраћења низа у зависности од броја елемената у реду. За реализацију реда користи се низ константе величине, која мора бити довољна да се у њу смести укупан број елемената који се додају у ред, без обзира на то колико је њих обрисано из реда. Поред тога, у сваком тренутку је неопходно знати индексе првог и последњег елемента у реду. Индекси -1 означавају да је ред празан. Приликом додавања елемента у ред, повећава се индекс последњег елемента и на ту позицију у реду уписује се нови елемент. У случају брисања елемента из реда, повећава се индекс првог елемента у реду. Могућа је и другачија имплементација која би захтевала само онолику величину низа колико је потребно да се сместе елементи који су у једном тренутку у реду, међутим таква реализација захтева стално померање преосталих елемената приликом брисања првог елемента из реда. У овом случају ред је ограничене дужине.

#include <stdio.h> 
#define MAX 100 /* Maksimalna velicina reda */ 
#include <stdlib.h> 
 
void insert(int queue[], int *rear, int value) 
{ 
if(*rear < MAX‐1) 
{ 
*rear= *rear +1; 
queue[*rear] = value; 
} 
else 
{ 
printf("Red je pun. Ne moze se dodati vrednost.\n"); 
exit(0); 
} 
} 
 
void delete(int queue[], int *front, int rear, int * value) 
{ 
if(*front == rear) 
{ 
printf("Red je prazan. Ne moze se obrisati vrednost.\n"); 
exit(0); 
} 
 
*front = *front + 1; 
*value = queue[*front]; 
} 
 
 
void main() 
{ 
int queue[MAX]; 
int front,rear; 
int n,value; 
front=rear=(‐1); 
 
do 
{ 
do 
{ 
printf("Unesite element koji zelite da dodate u red:\n"); 
scanf("%d",&value); 
 
insert(queue,&rear,value); 
 
printf("Unesite 1 za dodavanje novog elementa u red:\n"); 
scanf("%d",&n); 
} while(n == 1); 
 
printf("Unesite 1 za brisanje elementa iz reda:\n"); 
scanf("%d",&n); 
 
while( n == 1) 
{ 
delete(queue,&front,rear,&value); 
printf("Obrisana vrednost je %d\n",value); 
 
printf("Unesite 1 za brisanje elementa iz reda:\n"); 
scanf("%d",&n); 
} 
 
printf("Unesite 1 za dodavanje novog elementa u red:\n"); 
scanf("%d",&n); 
 
} while(n == 1); 
}

Реализација реда помоћу листе

Ред се може веома ефикасно реализовати коришћењем повезаних листа тако што би се нови елемент додавао увек на крај листе. Такође, у случају брисања елемента из реда скидао би се увек први елемент у листи, односно онај који је први додат.

На почетку, листа је празна, па су и показивачи на почетак и крај листе (front и rear) једнаки NULL. Функција insert креира нови елемент и додаје га на крај листе. Функција delete враћа вредност првог елемента у листи и помера показивач front на следећи елемент у листи. На крају се уништава елемент који је био на почетку листе. На Слици 4 приказан је изглед реда представљеног повезаном листом приликом додавања и брисања елемената следећим редоследом: Insert(5), Insert(8), Delete(), Insert(2), Insert(7), Delete().

Слика 4. Шематски приказ додавања и брисања елемената из реда представљеног повезаном листом

Слика 4. Шематски приказ додавања и брисања елемената из реда представљеног повезаном листом

# include <stdio.h> 
# include <stdlib.h> 
 
struct node 
{ 
int data; 
struct node *link; 
}; 
 
void insert(struct node **front, struct node **rear, int value) 
{ 
struct node *temp; 
 
/* kreiranje novog cvora koriscenjem prosledjene vrednosti */ 
temp=(struct node *)malloc(sizeof(struct node)); 
if(temp==NULL) 
{ 
printf("Greska pri alociranju memorije.\n"); 
exit(0); 
} 
 
temp‐>data = value; 
temp‐>link=NULL; 
 
if(*rear == NULL) 
{ 
*rear = temp; 
*front = *rear; 
} 
else 
{ 
(*rear)‐>link = temp; 
*rear = temp; 
} 
} 
 
void delete(struct node **front, struct node **rear, int *value) 
{ 
struct node *temp; 
 
if((*front == *rear) && (*rear == NULL)) 
{ 
printf("Red je prazan. Ne moze se obrisati vrednost.\n"); 
exit(0); 
} 
 
*value = (*front)‐>data; 
temp = *front; 
*front = (*front)‐>link; 
 
if(*rear == temp) 
*rear = (*rear)‐>link; 
 
free(temp); 
} 
  
void main() 
{ 
struct node *front=NULL,*rear = NULL; 
int n,value; 
 
do 
{ 
do 
{ 
printf("Unesite element koji zelite da dodate u red:\n"); 
scanf("%d",&value); 
 
insert(&front,&rear,value); 
 
printf("Unesite 1 za dodavanje novog elementa u red:\n"); 
scanf("%d",&n); 
} while(n == 1); 
 
printf("Unesite 1 za brisanje elementa iz reda:\n"); 
scanf("%d",&n); 
 
while( n == 1) 
{ 
delete(&front,&rear,&value); 
printf("Obrisana vrednost je %d\n",value); 
 
printf("Unesite 1 za brisanje elementa iz reda:\n"); 
scanf("%d",&n); 
} 
 
printf("Unesite 1 za dodavanje novog elementa u red:\n"); 
scanf("%d",&n); 
 
} while(n == 1); 
}

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се /  Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се /  Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се /  Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се /  Промени )

Повезивање са %s