Анализ структур данных. Часть 2: Очередь, стек и хеш-таблица
Страница 9. Заключение

Заключение

В этой статье мы рассмотрели три структуры данных, поддерживаемых библиотекой классов .NET Framework:

• Очередь
  
• Стек
  
• Хеш-таблица

Очередь и стек по своим возможностям подобны ArrayList-у, поскольку они могут хранить произольное число объектов любого типа. Отличие очереди и стека от ArrayList-а состоит в том, что ArrayList позволяет доступаться к его элементам в произвольном порядке, в то время как и очередь, и стек накладывают ограничения на порядок доступа к своим элементам.

Очередь - это структура данных типа FIFO=First In, First Out . Т.е. порядок извлечения элементов из очереди будет таким же как и порядок их добавления в очередь. To Для этих целей очередь предоставляет два метода: Enqueue() и Dequeue(). Очереди полезны для обработки заданий или других ситуаций, когда элементы должны обрабатываться в порядке их прихода.

Модель доступа к данным стека называется LIFO=Last In, First Out. Такая схема доступа реализована в стеке с помощью методов Push() и Pop(). Стеки часто используются в различных областях computer scienceот исполнения кода до синтаксического разбора.

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

На этом мы заканчиваем вторую статью нашей серии. В третьей части мы рассмотрим двоичные деревья поиска -структуру данных, которая дает логарифмическое время поиска - O(log n). Подобно хеш-таблицам, двоичные деревья поиска идеально подходят, если вы знаете, что вам придется часто осуществлять поиск данных.

До следующего раза, Счастливого Программирования!

Литература

• Кормен, Лейзерсон, Ривест. "Алгоритмы. Построение и анализ", М.: МЦНМО, 2002.
  
• Headington, Mark R. and David D. Riley. "Data Abstraction and Structures Using C++." D.C. Heath and Company. 1994.
  
• Дж. Рихтер Программирование на платформе Microsoft .NET Framework
  
• Shared Source Common Language Infrastructure 1.0 Release (Сделана доступной в ноябре 2002 года)

Скотт Митчелл, автор пяти книг и основатель 4GuysFromRolla.com, на протяжении последних пяти лет работал с веб-технологиями Microsoft. Скотт работает независимым консультантом, преподавателем и писателем. Недавно он получил степень магистра Computer Science в Калифорнийском университете (University of California), Сан-Диего. Связаться с ним можно по адресу Этот e-mail защищен от спам-ботов. Для его просмотра в вашем браузере должна быть включена поддержка Java-script

Перевод - Станислав Воног, Московский физико-технический институт