Алгоритм извлечения элемента из стека

В данном алгоритме вершина begin не сдвигается.

1. Устанавливаем текущий указатель на вершину стека: t = begin;

2. Обрабатываем информационную часть текущего элемента (t -> info), например, выводим на экран.

3. Переставляем указатель текущего элемента на следующий элемент, адрес которого находится в адресной части текущего:

t = t->Next;

Просмотр стека

1. Устанавливаем текущий указатель на вершину t = begin.

2. Проверяем, если begin равен NULL, то стек пуст, выводим сообщение и либо завершаем работу, либо переходим на формирование стека.

3. Если стек не пуст, начинаем выполнять цикл до тех пор, пока текущий указатель t не равен NULL, т.е. пока не обработаем последний элемент, в адресной части которого находится значение NULL.

4. Выводим на экран информационную часть текущего элемента:

printf(“\n Элемент: %d”, t -> info); или cout << t->info;

5. Переставляем текущий указатель на следующий элемент:

t = t -> Next;

6. Конец цикла.

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

void View(Stack *begin)

{

Stack *t = begin;

if(begin == NULL) {

puts(“ Стек пуст! ”);

return;

}

while(t!= NULL) {

printf(“ %d \n”, t->info);

t = t -> Next;

}

}

Обращение к этой функции: View(begin);

 

Алгоритм освобождения памяти, занятой стеком

1. Начинаем цикл, выполняющийся пока begin не станет равным NULL.

2. Устанавливаем текущий указатель на вершину стека: t = begin;

3. Вершину стека переставляем на следующий элемент: begin = t->Next;

4. Уничтожаем текущий (бывшую вершину) элемент, т.е. освобождаем занятую под него память free (t);

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

void Delete_Stack(Stack **begin) {

Stack *t;

while(*begin!= NULL) {

t = *begin;

*begin = (*begin) -> Next;

free(t);

}

}

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

Delete_Stack(&begin);

if(begin == NULL)

puts(“ Free! ”);

...

Алгоритм проверки правильности расстановки скобок

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

При реализации алгоритма анализа исходное выражение просматривается слева направо.

1. Если в выражении обнаружена открывающаяся скобка, то анализируем содержимое стека:

а) если стек пуст или не пуст, но в вершине находится тоже открывающая скобка, то записываем ее в стек;

б) если стек не пуст и в вершине находится закрывающая скобка, то обе скобки выбрасываем из рассмотрения (находящуюся в стеке удаляем).

2. Если обнаружена закрывающая скобка и стек пуст, то выражение составлено неверно, выводим сообщение об этом и завершаем работу.

3. Просмотрев все выражение, проверяем стек и, если он не пуст, то баланс скобок нарушен и выражение составлено неверно, выводим сообщение об этом и завершаем работу.

По такому принципу работают все компиляторы, проверяя баланс круглых скобок в выражениях, баланс фигурных скобок во вложенных блоках, вложенные циклы и т.п.

 

Структура данных ОЧЕРЕДЬ

Очередь – упорядоченный набор данных (структура данных), в котором в отличие от стека извлечение данных происходит из начала цепочки, а добавление данных – в конец этой цепочки.

Очередь также называют структурой данных, организованной по принципу FIFO (First In, First Out) – первый вошел (первый созданный элемент очереди), первый вышел.

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

Пример очереди – некоторый механизм обслуживания, который может выполнять заказы только последовательно один за другим. Если при поступлении нового заказа данное устройство свободно, оно немедленно приступит к выполнению этого заказа, если же оно выполняет какой-то ранее полученный заказ, то новый заказ поступает в конец очереди из других ранее пришедших заказов. Когда устройство освобождается, оно приступает к выполнению заказа из начала очереди, т.е. этот заказ удаляется из очереди и первым в ней становится следующий за ним заказ.

Заказы, как правило, поступают нерегулярно и очередь то увеличивается, то укорачивается и даже может оказаться пустой.

При работе с очередью обычно помимо текущего указателя используют еще два указателя, первый указатель устанавливается на начало очереди, а второй – на ее конец.

Шаблон элемента структуры, информационной частью которого является целое число, может иметь следующий вид:

struct Spis {

int info;

Spis *Next;

};

При организации очереди обычно используют два указателя

Spis *begin, *end;

где begin и end – указатели на начало и конец очереди соответственно, т.е. при создании очереди мы организуем структуру данных следующего вида:

каждый элемент которой имеет информационную infо и адресную Next (A 1, A 2, ...) части.

Основные операции с очередью следующие:

– формирование очереди;

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

– удаление элемента из начала очереди.

Формирование очереди

Формирование очереди состоит из двух этапов: создание первого элемента, добавление нового элемента в конец очереди.

Создание первого элемента очереди

Этот этап заключается в создании первого элемента, для которого адресная часть должна быть нулевой (NULL). Для этого нужно:

1) ввести информацию для первого элемента (целое число i);

2) захватить память, используя текущий указатель:

t = (Spis*) malloc(sizeof(Spis)); или t = new Spis;

в результате формируется конкретный адрес (А 1) для первого элемента;

3) сформировать информационную часть:

t -> info = i; (обозначим i 1)

4) в адресную часть занести NULL:

t -> Next = NULL;

5) указателям на начало и конец очереди присвоить значение t:

begin = end = t;

На этом этапе получим следующее: