Простейшие операции с очередью
Структуры данных
Наиболее распространенные структуры данных
1. Массивы
2. Стеки
3. Очереди
4. Связные списки
5. Деревья
6. Графы
7. Боры (это тоже деревья, но их целесообразно рассмотреть отдельно).
8. Хеш-таблицы
Массивы
Массив — это простейшая и наиболее распространенная структура данных. Другие структуры данных, например, стеки и очереди, производны от массивов.
Здесь показан простой массив размером 4, содержащий элементы (1, 2, 3 и 4).
Каждому элементу данных присваивается положительное числовое значение, именуемое индексом и соответствующее положению этого элемента в массиве. В большинстве языков программирования элементы в массиве нумеруются с 0.
Существуют массивы двух типов:
· Одномерные (такие, как показанный выше)
· Многомерные (массивы, в которые вложены другие массивы)
Простейшие операции с массивами
· Insert — вставляем элемент на позицию с заданным индексом
· Get — возвращаем элемент, занимающий позицию с заданным индексом
· Delete — удаляем элемент с заданным индексом
· Size — Получаем общее количество элементов в массиве
Вопросы по массивам, часто задаваемые на собеседованиях
· Найти второй минимальный элемент массива
· Найти неповторяющиеся целые числа в массиве
· Объединить два отсортированных массива
· Переупорядочить положительные и отрицательные значения в массиве
Стеки
Всем известна знаменитая опция «Отмена», предусмотренная почти во всех приложениях. Задумывались когда-нибудь, как она работает? Смысл такой: в программе сохраняются предшествующие состояния вашей работы (количество сохраняемых состояний ограничено), причем, они располагаются в памяти в таком порядке: последний сохраненный элемент идет первым. Одними массивами такую задачу не решить. Именно здесь нам пригодится стек.
Стек можно сравнить с высокой стопкой книг. Если вам нужна какая-то книга, лежащая около центра стопки, вам сначала придется снять все книги, лежащие выше. Именно так работает принцип LIFO (Последним пришел — первым вышел).
Так выглядит стек, содержащий три элемента данных (1, 2 и 3), где 3 находится сверху — поэтому будет 
убран первым:
Простейшие операции со стеком:
|
|
|
· Push — Вставляет элемент в стек сверху
· Pop — Возвращает верхний элемент после того, как удалит его из стека
· isEmpty — Возвращает true, если стек пуст
· Top — Возвращает верхний элемент, не удаляя его из стека
Вопросы о стеке, часто задаваемые на собеседованиях
· Вычислить постфиксное выражение при помощи стека
· Отсортировать значения в стеке
· Проверить сбалансированные скобки в выражении
Очереди
|
|
|
Очередь, как и стек — это линейная структура данных, элементы в которой хранятся в последовательном порядке. Единственное существенное отличие между стеком и очередью заключается в том, что в очереди вместо LIFO действует принцип FIFO (Первым пришел — первым вышел).
Идеальный реалистичный пример очереди — это и есть очередь покупателей в билетную кассу. Новый покупатель становится в самый хвост очереди, а не в начало. Тот же, кто стоит в очереди первым, первым приобретет билет и первым ее покинет.
Вот изображение очереди с четырьмя элементами данных (1, 2, 3 и 4), где 1 идет первым и первым же покинет очередь:
Простейшие операции с очередью
· Enqueue() — Добавляет элемент в конец очереди
· Dequeue() — Удаляет элемент из начала очереди
· isEmpty() — Возвращает true, если очередь пуста
· Top() — Возвращает первый элемент в очереди
Дата добавления: 2020-01-07; просмотров: 163; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!