Что такое словарь в программировании

Словари

«Неупорядоченный» – значит, что последовательность расположения пар не важна, в следствие чего обращение к элементам по индексам невозможно.

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

Чтобы представление о словаре стало более понятным, проведем аналогию с обычным словарем, например, англо-русским. На каждое английское слово в таком словаре есть русское слово-перевод: cat – кошка, dog – собака, table – стол и т. д. Если англо-русский словарь описать с помощью Python, то английские слова можно сделать ключами, а русские – их значениями:

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

В словаре доступ к значениям осуществляется не по индексам, а по ключам, которые заключаются в квадратные скобки (по аналогии с индексами списков):

В словаре не может быть двух элементов с одинаковыми ключами. Однако могут быть одинаковые значения у разных ключей.

Ключом может быть любой неизменяемый тип данных. Значением – любой тип данных. Значения словарей вполне могут быть структурами, например, другими словарями или списками.

Перебор элементов словаря в цикле for

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

Но по ключам всегда можно получить значения:

В цикле for можно распаковывать кортежи, таким образом сразу извлекая как ключ, так и его значение:

Методы словаря keys() и values() позволяют получить отдельно перечни ключей и значений. Так что если, например, надо перебрать только значения или только ключи, лучше воспользоваться одним из этих методов:

Методы словаря

Метод clear() удаляет все элементы словаря, но не удаляет сам словарь. В итоге остается пустой словарь:

Словарь – это изменяемый тип данных. Следовательно, как и список он передается в функцию по ссылке. Поэтому иногда, чтобы избежать нежелательного изменения глобального словаря его копируют. Это делают и с другими целями.

Метод get() позволяет получить элемент по его ключу:

С помощью setdefault() можно добавить элемент в словарь:

С помощью update() можно добавить в словарь другой словарь:

Также метод обновляет значения существующих ключей. Включает еще ряд особенностей.

Практическая работа

Напишите функцию, которая принимает один словарь, и возвращает другой, в котором ключами являются значения из первого словаря, а значениями – соответствующие им ключи. Создайте словарь, передайте его в функцию. Выведите на экран исходный и «перевернутый» словари.

Примеры решения и дополнительные уроки в android-приложении и pdf-версии курса

Источник

Словарь (программирование)

Смотреть что такое «Словарь (программирование)» в других словарях:

Словарь — Многотомный латинский словарь У этого термина существуют и другие значения, см. Словарь (программирование). Словарь книга … Википедия

программирование — кодирование (на (машинном, мышинном) языке) Словарь русских синонимов. программирование сущ., кол во синонимов: 9 • автопрограммирование (1) … Словарь синонимов

Программирование — процесс подготовки задач для их решения с помощью компьютера; итерационный процесс составления программ. По английски: Programming См. также: Программирование Жизненный цикл программного обеспечения Компьютерные программы Финансовый словарь Финам … Финансовый словарь

ПРОГРАММИРОВАНИЕ — 1) процесс составления программы, плана действий. 2) Раздел информатики, изучающий методы и приёмы составления программ. С долей условности П. как дисциплина разделяется на: теоретическое, изучающее матем. абстракции программ (как объектов с… … Физическая энциклопедия

ПРОГРАММИРОВАНИЕ — Процесс и искусство создания компьютерных программ и/или программного обеспечения с помощью языков программирования. Программирование сочетает в себе элементы искусства, фундаментальных наук (прежде всего информатика и математика), инженерии,… … Словарь бизнес-терминов

программирование — Научная и практическая деятельность по созданию программ. [ГОСТ 19781 90] программирование разработка ПО — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] Тематики информационные технологии в… … Справочник технического переводчика

ПРОГРАММИРОВАНИЕ — ПРОГРАММИРОВАНИЕ, я, ср. (спец.). 1. см. программировать. 2. Часть прикладной математики и вычислительной техники, разрабатывающая методы составления программ (в 6 знач.). Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 … Толковый словарь Ожегова

программирование в графических образах — — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] Тематики информационные технологии в целом EN iconic programming … Справочник технического переводчика

программирование перемещения регулирующих стержней в активной зоне при аварии ядерного реактора — — [А.С.Гольдберг. Англо русский энергетический словарь. 2006 г.] Тематики энергетика в целом EN control rod program … Справочник технического переводчика

программирование с использованием макрокоманд — — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] Тематики информационные технологии в целом EN macroprogramming … Справочник технического переводчика

Источник

Словарь (map) на языке C#

Словарь (map) — это структура данных, представляющая собой специальным образом организованный набор элементов хранимых данные. Все данные хранятся в виде пар ключ-значение. Доступ к элементам данных осуществляется по ключу. Ключ всегда должен быть уникальным в пределах одного словаря, данные могут дублироваться при необходимости. У данной структуры есть и другие часто встречающиеся названия: ассоциативный массив или Dictionary. Принцип работы словаря схож с камерой хранения: есть ячейка, в которой может храниться что угодно, но доступ к этой ячейке осуществляется по уникальному номеру, благодаря чему ее всегда легко найти. Давайте рассмотрим пример реализации словаря на языке C#.

На рисунке ниже представлена схематичная структура словаря.

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

1. Add — добавление нового элемента с уникальным ключом.

2. Remove — удаление элемента по ключу.

3. Update — изменить хранимое значение по ключу.

4. Get — получить хранимое значение по ключу.

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

Теперь рассмотрим программный код.

Объявим класс словаря, его свойства и реализуем основные операции

Теперь проверим работу словаря обратившись к нему

Ну и наконец запустим приложение и посмотрим результат работы на консоли

Автор, у тебя мап на списке чтоль?

Их обычно на красно-черных деревьях делают (или на AVL деревьях, если вставок мало, выборок много).

Словари делают на хеш-таблицах.

Соответственно, у деревьев локап за O(log N), у хеш-таблиц за O(1) до O(N) (если bad case и автор упоролся и не контролирует load factor).

Я не понял, в С# map’a не было.

А vector там хоть есть, или что-то подобное? А queue??

Легла в направлении мечты. Пост № 4

Всем привет. Как прошла ваша неделя? У меня замечательно, закончила я с основами шарпа, ну как закончила, решила, что все остальное буду уже учить в процессе. И вот, пару дней назад я перешла к Unity. И это очень сложно описать, какой у меня пока идет восторг, вроде бы пока у тебя ничего особенного нет, на экране – просто гуляющий овал, какие то картинки взятые бесплатно с сайта Unity, но как же это здорово, от этой маленькой тени настоящей игры, у тебя уже вырабатывается адреналин.

Если брать более конкретно, то за эти два дня Unity, (первые три дня я занималась ООП по C#) узнала, как создавать окружение, откуда брать ассеты и как с ними работать, поняла, как создавать движения персонажа, его прыжок, расставила платформы, как сделать движение камеры за персонажем, с помощью cineMachine.

Начала читать книгу: “Unity и C# Геймдев от идеи до реализации” – Джереми Бонд. Пока успела прочитать 83 страницы. Начало книги посвящено геймдизайну, пока все описано в общих чертах, посмотрим, что будет дальше.

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

На следующей неделе в планах: анимация персонажа, боёвка, добавление различных уровней, музыка, звуки, враги и т.д.. Иногда появляется небольшой страх, что сколько всего нужно запомнить, но потом думаю, что создать пару своих проектов, и это должно уложиться в голове. Потому что пока в ней небольшой бардак, а пока из-за страха энтузиазм упал до 8/10. И как люди умудряются сделать игру за пару дней?

Как и обещала, делюсь ресурсами, которые мне посоветовали в комментариях, плюс чем пользуюсь я для изучения:

• Курс по Unity. Создание 2D платформера – прохожу сейчас С#.(Udemy).

• Complete C# Unity Game Developer 2D – возьмусь после прохождения курса по Unity (Udemy).

• Ulearn.me – тоже прекрасный курс по С#.

• exercism.org – курсы по C# на английском.

Сайты с задачами (здесь те, которые мне понравились больше всего):

• codingame.com – это сайт огонь, спасибо за подсказку.

• c-sharp.pro – здесь задачки для начинающих

• С# для чайников – хорошая замена онлайн курсов, для тех, кто любит книги.

• Unity и C# Геймдев от идеи до реализации, 2-е издание.

• Геймдизайн, как создать игру, в которую будут играть все.

• «Новый уровень!» Руководство по геймдизайну.

• Проектирование виртуальных миров. Теория и практика дизайна уровней.

• Кровь пот и пиксели – книгу уже прочитала, очень она понравилась, хорошо снимает розовые очки, что в игровой индустрии всё гладко и хорошо показывает, как много бывает кранча при создании игр.

• Чистый код. Создание анализ и рефакторинг. Роберт Мартин – для этой книги нужны уже хоть какие-то знания в C#.

• Грокаем алгоритмы – Адитья Бхаргава

• Геймдизайн. Рецепты успеха лучших компьютерных игр от Super Mario и Doom до Assassin’s Creed и дальше – Тайнан Сильвестр

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

Источник

Словарь Python – полное руководство

Словарь Python используется для хранения данных в формате пары ключ-значение.

Что такое словарь в Python?

Словарь в Python – это тип данных, который может имитировать реальную организацию данных, в которой существует определенное значение для определенного ключа. Это изменяемая структура данных. Словарь определяется в элементах ключи и значения:

Другими словами, мы можем сказать, что словарь – это набор пар ключ-значение, где значением может быть любой объект Python. Напротив, ключи – это неизменяемый объект Python, то есть числа, строка или кортеж.

Создание словаря

Словарь можно создать, используя несколько пар ключ-значение, заключенных в фигурные скобки <>, и каждый ключ отделяется от своего значения двоеточием(:). Синтаксис для определения словаря приведен ниже.

В приведенном выше словаре Dict ключи Name и Age представляют собой строку, которая является неизменяемым объектом.

Давайте посмотрим, как создать словарь и напечатать его содержимое.

Python предоставляет встроенный метод функции dict(), который также используется для создания словаря. Пустые фигурные скобки <> используются для создания пустого словаря.

Доступ к значениям словаря

Мы обсудили, как можно получить доступ к данным в списке и кортеже с помощью индексации.

Однако доступ к значениям в словаре можно получить с помощью ключей, поскольку ключи в словаре уникальны.

Доступ к словарным значениям можно получить следующим образом.

Python предоставляет нам альтернативу использованию метода get() для доступа к значениям словаря. Результат будет тот же, что и при индексации.

Добавление значений словаря

Словарь – это изменяемый тип данных, и его значения можно обновлять с помощью определенных ключей. Значение можно обновить вместе с ключом Dict[ключ] = значение. Метод update() также используется для обновления существующего значения.

Примечание. Если пара “ключ-значение” уже присутствует в словаре, значение обновляется. В противном случае новые ключи добавляются в словарь.

Давайте посмотрим на примеры обновления значений словаря:

Удаление элементов с помощью ключевого слова del

Элементы словаря можно удалить с помощью ключевого слова del, как указано ниже.

Последний оператор печати в приведенном выше коде вызвал ошибку, потому что мы пытались напечатать словарь сотрудников, который уже удален.

Метод pop() принимает ключ в качестве аргумента и удаляет связанное значение. Рассмотрим следующий пример.

Python также предоставляет встроенные методы popitem() и clear() для удаления элементов из словаря. Popitem() удаляет произвольный элемент из словаря, тогда как метод clear() удаляет все элементы из всего словаря.

Итерационный словарь

Словарь можно повторять с помощью цикла for, как указано ниже.

# цикл для печати всех ключей словаря

#for цикл для печати всех значений словаря

#for цикл для печати значений словаря с помощью метода values().

#for цикл для печати элементов словаря с помощью метода items().

Свойства ключей словаря

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

Рассмотрим следующий пример:

2. В Python ключ не может быть изменяемым объектом. Мы можем использовать числа, строки или кортежи в качестве ключа, но мы не можем использовать какой-либо изменяемый объект, такой как список, в качестве ключа в словаре.

Встроенные функции словаря

Встроенные методы словаря

Встроенные методы словаря Python вместе с описанием приведены ниже.

Источник

Просто о списках, словарях и множествах или ТОП 5 структур данных

Привет. Ей! Не говорите “Да блин! Я знаю, чем отличается список от вектора, мне не нужна эта статья”. Прошу, загляните под кат и освежите свои знания. Я надеюсь, однако, что вы сможете почерпнуть из этой статьи намного больше и, некоторые, возможно, наконец-то разберутся, почему существует так много типов данных для коллекций объектов.

Введение

Так уж сложилось, что в программировании коллекции представляет много, нет ОЧЕНЬ МНОГО различных сущностей — списки, массивы, вектора, множества, стеки, очереди, ассоциативные массивы и у большинства из этих структур данных есть еще по несколько подвидов.

Должны же быть причины, чтобы для простого представления какой-либо совокупности объектов существовало настолько много различных вариаций.

Должны же быть отличия между списком и массивом? Между ассоциативным массивом и хеш-таблицей?

Коллекция

Для начала — самое скучное (да, я люблю такое). Что такое коллекция вообще?

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

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

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

Ладно, свой негласный долг я выполнил, теперь поехали!

1 Вектор (Vector, Array)

А вы чего ждали?

Вектор (он же одномерный массив) — упорядоченный набор элементов с произвольным доступом по числовому индексу. Что для нас важно в этом определении? Да ничего. Шучу, на самом деле нам важно почти каждое слово:

Доступ к элементам производится по числовому индексу (обычно начиная с 0-го индекса, хотя есть и исключения), обычно доступ к элементу коллекции по индексу записывается как myFavoriteCats[i] или blackKitties[5]. Причем для обозначения этого самого числа — индекса используют букву i.

А когда одной буквы не хватает приплетают сюда j и k.

Итак, далее мы понимаем, что доступ произвольный — значит мы можем обращаться к элементам под индексами 0, 42, 2014 и вобщем-то ожидаем, что операция будет сложности O(1), т.е. константной и независимо от того какой из элементов мы запросим он нам со скоростью света тут же вернется.

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

Релизация

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

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

И действительно, получить доступ к определенному элементу очень просто — прибавляем к указателю на первый элемент индекс (с некоторыми поправками на размер типа данных) и получаем указатель на нужный элемент! Осталось разыменовать и у нас в переменной нужная кошечка!

Ладно, вектор — классная структура, но и у него есть недостатки (а у кого их нет?!), например нельзя просто так взять и добавить в вектор новый элемент! Особенно втиснуть его в середину. Нельзя также сказать, что кошки с номерами 0, 1 и 4 у нас есть, а с номерами 2 и 3 — нет (раньше они были, но оказалось, что это собаки).

Можно представить себе вектор, как книжную полку с отделениями, в каждом из которых помещается ровно одна книга. Чтобы засунуть новый роман Донцовой между 10-ым и 11-ым томом Большой Совецкой Энциклопедии нужно сильно постараться и переложить все тома с 11-го по 65-ый тома (можно схитрить и поставить 11-ый том в конец, но я вам этого не говорил, да и мы в таком случае потеряем упорядоченность).

В моей памяти все именно так

Применение

В нашем случае вектор бы идеально подошел для топ-10 самых милых котят, т.к. добавлять и удалять элементы не нужно (только изменять), пропусков между 1-ым и 5-ым местом быть не должно, да и удобно обращаться по номеру.

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

2 Список (List)

Первый том

Ух! Список задач на сегодня, список покупок в магазине. Список гостей на свадьбу… Так. Ближе к делу.

Мы уже знаем, что элементы вектора лежат акуратненько друг за другом, красиво и ровно. Это дает нам как преимущества так и недостатки.

Список в этом плане полностью противоположная вещь — его элементы могут быть разбросаны по памяти как угодно! Из-за этого мы теряем возможность быстро получить элемент по индексу, а также не можем быстро скопировать весь список, но получаем довольно приятную штуку — мы можем вставлять элементы за константное время в любое место! По слухам удаляются элементы из списка тоже за O(1).

Реализация

Хм. А как с формальным определением?

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

Для последнего элемента списка мы храним нулевой указатель (на диаграммах я буду использовать указатель на нулевую кошку (Null Cat), не пугайтесь).

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

Если бы я мог, я бы один элемент списка разместил на северном полюсе, а другой где-нибудь в окресностях Бетельгейзе

Применение

Список бы подошел для (внимание!) списка бездомных котят, отсортированных по возрасту (по возрастанию). Нам как-раз нужно часто добавлять и удалять элементы из списка (вы не подумайте ничего такого — котят забирают), да и чаще понадобятся первые элементы списка — я бы взял себе маленького пушистого котенка, а не 8-ми-летнего манула.

Ладно. Списки это вроде простая структура. Что есть еще?

3 Множество (Set)

Это Сет

Похожее понятие есть в математике, а точнее в теории множеств. Множество отличается и от вектора и от списка, хотя их реализация может быть похожа.

Множество — неупорядоченный набор элементов, без повторов. Ух. И все? Ни тебе произвольного доступа, ничего! Зачем такое нужно?

Как мы знаем в векторе можно быстро получить элемент по индексу, в списке можно быстро добавить или удалить элемент, а что с множеством?

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

Реализация

В множестве, т.к. оно неупорядочено можно сортировать элементы при добавлении и в случае чего устроить бинарный поиск. Хм. Вот ведь парадокс, коллекция неупорядоченная, а внутри все будет по-порядку. Тут важно понять, что если вы добавите новый элемент в множество, не факт, что он пойдет в конец.

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

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

Вообще есть еще упорядоченные множества, множества с повторами (мультимножество), и вероятно должно быть упорядоченное мультимножество.

Теория множеств дается проще, если брать множество котят

Применение

Множество идеально подойдет для списка любимых котят, потому что их множество. Ха! Шучу.

Но оно действительно подойдет, потому-что такую коллекцию не нужно сортировать (упорядоченность не важна) и мы легко сможем проверить, находится ли какой-нибудь конкретный кот в этом множестве (скажем у меня 100 котят и любимых я кормлю креветками).

Ну ладно. Множества тоже хороши, но неужели есть что-то еще?

4 Словарь (Associative Array, Map, Dictionary)

Признайтесь, это лучше, чем просто словарь

Словарь (он же ассоциативный массив) — это тот-же вектор, но с небольшими отличиями. В качестве индекса (который в словаре будет называться ключ) могут выступать не только числа, но и любые другие типы данных (даже другие коллекции!). Также допустимы пропуски, если мы все-таки будем использовать в качестве ключа целое число, например у нас может быть элемент связанный с ключем 5, но при этом отсутствовать элемент связанный с ключем 4.

Что все это значит на практике? Всего-лишь, то, что в квадратных скобках для ображения к элементу по “индексу” мы можем указывать произвольный тип, например allMyCats[“Murka”].

Реализация

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

Мы также не можем сказать какая пара первая, какая последняя и что раньше “Murka” или “Borka”, поэтому словарь считается неупорядоченной структурой.

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

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

Применение

Самый правдоподобный и грамотный способ — использовать словарь вместе со списком, где ключем словаря будет строка — имя кошки, а значением — список кошек с таким именем. Это позволит быстро найти всех кошек по имени Мурка и выбрать из них ту, которая в данный момент нужна.

Примерно так выглядит в памяти std::map >

И у меня для вас новость — типы коллекций закончились. Ну все. Вообще больше нет. Совсем.

5 Стек (Stack)

Еще один кот и будет Stack Overflow

Ха! Я вас обманул (всмысле пошутил)! Есть еще пара структур данных, которые представляют коллекции.

Итак стек — коллекция с необычным доступом, точнее с необычными правилами относительно того, как могут быть добавлены и удалены элементы.

Все просто — добавляемый элемент, называемый “последним”, первый выбывает из из стека.

Стек очень нужен и полезен в программировании. Например с помощью стека осуществляется вложенный вызов процедур — в стек сохраняются адрес возврата и аргументы вызванной функции.

Реализация

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

В низкоуровневой реализации (точнее то, как он реализован в современных архитектурах) есть интересные моменты.

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

Если в стек поместить слишком много данных программа завершится со всем знакомой ошибкой — Stack Overflow, это значит, что указатель на конец стека превысил верхний допустимый предел.

Также может случиться обратная ситуация (Stack Underflow), если попытаться забрать из стека больше чем в нем есть, но в высокоуровневых языках она не встречается (понятно почему — нам не дают напрямую работать со стеком).

Если кому интересно как это все работает — изучение ассемблера для какой-нибудь популярной архитектуры, вроде i386, может вам помочь.

Применение

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

Разное

На самом деле есть еще куча коллекций, таких как очередь, двусторонняя очередь (дек), двусвязанный список, кольцевое множество, очереди с приоритетом.

Есть деревья (да их целый лес!) и графы.

Есть вероятностные структуры данных, такие как вероятностное множество и список с пропусками.

Я очень хочу про все это написать, но времени и места на хабре не всегда мало.

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

Строки

В первую очередь то, как реализованы строки в некоторых языках может показаться странным. Самое простое и эффективное решение это наверное решение C — строка это набор символов, с нулевым символом в конце, что позволяет обходиться без дескриптора.

В C++ std::string уже больше походит на вектор.

Ну а в старом паскале дескриптор (точнее всего-лишь длина) хранится в нулевом элементе массива.

В Haskell String — это список символов ([Char]), из чего вытекает, что получение длины строки имеет сложность O(n). Зато их очень удобно оббегать рекурсивно.

В общем случае, строка — это упорядоченный набор символов и не более. Какой именно тип коллекции будет использован — не важно (ну я бы не советовал использовать множество, ха!).

Очередь (Queue)

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

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

Еще можете попробовать реализвать очередь на двух стеках, но это тоже менее эффективно.

Также есть дек (двусторонняя очередь — deque). В ней можно добавлять элементы как в конец, так и в начало. И забирать их тоже и с конца и с начала.

Заключение

Ух. Я начинаю повторяться

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

Однако я думаю статья исполнит свою роль — просто и понятно изложит основы структур данных для читателей разной степени подготовленности. И я буду рад продолжить и осветить множество (или очередь, ха!) других тем в таком-же ключе.

Спасибо тем, кто смог дочитать аж до этих строк (как они это выдержали?).

Источник