Очередь, алгоритмы основных операций

 

Еще одной базовой структурой данных является очередь. Эта структура данных аналогична стеку, так как очередь объединяет объекты, работа с которыми — добавление и удаление — осуществляется по принципу FIFO (first-in first-out) (первым пришел — первым ушел). Добавление объектов в очередь может осуществляться в любое время, однако удаленным может быть лишь объект, который был добавлен первым. Говорят, что элементы добавляются в очередь с конца, а удаляются с начала. Можно сравнить очередь данных с очередью людей в любом магазине: они встают в очередь с конца, а тот, кто был первым в очереди, обслуживается.

Очередь S является абстрактным типом данных, который поддерживает две основные функции:

enqueue (о): помещает объект о в конец очереди.

Вход: объект; Выход: нет.

dequeue (): производит удаление и возвращает объект из начала очереди; если очередь пуста, выдается сообщение об ошибке.

Вход: нет; Выход: объект.

Кроме того, очередь выполняет следующие дополнительные функции:

size (): возвращает число объектов в очереди.

Вход: нет; Выход: целое число.

isEmpty (): возвращает логическое значение, подтверждающее, что очередь пуста.

Вход: нет; Выход: логическое значение.

front (): возвращает первый объект в очереди, не удаляя его; если очередь пуста, выдается сообщение об ошибке.

Вход: нет; Выход: объект.

Рассмотрим реализацию очереди с помощью массива Q для хранения элементов очереди, длина которого N, например, N = 1000. Так как основной характеристикой очереди является добавление и удаление объектов по принципу FIFO, необходимо определить способ наблюдения за началом и концом очереди.

Для того чтобы избежать перемещения объектов в Q, применим две переменные f и r

• f является индексом ячейки Q, в которой хранится первый элемент очереди (кандидат на удаление при выполнении метода dequeue) при условии, что очередь не является пустой (в этом случае f= r).

• r является индексом следующей доступной ячейки массива Q.

Изначально присваиваем f=г=0, что означает пустую очередь. Теперь, после удаления элемента из начала очереди просто увеличиваем значение f на 1 для получения индекса следующей ячейки массива. Если добавляем новый элемент, то увеличиваем значение r на 1 для получения индекса следующей доступной ячейки массива Q. Для обеспечения возможности использования всего массива Q предположим, что индексы f и г «охватывают» конечные точки массива Q. В этом случае Q рассматривается как «круговой» массив, который продолжается от Q[0] до Q[N- 1], а затем снова возвращается к Q[0].

Реализация подобного представления Q довольно проста. При каждом увеличении значения f и r на 1 необходимо записать эту операцию в виде (f + 1) mod N или (r + 1) mod N соответственно, где mod N обозначает операцию деления по модулю, которая вычисляется путем получения остатка от деления. Размер очереди вычисляется с помощью выражения (N-f+r) mod N, которое позволяет получить правильный результат как в случае нормальной конфигурации, где f<г, так и при «круговой» конфигурации, где r<f.

Алгоритмы функций:

size():

1. Возврат (N - f+ r) mod N

isEmpty():

1. Возврат (f = r)

front():

1. Возврат Q[f]

dequeue():

1. temp =Q[f]

2. Q[f]=0

3.f= (f+ 1) mod N

4. Возврат temp

enqueue(o):

1. О[t]= о

r =(r + 1) mod N

Реализация очереди на основе однонаправленного связного списка

Очередь также можно реализовать на основе однонаправленного связного списка. Для наибольшей эффективности поместим начало очереди, где можно только удалять элементы, в начало списка, а конец очереди, где можно добавлять элементы, — в хвост списка. Не следует забывать о необходимости сохранения ссылок на начальный и конечный узлы списка.

class Que

{

private Node first, last;

private int size;

public int Size

{

get { return size; }

set { size = value; }

}

public Node First

{ get { return first; }

set { first = value; }

}

public Node Last

{

get { return last; }

set { last = value; }

}

public Que() { First = null; Last = null; }

public void enqueue(int obj)

{

Node node = new Node(obj);

node.Next=null; // узел будет новым концевым узлом

if (Size == 0)

First = node; //особый случай, если до этого очередь была пуста

else

Last.Next=node; // добавляет узел в конец списка

Last = node; // перенаправляет ссылку к концевому узлу

Size++;

}

public int dequeue()

{

int obj;

obj = First.Data;

First = First.Next;

Size--;

if (Size == 0)

Last = null; // сейчас очередь пуста

return obj;

}

public int siz() { return Size; }

public bool isEmpty() { if (Size == 0) return true; else return false; }

public Node front() { return First; }

}

Классы коллекций

 

Класс ArrayList и его методы

 

Очень часто случается так, что размер массива неизвестен заранее. Именно в таких случаях удобно использовать класс ArrayList – динамический одномерный массив, то есть массив, позволяющий динамически менять свой размер. ArrayList реализует абстрактный тип «список».

Конструктор ArrayList() инициализирует новый пустой экземпляр класса ArrayList.

Реальное количество элементов, хранящихся в данный момент в ArrayList, можно узнать из свойства Count.

Метод Add(объект) добавляет объект в конец списка ArrayList.

Метод BinarySearch (объект) выполняет поиск элемента по всему отсортированному списку ArrayList и возвращает индекс (с нуля) этого элемента или -1, если элемента нет.

Метод Clear() удаляет все объекты из коллекции ArrayList

Метод Contains(объект) определяет, входит ли элемент в состав коллекции ArrayList.

Метод Insert (индекс, объект) вставляет элемент в список ArrayList по указанному нндексу.Метод Remove(объект) удаляет первое вхождение указанного объекта из списка ArrayList.Метод RemoveAt(индекс) удаляет элемент с указанным индексом из списка ArrayList.

В условиях примера с двумя классами вначале создается пустая коллекция:

Global.A1 = new ArrayList();

Добавление элемента в коллекцию:

if (radioButton1.Checked){

Global.A1.Add(new stud(Global.st1.name,Global.st1.age, Global.st1.ball, Global.st1.group)); }

else

{Global.A1.Add(newgrad_stud(Global.st1.name,Global.st1.age, Global.st1.ball,Global.st1.group, Global.st1.place)); }

Вывод элементов коллекции:

listBox1.Items.Clear();

foreach (stud A0 in Global.A1){

listBox1.Items.Add(A0.info()); }

Класс Stack и его методы

 

Этот класс представляет собой коллекцию объектов типа "последним пришел — первым вышел" (LIFO).

Конструктор Stack() инициализирует новый пустой экземпляр класса Stack.

Реальное количество элементов, хранящихся в данный момент в Stack, можно узнать из свойства Count.

Метод Contains(объект) определяет, входит ли элемент в состав коллекции Stack.

Метод Clear() удаляет все объекты из коллекции Stack.

Метод Peek()возвращает верхний объект стека Stack, но не удаляет его.Метод Pop() удаляет и возвращает верхний объект стека Stack.Метод Push(объект) вставляет объект как верхний элемент стека Stack.

Пример применения методов:

using System.Collections;public class SamplesStack { public static void Main() {// Создание и инициализация нового стекаStack myStack = new Stack();myStack.Push("The");myStack.Push("quick");myStack.Push("brown");myStack.Push("fox");// Вывод содержимого стека с конца Console.Write("Содержимое стека:");PrintValues(myStack, '\t');// Удаление элемента из стекаConsole.WriteLine("(Удаленный)\t\t{0}", myStack.Pop());// Вывод содержимого стека Console.Write(" Содержимое стека:");PrintValues(myStack, '\t');// Просмотр элемента в вершине стека.Console.WriteLine("(Верхний элемент)\t\t{0}", myStack.Peek());}public static void PrintValues(Stack myCollection,char mySeparator) { foreach (Object obj in myCollection) Console.Write("{0}{1}", mySeparator, obj); Console.WriteLine();} }

Класс Queue и его методы

 

Этот класс представляет коллекцию объектов, основанную на принципе "первым поступил — первым обслужен".

Конструктор Queue() инициализирует новый пустой экземпляр класса Queue.

Реальное количество элементов, хранящихся в данный момент в Queue, можно узнать из свойства Count.

Метод Contains(объект) определяет, входит ли элемент в состав коллекции Queue.

Метод Clear() удаляет все объекты из коллекции Queue.

Метод Dequeue() удаляет и возвращает объект, находящийся в начале коллекции Queue.

Метод Enqueue(объект) добавляет объект в конец коллекции Queue.

Метод Peek() возвращает объект, находящийся в начале коллекции Queue, но не удаляет его.

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

using System.Collections;public class SamplesQueue {public static void Main() {// Создание и инициализация новой очереди Queue myQ = new Queue(); myQ.Enqueue("The"); myQ.Enqueue("quick"); myQ.Enqueue("brown"); myQ.Enqueue("fox");// Вывод очереди в порядке поступления Console.Write("Очередь:"); PrintValues(myQ); // Удаление первого элемента очередиConsole.WriteLine("(Удален)\t{0}", myQ.Dequeue());// Вывод очереди в порядке поступления Console.Write(" Очередь:"); PrintValues(myQ);// Вывод первого элемента без его удаления Console.WriteLine("(Первый элемент) \t{0}", myQ.Peek()); } public static void PrintValues(Queue myCollection) { foreach (Object obj in myCollection) Console.Write(" {0}", obj);Console.WriteLine(); }}

 

Класс List и его методы

Класс List – это коллекция, элементами которой являются экземпляры класса. Поддерживает методы для поиска по списку, выполнения сортировки и других операций со списками.

Объявление списка имеет вид:

List<тип входящего объекта> имя = new List< тип входящего объекта>(); У класса имеются свойство

Count - Число элементов, которое фактически содержится в коллекции.

Полезные методы класса List перечислены в табл. 12.

Таблица 12

Некоторые методы класса List

Метод	Описание
Add(объект)	Добавляет объект в конец коллекции
Clear()	Удаляет все элементы из коллекции
bool Contains(элемент)	Определяет, входит ли элемент в состав коллекции
bool Exists(метод)	Определяет, содержит ли коллекция элементы, удовлетворяющие условиям указанного метода, который в качестве параметра должен иметь объект того класса, который помещен в коллекцию
Тип объекта Find(метод)	Выполняет поиск элемента, удовлетворяющего условиям метода, и возвращает первое найденное вхождение в пределах всего списка
Insert(индекс с 0,элемент)	Добавляет элемент в список в позиции с указанным индексом
bool Remove(элемент)	Удаляет первое вхождение указанного объекта из коллекции
Sort(метод сравнения)	Сортирует элементы во всем списке с использованием указанного метода

Один из примеров иллюстриует применение метода Exists List<string> dinosaurs = new List<string>();dinosaurs.Add("Compsognathus");dinosaurs.Add("Amargasaurus");dinosaurs.Add("Oviraptor");dinosaurs.Add("Velociraptor");dinosaurs.Add("Deinonychus");dinosaurs.Add("Dilophosaurus");dinosaurs.Add("Gallimimus");dinosaurs.Add("Triceratops"); Console.WriteLine("\nExists(EndsWithSaurus): {0}", dinosaurs.Exists(EndsWithSaurus)); // Метод поиска возвращает true, если строка заканчивается "saurus" private static bool EndsWithSaurus(String s) { if ((s.Length > 5) && (s.Substring(s.Length - 6).ToLower() == "saurus")) { return true; } else {return false; } } Второй пример иллюстрирует применение метода Sort: List<string> dinosaurs = new List<string>();dinosaurs.Add("Pachycephalosaurus");dinosaurs.Add("Amargasaurus");dinosaurs.Add("");dinosaurs.Add(null);dinosaurs.Add("Mamenchisaurus");dinosaurs.Add("Deinonychus");Display(dinosaurs);dinosaurs.Sort(CompareDinosByLength);Display(dinosaurs);private static int CompareDinosByLength(string x, string y){// сранение длин двух строк int retval = x.Length.CompareTo(y.Length); if (retval!= 0) // Если строки неравной длины, то более длинная строка больше return retval; else {// Если строки равной длины, они сортируются обычным образом return x.CompareTo(y); } } private static void Display(List<string> list) { Console.WriteLine(); foreach(string s in list) {if (s == null) Console.WriteLine("(null)"); else Console.WriteLine("\"{0}\"", s); } }

m(n => (long)n)));