Стек. Реализация 5 (на основе указателя на указатель).

У Реализации 4 есть существенный недостаток. Допустим, что стек создан внутри некоторой функции и требуется использовать его вне данной функции. Тогда у нас есть единственная возможность осуществить данную реализацию, это - сделать переменную st4 глобальной или локальной статической. В противном случае, при выходе из данной функции переменная st4 утратит свое существование и указателями st4[0], st4[1] уже нельзя будет пользоваться. Но, как уже писалось, подобный способ реализации является дурным стилем.

Собственно, вся наша проблема состоит в том, что память под переменную st4 отводится и очищается автоматически. В качестве альтернативы, отведение/очистку памяти под указатели можно взять на себя. Для этого следует использовать указатель на указатель на целую переменную:

int **st5;

Функция создания стека не более чем из n элементов может выглядеть, в простейшем случае, следующим образом

int ** StackCreate5(int n)

{int **st; st = (int**)malloc(2*sizeof(int*));

st[1]= st[0] = (int*)malloc(n*sizeof(int));

}

а ее вызов будет выглядеть так: st5=StackCreate5(n);

Теперь переменная st5 может быть локальной и если ее вернуть из функции, то содержимое стека не будет потерянным. Очистку стека можно произвести с помощью следующей функции

void StackDelete5(int **st) { free(st[0]); free(st);}

а ее вызов будет выглядеть так: StackDelete5 (st5);

Если мы хотим уменьшить накладные расходы при отведении памяти и ускорить создание/уничтожение стека, то имеет смысл изменить несколько скорректировать функции StackCreate5 и StackDelete5. Действительно, память можно отвести всего один раз. Размер отведенной памяти должен быть достаточен для хранения (последовательно) массива из двух указателей и для массива из n элементов стека. В таком случае функции отведения/освобождения памяти могут выглядеть следующим образом

int ** StackCreate5x(int n)

{int **st; st = (int**)malloc(2*sizeof(int*)+ n*sizeof(int));

st[1]= st[0] = (int*)(st+2);

}

void StackDelete5x(int **st) {free(st);}

Очередь.

Очередью называется структура данных, организованная по принципу FIFO – first-in, first-out, т.е. элемент, попавшим в множество первым, должен первым его и покинуть. При практическом использовании часто налагается ограничение на длину очереди, т.е. требуется, чтобы количество элементов не превосходило N для некоторого целого N.

Создание исполнителя очередь предполагает наличие следующих функций

Ø инициализация

Ø добавление элемента в конец очереди

Ø взятие/извлечение элемента с начала очереди

Ø проверка: пуста ли очередь?

Ø очистка очереди

Обычно, используется реализация циклической очереди. Т.е. под очередь отводится некоторый непрерывный кусок памяти (массив) и при подходе хвоста очереди к концу массива хвост автоматически перебрасывается на противоположный конец массива. Например, для реализации стандартной очереди из менее чем 100 целых чисел на базе массива в языке С следует определить следующие данные

#define N 100

int array[N], begin=N-1,end=N-1;

Было бы логичным объединить все эти данные в единую структуру:

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