Очередь и стек в C#

В этой статье мы познакомимся со структурами "очередь" и "стек".

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

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

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

В данной статье мы не будем трогать очередь с приоритетами, а лишь рассмотрим классическую очередь, т.е. первым пришел, первым ушел (FIFO - first in, first out).

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

Класс Queue находится в пространстве имен System.Collections, поэтому перед тем, как использовать его, желательно подключить это пространство, чтобы в дальнейшем не утруждать себя записями вида System.Collections.Queue:
using System.Collections;

Сейчас можно смело работать с очередью. Для работы нам могут понадобиться следующие методы:

Enqueue() - помещает элемент в конец очереди

Dequeue() - достает из очереди первый элемент

В принципе этого вполне достаточно. У класса Queue есть еще несколько полезных методов:

Contains() - проверяет имеется ли данный объект в очереди

Count - свойство, содержащее количество элементов в очереди

Peek() - возвращает первый элемент в очереди, но не удаляет его

Рассмотрим пример:
        static void Main(string[] args)
        {
            Queue q = new Queue(3);

            q.Enqueue(3); //помещаем в очередь тройку
            q.Enqueue(4); //помещаем в очередь четверку
            q.Enqueue(5); //помещаем в очередь пятерку

            //наша очередь выглядит так: 5 4 3

            Console.WriteLine("В очереди содержится " + q.Count + " объекта"); //выведет 3

            Console.WriteLine("Первый элемент: " + q.Peek()); //выведет 3

            Console.WriteLine((int)q.Dequeue()  (int)q.Dequeue() - (int)q.Dequeue()); //3+4-5=2
           
        }

Немного пояснений. Сперва мы создаем экземпляр класса Queue. После чего помещаем в очередь 3 элемента. В нашем случае это объекты типа int. Обратите внимание на очередность. Тройка заняла очередь первой, а пятерка последней. Далее мы узнаем, сколько элементов содержится в очереди. Узнаем, кто первый. Ну а далее мы извлекаем элементы из очереди и сразу выполняем простенькие расчеты. Приведение к типу int обязательно, т.к. в очереди хранятся объекты типа object вне зависимости от того, что в очередь было помещено.

Нужно помнить, что невозможно узнать, кто в очереди второй или третий, пока не "достать" из очереди соответствующее количество элементов. Если вам такая функция нужна, то скорее всего придется отказаться от использования класса Queue и реализовывать очередь самому, на основе массива или ArrayList-а (о нем будет рассказано в следующей статье).

Хочу так же обратить ваше внимание на то, что очередь не является типизированной, т.е. в ней могут содержаться объекты разных типов, так что нужно быть внимательными. Т.е. если мы сделаем так:
            q.Enqueue("строка"); //помещаем в очередь строку
            q.Enqueue(3); //помещаем в очередь тройку
            q.Enqueue(4); //помещаем в очередь четверку
            q.Enqueue(5); //помещаем в очередь пятерку

То наша программа "вылетит" с ошибкой, при попытке приведения типов.

Пора перейти к изучению структуры "Стек". Со стеком мы также встречаемся в реальной жизни, правда, не так часто как с очередью. Примеров стека в жизни тоже довольно-таки много. Например, диски, надетые на шпиндель, стопка тарелок и другие. От очереди стек отличается лишь тем, что первым "достается" не тот, кто первым пришел, а тот, кто пришел последним (эх, хорошо, что в магазинах очереди, а не стеки). В программировании стеки применяются не реже чем очереди. Работать с ними так же легко. Как и для очередей в существует готвый класс Stack, который содержит все необходимые функции, а именно:

Push() - помещает элемент в стек

Pop() - достает элемент из стека

Peek() - возвращает верхний элемент стека

Contains() - проверяет содержится ли элемент в стеке

Count - свойство содержащее количество объектов в очереди

Функции практически аналогичны функциям очереди. Я решил, что работу стека мы изучим на примере следующей задачи:

Пусть у нас имеется арифметическое выражение, поддерживающее 3 вида скобок: (), [], {}. Наша задача - проверить правильность расположения скобок в выражении.

Примеры:

{(5-[3+9])-4} - правильное выражение

{(5-[3+)9]-4} - неверное выражение

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

Приступим к реализации:
        static void Main(string[] args)
        {
            string str;
            char c;
            Stack s = new Stack();
            str=Console.ReadLine();

            for (int i = 0; i < str.Length; i++)
            {

                if ((str[i] == ′(′) || (str[i] == ′[′) || (str[i] == ′{′))
                {
                    //если это открывающая скобка, то
                    s.Push(str[i]); //помещаем скобку в стек
                }
                else if ((str[i] == ′)′) || (str[i] == ′]′) || (str[i] == ′}′))
                {
                    //если это закрывающая скобка
                    if (s.Count == 0)
                    {
                        //если стек путстой
                        Console.WriteLine("Не хватает скобки");
                        break;
                    }

                    c = (char)s.Pop();
                    //проверяем соответствие форм
                    if (((c == ′{′) && (str[i] == ′}′)) ||
                        ((c == ′[′) && (str[i] == ′]′)) ||
                        ((c == ′(′) && (str[i] == ′)′)))
                    {
                        continue;
                    }
                    else
                    {
                        Console.WriteLine("Неверный тип скобки");
                        break;
                    }
                }
                else
                {
                    //если это другой символ
                    continue;
                }
            }

            if (s.Count > 0)
            {
                //в стеке остались скобки
                Console.WriteLine("Не хватает закрывающей скобки");
            }
        }

Прокомментирую код. Сперва мы создаем 3 переменные: типа string (строка), сhar (символ), Stack (стек). После чего считываем строку с экрана (ее должен ввести пользователь). Далее в цикле for мы пробегаем по всем символам введенной строки. В принципе дальше все идет по алгоритму описанному выше. Повторяться не буду. Скажу лишь, что break прерывает цикл, а continue прерывает текущую итерацию и переходит к следующему шагу цикла. обратите внимание, что в конце стек должен быть пустым. Если он не пустой, значит открывающих скобок больше чем закрывающих.

Отмечу, что представленное выше решение не является оптимальным. Я старался описать алгоритм как можно более понятно.

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


 

 

 
13.12.2008

Отзывы и комментарии

 


 
Тема
Ваше имя
Почтовый адрес
Текст сообщения
Ключ защиты:
Защита от спама
 
 
 
 
10.12  .NET Reactor
15.11  n
15.11  C# ClickOnce
 
11.10  GAC и ngen
10.10  SqlTypes