Очереди

Стек

Стек с максимальным объемом n элементов можно реализовать в виде массива, например S [0...n-1], и индекса последнего заполненного элемента массива top. Таким образом, значение top, равное 0, соответствует пустому стеку.

push (3) pop () pop ()

	Вершина стека				Вершина стека		Вершина стека
	5		5		5		5
	4				4
							3

top=4 top=5 top=4 top= 3

Реализация стека S в виде массива

Протестировать стек на наличие в нем элементов можно с помощью операции, которая сводится к проверке значения индекса top. Если элемент снимается с пустого стека (top=0), то возникает ошибка. Если значение top превосходит n-1, то стек переполняется.

Пример. Реализация стека с фиксированным количеством элементов.

#include <stdio.h>

int push (int *s,int d, int *top,int v){

if(*top==v)return 1;

s[*top]=d;

(*top)++;

return 0;

};

int pop (int *s,int *d, int *top){

if(*top==0)return 1;

(*top)--;

* d=s[*top];

return 0;

}

void main(){

const int v=5;

int s[v]={0};

int top=0,d,i,k;

for(i=0;i<6;i++)

push(s,i,&top,v);

printf("\n");

for(i=0;i<6;i++){

k=pop(s,&d,&top);

printf("%d ",d); }

}

Очереди

Способ реализации очереди не более чем из n -1 элементов при помощи массива Qu [0.. n-1 ]. Для реализации очереди используются две индексные переменные – top, указывающая первый элемент в очереди (который будет удален из нее очередной операцией out), и bottom, указывающая позицию, в которую будет добавляться новый элемент. Элементы очереди расположены в ячейках Qu[ top], Qu [top + 1], Qu [bottom – 1], которые циклически замкнуты в том смысле, что ячейка 0 следует сразу же после ячейки n-1 в циклическом порядке. При условии top = bottom очередь пуста. Изначально выполняется соотношение top = bottom = 0. если очередь пуста, то при попытке удалить из нее элемент происходит ошибка. Если же top%n = bottom %n, то очередь заполнена, и попытка добавить в нее элемент приводит к ее переполнению.

0 1 2 3 4 5 6 7 8 9

Head tail

0 1 2 3 4 5 6 7 8 9

8

Tail Head

0 1 2 3 4 5 6 7 8 9

Tail Head

Пример. Реализация очереди с помощью массива

#include <stdio.h>

#include <conio.h>

const int v=5;

int in (int *qu,int d, int top,int *bottom){

if((*bottom>top) && ((top%v)==(*bottom)%v)) return 1;

qu[*bottom%v]=d;

(*bottom)++;

return 0;

};

int out (int *qu,int *d, int *top,int bottom){

if(*top==bottom)return 1;

*d=qu[*top%v];

(*top)++;

return 0;

}

void main(){

int qu[v]={0};

int top=0,bottom=0,d,i,k;

in(qu,10,top,&bottom);

out(qu,&d,&top,bottom);

}

Дата добавления: 2015-07-10