Очереди

Else

Else

Do

{

if (isBracket(begBracket, a[++i]))

myStack.Push(a[i]);

if (isBracket(endBracket, a[i]))

if (!myStack.isEmpty())

switch (myStack.Pop())

{

case '(':

if (a[i]!=')')

{result =i; error = true;}

break;

case '[':

if (a[i]!=']')

{result =i; error = true;}

break;

case '{':

if (a[i]!='}')

{result =i; error = true;}

break;

}

{ error = true; result = i; }

}

while (!error && (i != lenA-1));

if (!myStack.isEmpty() || error)

result = i;

return result;

}

Для вызова процедуры достаточно написать одну строчку кода:

Console.WriteLine(BracketTest("{aaa(bbb)cc[ss[]}"));

Для данной строки на экране будет напечатано число 17. Это означает, что в 17-ой позиции строки ошибка – напечатана скобка }, а должна быть сначала скобка ].

В программировании принцип работы с очередью тот же самый, что и в быту: первым пришел — первым ушел (FIFO — от англ.First — In – First — Out).

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

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

Основные операции c очередью те же, что и со стеком:

· инициализация очереди;

· добавление элемента в очередь;

· проверка очереди на пустоту;

· взятие элемента из очереди.

В зависимости от характера решаемой задачи очередь можно организовать статически или динамически. Если в процессе работы очередь то очень длинная (несколько десятков или сотен элементов), то короткая (один-два элемента), имеет смысл реализовать очередь с использованием динамической структуры (списка). Если заранее известна максимальная длина очереди, то можно использовать статический массив. Рассмотрим оба этих способа.

При динамической реализацииосновой очереди является линейный односвязный список. Однако, в отличие от динамического стека, который определяется одним указателем (на вершину), для работы с очередью необходимы два указателя: на голову очереди и на ее хвост. Поэтому для определения очереди возьмем класс, содержащую в качестве полей эти два указателя. И тогда при работе с очередью последняя будет характеризоваться только одним параметром. Это описание очереди и основные операции приведены в листинге 8.25.

Листинг 8.25. Очередь, реализованная динамически

namespace SpaceStack

{

class MyStack // Очередь

{

Node top; // голова очереди

Node tail; // хвост очереди

public void Push(object data) // в стек

public object Pop() // взять из стека

public bool isEmpty() // проверка на пустоту

public class Node // узел

// положить в хвост очереди

public void PushQueue(object inf)

{

Node p = new Node(null, inf);

if (isEmpty())

{

top = p; tail = p;

}

Дата добавления: 2014-03-11; просмотров: 350; Нарушение авторских прав

Мы поможем в написании ваших работ!