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

Часть 2: Очередь, стек и хеш-таблица

Обзор: Эта статья - вторая часть серии из 6 статей о структурах данных в .NET Framework - посвящена трем наиболее часто рассматриваемым структурам данных: очереди, стеку и хеш-таблице. Как мы увидим, очередь и стек делаются с помощью ArrayList-а, обеспечивая место для хранения переменного числа объектов, накладывая, однако, при этом ограничения на порядок доступа к элементам. Хеш-таблица - это структура данных, похожая на массив, но с большей гибкостью индексирования элементов. В то время как в массиве элементы индексируются с помощью порядковой величины, элементы хеш-таблицы могут быть индексированы посредством любого объекта.

Введение

В Части 1: Подробный анализ структур данных, мы остановились на определении понятия структур данных, методах оценки их эффективности, а также на том, как эти соображения влияют на выбор той или иной структуры данных для конкретного алгоритма. Помимо изучения базовых вещей о структурах данных и анализе их эффективности, мы также рассмотрели наиболее часто используемую структуру данных - массив.

Массив содержит совокупность однородных элементов (элементов одного типа), каждому из которых соответствует порядковый индекс. Физически, содержимое массива располагается в памяти в виде непрерывной области. Благодаря этому чтение или запись элемента массива осуществляется очень быстро.

Два недостатка массивов - это их однородность и то, что размер массива должен быть явно задан. Для устранения этого недостатка библиотека классов .NET Framework содержит в себе такую структуру данных как ArrayList, которая представляет собой совокупность элементов разного типа. Причем его размер увеличивается автоматически при необходимости. Как мы уже обсудили в предыдущей статье, реализация ArrayList в .NET Framework использует массив типа object. Каждый вызов метода Add() ArrayList-а проверяет, достаточен ли размер внутреннего массива object-ов для хранения дополнительных элементов и если нет, то размер этого внутреннего массива автоматически удваивается.

Во второй части серии мы продолжим наше знакомство с массивоподобными структурами данных и, прежде всего, рассмотрим очередь (queue) и стек (stack). Подобно ArrayList-у, эти две структуры данных содержат совокупность элементов разного типа (heterogeneous data) в непрерывной области памяти (contiguous block). Однако, как очередь, так и стек, налагают ограничения на порядок доступа к данным.

После рассмотрения очереди и стека, мы посвятим остальное время, разбираясь в механизмах работы хеш-таблицы. Хеш-таблица, иногда называемая также ассоциативным массивом (associative array), хранит совокупность элементов различного типа. Однако, элементы хеш-таблицы могут быть проиндексированы с помощью объектов произвольного типа (например, строками), а не только порядковым индексом.