Структуры данных — большой гайд

Теория: Простое определение — Связь между алгоритмами и структурами данных — Простые структуры: типы данных — Сложные (интегрированные) структуры данных — Статические, динамические, полустатические — Связные и несвязные — Линейные и нелинейные

Стандартные операции и применение — Как подобрать структуру данных — Встроенные структуры данных в Python — в Java — в JavaScript — Продвинутые структуры данных: деревья и графы

Практикум: Массивы — Дженерики — Список — Связный список — Хэш-сет — Словарь/Хэш-карта — Очередь — Стек — Кортеж

Где применяются: Массив — Связный список — Стек — Очередь

Теория

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

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

Более простыми словами

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

Алгоритмы и структуры данных — как это связано

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

Поэтому структуры данных неразрывно связаны с алгоритмами. Изучая структуры данных, не обойтись без изучения алгоритмов.

Существует классическая книга “Алгоритмы и структуры данных” швейцарского ученого Никлауса Вирта, воспитавшая уже поколения программистов (буквально поколения: первое издание книги вышло в 1976). В ИТ сложилась практика советовать новичкам начинать изучение алгоритмов и структур данных именно с этой книги; ее принято считать фундаментальной. К сожалению, примеры кода в этой книге составлены на древнем языке Оберон (и подобных, тоже древних, вроде Паскаля); вряд ли современный тестировщик когда-нибудь будет работать с кодом на этом языке; есть там и другие проблемы; а времени на учебу может быть мало; поэтому начинать изучение структур данных и алгоритмов (дисциплина «АСД» в университете на первом курсе профильных вузов) — лучше, например, с бесплатных (и при этом неплохих!) курсов в интернете; примеры там изложены на современных (и широко применяемых в QA) языках Python, Java, JavaScript.

Простые структуры данных (типы данных)

Это так называемые примитивы — базовые элементы в классификации структур данных. Типы данных это как бы кирпичики, из которых строятся сложные структуры данных. Типы данных в QA это, например: булевы (логические), целые, с плавающей точкой, двоичные, символы, указатели, строки, и подобные «неделимые». В языках программирования набор простых типов может отличаться.

В наглядном виде иерархия структур данных выглядит так:

Сложные (интегрированные) структуры данных

Состоящие из других структур данных, простых или (тоже) интегрированных. Данный гайд описывает сложные структуры данных. Наиболее часто применяются в QA: массивы, стеки, связные списки, очереди, а также деревья (включая двоичные), и графы (“сложные деревья”).

Статические структуры данных

Данные имеют фиксированный формат, размер и расположение в памяти. Примеры: векторы, массивы, множества, записи.

Динамические структуры данных

Нефиксированный формат, размер и расположение; это изменяется в зависимости от задачи. Примеры: стеки, очереди, строки, списки, графы, деревья.

Полустатические структуры данных

Основная характеристика: изменяемый размер, но это изменение ограниченное, не превышающее какой-то лимит. Пример: однонаправленный связный список.

Линейные структуры данных

Данные упорядочены в последовательном порядке; как в массивах, стеках, очередях, связных списках. Каждый элемент “привязан” в последующему и предыдущему.

Нелинейные структуры данных

Данные расположены как бы в “рендомном” порядке, то есть без последовательности (привязки). Элементы могут быть “привязаны” к одному или многим другим элементам. Нелинейные структуры это деревья, графы.

Связные и несвязные структуры данных

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

Примеры связных структур: связный список, дерево поиска.

Примеры несвязных структур: массивы, строки, стеки, векторы.

Структуры данных — стандартные операции

• Создание структуры данных.
• Вставка данных в структуру. Существует три варианта вставки:
  • В начало
  • В конец
  • В нужное место
• Обход (traversal) каждого элемента как минимум один раз.
• Поиск элемента среди других. Варианты поиска:
  • Линейный (последовательный) поиск; простой
  • Бинарный (двоичный, полуинтервальный, логарифмический) поиск; он сложнее логически, но быстрее (производительнее)
• Сортировка, то есть упорядочивание элементов, выстраивание их в нужном порядке.
  • Сортировка пузырьком (пузырьковая сортировка)
  • Сортировка выбором
  • Быстрая (сортировка Хоара)
  • Сортировка слиянием
  • Сортировка кучей (пирамидальная)
• Слияние, то есть объединение элементов из двух сортированных структур
• Обновление, то есть замена значения элемента в структуре новым значением
• Удаление элемента из структуры; как и создание, удаление может быть из начала, конца, или из нужного места.

Применение структур данных

• Сохранение новых данных в структуру данных (базу данных, чаще всего)
• Управление системными ресурсами: выделение памяти, манипуляции с файлами и папками, формирование очередей задач
• Обмен данными по сети (например, через TCP-IP)
• Упорядочивание (организация) данных и их сортировка 
• Индексация элементов в базе данных (присвоение условных номеров в нужном порядке)
• Поиск нужных данных — самым быстрым и эффективным способом
• Масштабирование (расширение или уменьшение) крупных объемов данных в Big Data

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

Проанализировать задачу, учитывая:

• Какие операции поддерживаются в структуре данных
• Вычислительная сложность. Сколько времени требуется на операции, сколько памяти выделяется? Опытный программист/тестировщик “на лету” оценивает это, учитывая все нюансы, соблюдая баланс краткости и эффективности.
• Элегантность решения (да!)

Структуры данных в языках программирования: блиц

[имеются в виду встроенные (inbuilt), они же — наиболее часто применяемые, по крайней мере джуниором QA]

Структуры данных в Python

В Python существует 4 встроенных структуры данных: 

• списки (List)
• словари (Dictionary)
• кортежи (или тюплы, Tuple)
• и множества (или наборы, сеты, Set).

Для Junior QA с Python этих структур может быть достаточно, так как операции с этими структурами составляют примерно 80%  “от общей массы”.

Встроенные структуры данных в Python

Списки	Словари
— На списках следует сделать упор в изучении, поскольку они в Python являются очень функциональным и видимо наиболее часто применяемым инструментом; cловари и кортежи в некотором смысле “работают как вариации списков” — Квадратные скобки: [ ] — Допускаются элементы-дубликаты — В списках можно хранить любые объекты (числа, строки, другие списки) — Доступ к спискам осуществляется на программном уровне “как к строкам“, то есть используя срезы и конкатенацию — На более фундаментальном уровне (уровне интерпретатора) списки в Python являются Си-массивами (фактически список это массив указателей)	— Словари похожи на хэши или карты в других языках программирования — Фигурные скобки: { } — как и в множестве, но: — Элементы в словаре — последовательность пар ключ:значение, через двоеточие, разделенных запятыми — Ключи являются уникальными и неизменяемыми объектами — Не допускаются элементы-дубликаты — Начиная с версии Питона 3.7, словари являются упорядоченными структурами данных
Кортежи	Множества
— Круглые скобки: ( ) — Допускаются элементы-дубликаты — “Как списки”, но неизменяемы (то есть нет методов добавления/удаления); чтобы защитить данные от непреднамеренных изменений — А если понадобилось изменить данные в кортеже, есть функции преобразования “туда и обратно”: list() и tuple(): — Могут состоять из элементов совершенно разных типов, через запятую — Занимают меньше места в памяти, чем списки — В кортежи удобно включать списки	— Неупорядоченная коллекция уникальных (не повторяющихся) и неиндексированных объектов — И бывают “замороженные множества” (frozenset), то есть неизменяемые — Фигурные скобки: {} , как в словаре — Не допускаются элементы-дубликаты — Элементы множества являются неизменяемыми, но можно удалять их из множества и добавлять новые — Элементом множества может быть число, строка, список; и не может быть кортеж — Доступны все стандартные операции с множествами из математики (например объединение, пересечение, разность)

Структуры данных в Java

• ArrayList
• LinkedList
• HashMap
• Set

Подробнее о структурах данных в Java — в блиц-практикуме далее

Структуры данных в JavaScript

Массив (Array)	Множество (Set)
Упорядоченный набор данных; дубликаты разрешены;  Пример массива в JS: [1, 2, false, ‘good’]	Неупорядоченный набор данных; дубликаты не разрешены Пример множества в JS: new Set () set.add(1)
Объект (Object)	Карта (Map)
Состоит из пар {ключ:значение}; значения можно менять Пример:  {name: ‘Ivan’, age: 28}	Состоит из пар {ключ:значение}; только для хранения; для карты есть методы get, set, delete Пример:  new Map() map.set(‘name’, ‘Ivan’)

Другие, наиболее часто используемые, структуры данных в JS:

• Стек
• Очередь
• Хеш-таблица
• Связный лист
• Бинарное дерево

Продвинутые структуры данных: деревья и графы

Дерево

Нелинейная структура данных, состоящая из узлов (нодов, вершин), соединенных ребрами (edges): 

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

Дерево является иерархической структурой данных. Пример иерархической структуры в ИТ: DOM-дерево HTML-документа, представляющее ее объектную модель. Пример иерархической структуры в жизни — генеалогическое дерево.

Термины

Узел (нод) — одна из “вершин” в древовидной структуре, здесь содержится ключ (значение), и указатель на нижестоящий, или дочерний узел (также потомок); соответственно главный узел называется родительским по отношению к дочернему (родитель). 

Ребра — связные линии, соединяющие узлы.

Корень — первый узел в дереве:

Листья — последние узлы в дереве (терминальные), то есть они не имеют дочерних узлов. Все другие узлы называются внутренними.

Высота дерева — длина самого продолжительного пути к листу.

Глубина узла — длина пути к его корню.

На рисунке ниже показаны высота (h) и глубина (d) каждого узла:

Лес — совокупность не соединенных деревьев:

Наиболее распространённые типы деревьев:

• Бинарное дерево
• Бинарное дерево поиска
• AVL-дерево
• B-дерево
• T-дерево

Часто применяется Бинарное дерево (двоичное) — в котором каждый узел имеет не более 2 потомков, левого и правого. 

Обход дерева — алгоритм получения доступа к нужному узлу, путем «обхода» (traversal) всех его узлов, по одному разу.

Существует поиск в глубину (алгоритм «идёт вглубь дерева до упора») и поиск по ширине (последовательный просмотр по «уровням» дерева). 

Поиск в глубину имеет три основных способа: центрированный, прямой, обратный (inorder, preorder, postorder).

Более подробно об обходе дерева.

Применение деревьев:

• Бинарные деревья поиска (BST) — для очень быстрой проверки, есть ли элемент (в базе)
• Специфический тип дерева, называемый trie (префиксное дерево), в современных моделях роутеров для хранения данных
• B (дерево поиска) и T (trie) типы деревьев — в крупных базах данных
• В компиляторах языков программирования, для проверки синтаксиса написанного кода

Граф

Граф — совокупность узлов (проще говоря, “контейнеров с данными”), соединенных с другими узлами в нужном порядке. 

Граф математически описывается как структура вида G (V, E), где 

• V — совокупность (коллекция) вершин (англ. vertices)
• E — коллекция ребер, представляемых как упорядоченные пары вершин (u,v)

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}

Термины

Смежность (adjacency). Вершина смежна другой вершине, если между ними есть соединяющее ребро. Также ребра считаются смежными (между собой), если соединяют одну вершину.

Петля — ребро, имеющее только одну вершину (“тупиковое”).

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

Длина пути — количество ребер, которые “нужно пройти” в пути.

Цепь — если ребра по пути не повторяются.

Связный граф — в котором можно проложить путь между любыми двумя вершинами.

Дерево представляет собой связный граф, не имеющий циклов.

Подробнее терминология графов.

Частые операции с графами

• Проверка наличия элемента в графе
• Обход графа
• Добавление элементов (вершин или ребер)
• Поиск пути из одной вершины к другой

Пример графа IRL

Современные социальные сети типа Facebook представляют собой пример графа — каждая страница (Профиль, Фотографии, События, Комментарии, Сторис и д.т.) является узлом в графе социальной сети, привязанным к другим узлам ссылками-”ребрами”:

Структуры данных: практикум

Упомянутый выше ИТ-гуру, автор “Алгоритмов и структур данных” Никлаус Вирт писал, что “обучение путем подачи хорошего примера часто — самый эффективный, а иногда — и единственно возможный метод”. 

Туториал описывает структуры данных, которые наиболее часто применяются в QA (то есть в автоматизированных тестах); эти примеры на C# и Java; описания более-менее релевантны и для других языков.

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

Arrays (Массивы)

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

Важные свойства массива:

• Первый элемент в массиве, как правило, с индексом “0” (а не “1”). 
• Если понадобился второй элемент массива, к нему обращаются по индексу “1”, и так далее.
• При создании массива задается его размер — далее не изменяемый. 

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

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

Существуют (и активно применяются в QA) структуры данных, более гибкие и удобные, чем простой массив — generic-обертки массивов; в C# это List, в Java — ArrayList. 

А иногда удобнее простой массив. Например для теста нужно создать URL с параметризованным запросом, содержащий список ID-шек через запятую:

<base_url>?ids=2,5,7

Создается метод, который принимает массив из ID-шек, и конвертирующий их в строку с запятыми:

Другой кейс. Есть строка с цифрами и символами; надо изъять из нее цифры, и вывести их сумму. Вот так:

Как упоминалось выше, существуют generic—обертки, более удобно оперирующие массивами. Вообще, тестеру, претендующему на миддла, очень желательно разобраться с дженериками на теоретическом уровне как можно раньше, до того, как приступать к углубленному изучению структур данных; ибо все структуры данных в известном смысле являются дженериками.

Generics (Дженерики)

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

• В Java и C# встроены дженерики ArrayList и List, Dictionary и так далее.
• Можно задать ограничение в плейсхолдере, что присваиваемый тип должен соответствовать изначальному типу, или что не может быть “пустым” (null). Бывают и другие ограничения
• Во многих дженериках предусмотрены удобные методы для манипулирования данными специфического типа
• Можно даже создавать собственные дженерики (кастомные).

Кастомные дженерики. Например есть у нас REST-API-микросервис, и мы создаем тестовый проект. Наш микросервис всегда возвращает StatusCode (всегда одного типа) и какие-то данные Data (они меняются в зависимости от ответа конечной точки API).

Создаем generic-модель, которую потом можно использовать для всех других конечных точек:

Выше создана модель RestResponse, в которой свойства имеют постоянный тип — HttpStatusCode (строковый тип). И также имеется Body с типом T — этот тип может быть задан любым.

Итак, создается метод, который парсит наши JSON-данные для модели, и ожидаем RestResponce типа <T> — с любым типом. 

Список (List). List (C#) / ArrayList (Java)

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

Удобство такой обертки состоит в методах для манипулирования данными.

Взглянем на пример:

Разумеется, существует намного больше методов, и надо их знать (для QA-миддла это наверное обязательно). List / ArrayList это базовая структура данных, исходя из ее очень частой применяемости в QA, и операции с ней нужно практиковать. Существуют специальные библиотеки, LINQ в C# и Stream API в Java (об этом в конце практикума бонусный пункт).

В Сети много туториалов для практики со списками, в том числе и для QA-автоматизаторов. В них часто встречается задача поиска и сохранения WebElements со страницы, для дальнейшей обработки.

Самая частая задача: проверка наличия элемента на странице. Если пытаться найти один элемент, получают ошибку “Нет такого элемента”; если ищут список, можно просто проверить, что количество его элементов равно 0.

Еще бывает кейс ожидания, когда количество элементов превысит какое-то значение:

Аналогично как в предыдущем пункте с дженериками; API-ответ ожидается с каким-то количеством элементов, но мы не знаем, каким. Поэтому задаем List<DataType>:

Linked List (Связный список)

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

Каждый элемент содержит данные о себе, и может запрашивать следующий элемент. В связном списке нельзя “перепрыгнуть” от первого элемента сразу к последнему. Если нам нужен последний, надо “пройти по порядку” по всем элементам.

Так же у двухстороннего связного списка (иногда еще называется двусвязным). Элементы такого списка “знают” о (то есть имеют связь с) сразу с двумя элементами — предыдущим и следующим.

Hash Set (Хэш-сет)

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

Попробуем добавить элементы-дубликаты в созданный хэш-сет:

Чем может быть полезен хэш-сет. Например, есть элементы-результаты, принятые от какого-то источника данных, и нужно профильтровать дубликаты. Создается HashSet<T> и в него добавляются все результаты. При этом дубликаты не смогут добавиться.

Примечание: в таких случаях можно применить Сортированный Сет (Sorted Set), элементы в нем сортируются автоматически:

Dictionary/HashMap (Словарь/Хэш-карта)

Как и хэш-сет, это разновидность Таблицы хэшей (Hash Table). Словарь в Java и C# это дженерик-класс с маппингом (картой), состоящей из пар ключ / значение. 

Ключи должны быть уникальными; попытка добавить дубликат вызовет ошибку.

Из-за своего удобства, такая специфическая структура данных является очень распространенной в практике QA.

Пример. Надо создать некий полезный метод работы с SQL-операторами. Для этого создаем словарь с ключами типа Enum и соответствующими им значениями SQL-операторов:

Далее передаем enum-ключ в метод, и получаем его значение:

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

Примечание. В Java эквивалент Словаря это HashMap:

Queue (Очередь)

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

В тестировании Очереди применяются, когда данные идут как бы “параллельно”, то есть одновременно поступают и отдаются. Например есть хранилище данных, и надо записать туда данные, и параллельно получить данные оттуда. 

Stack (Стек)

Это дженерик-класс с коллекцией, организованной по LIFO—принципу (“последним пришел — первым вышел”). Проще всего визуализировать Стек в виде стопки тарелок: тарелка, положенная в стопку последней, снимается первой.

Стеки чаще применяются в тестировании API-запросов. Допустим, может быть только одна операция со статусом “Выполняется” у одного Клиента. Но мы можем выполнять тесты параллельно, поэтому можно прописать в тесте на этапе beforeAll присвоение всем Клиентам ID-шек, и сохранить их все в Стеке.

Каждый тест пытается получить “самый верхний” ID Клиента и запустить тест с ним.

На cleanup—этапе теста возвращаем Client Id назад в Стек.

 

Итак, Стеки удобно применять в параллелизации тестов.

Tuple (Кортеж)

Упорядоченный список элементов. Применяется обычно для получения данных из методов.

Допустим есть Customer и его заказы Orders, и надо получить данные из User Details и Order Details:

Значит, создаем метод, получающий (возвращающий) User-модель и список заказов Orders:

В конце вызываем этот метод:

Можно возвращать несколько элементов, причем разных типов:

Бонус — LINQ/Stream API

В целом, с самыми распространенными структурами данных в QA мы ознакомились. Но не лишним будет ознакомиться еще с такой вещью, как более удобная обработка списков в LINQ в C# (Language Integrated Query) и Stream API в Java. Эти вещи помогают более эффективно (то есть быстрее и изящнее) обрабатывать данные, особенно что касается их фильтрации по условию, а также конвертации форматов.

Пример. Фильтруем значения больше 80. 

Синтаксис LINQ — через очередь (query):

И через лямбду:

Как видим, одинаковые результаты:

Лямбда — более удобный способ обработки, и в основном применяется именно он. Еще примеры с лямбдой, 

Операции: Sum, Average, Skip, Take

Сумма и Среднее — стандартные примеры из учебников. Пропуск и Отбор надо рассмотреть подробнее. Пример: имеем массив, в котором нужно скипнуть (пропустить) один элемент, и принять в обработку два следующих. То есть пропускаем элемент с индексом 0 и принимаем элементы с индексами 1 и 2; в списке будут элементы со значениями 92 и 81.

Операции с элементами: First, Last, Where, All, Any

Выводятся результаты:

Операция выбора (выбрать все данные и конвертировать). Есть Имя, Должность, и Зарплата:

Выбираем только Имена:

Или можно конвертировать в более сложные объекты:

В Java схожая по функциональности библиотека. Например имеем коллекцию с фамилиями и возрастом:

Фильтруем по возрасту и выводим имена:

Результат:

_{Источник — Структуры данных в автоматизации QA / Kostiantyn Teltov}

Структуры данных — где применяются

Массив

• Контакты в смартфоне хранятся в массиве
• Таблица результатов (или лучших игроков) в онлайн-игре хранится в массивах, сортируемых в ниспадающем порядке
• Обработка изображений (двумерные массивы = матрицы)
• Обработка речи (каждый звук сохраняется в виде массива)
• Пиксели на экране — тоже массив
• Названия книг в онлайн-библиотеке
• Билеты при заказе в онлайн-букинге хранятся в массиве

Связный список

• Список выполненных действий в Notepad (или любом редакторе); благодаря связному списку, можно отменить, повторить, или удалить действие
• И другие системы навигации, например переход Вперед/Назад по посещенным страницам в браузере (двунаправленный связный список)
• Слайд-шоу, то есть последовательный просмотр фоток тоже через связный список
• Мультитаскинг в операционной системе с многими пользователями, работающими одновременно: каждому пользователю через связный список выделяется часть ресурсов системы
• В мультиплеере во многих играх — циклический переход между пользователями
• В музыкальном плеере — навигация в плейлисте
• Посты на твоей странице Вконтакте идут в связном списке

Стек

• В текстовых редакторах вместо связного списка делается стек выполненных операций, которые можно Отменить/Повторить
• А также в браузерах, для навигации
• Уведомления (notifications) в Youtube — стеки в LIFO-формате; последние просмотренные видео показываются сначала
• Стеки управления памятью — важнейший компонент в операционной системе Windows

Очередь

• В операционной системе: списки ожидания на выполнение в устройствах типа принтера, жесткого диска, процессора
• А также ожидание прерываний
• В мессенджерах на смартфонах: когда пропадает мобильное покрытие у получателя, отправленные сообщения на сервере ждут в очереди на доставку
• В планировщиках задач
• Действия клавиатуры и мыши (что хорошо видно, когда система тормозит)
• Управление трафиком на сайтах
• Управление shared-ресурсами в локальных сетях

***

Также на сайте:

Что такое кросс-браузерное тестирование?

В чем разница между QA и QC?