Обхід лінійного списку, стеку, черги, деку

Якщо ви займаєтеся програмуванням, ви, напевно, зустрічалися з такими структурами даних, як лінійний список, стек, черга та дек. У цій статті ми розглянемо, як обійти кожну з цих структур даних та які є найбільш ефективні способи для цього.

Вступ

Перш ніж переходити до обходу кожної зі структур даних, давайте розберемося з тим, що таке лінійний список, стек, черга та дек.

Лінійний список

Лінійний список – це структура даних, яка складається з вузлів, кожен з яких містить дані та вказівник на наступний вузол. Лінійний список може бути однонаправленим, коли вузли вказують тільки на наступний вузол, або двонаправленим, коли вузли вказують на наступний та попередній вузли.

Стек

Стек – це структура даних, яка працює за принципом “останній увійшов – перший вийшов”. Елементи можуть бути додані до стеку тільки на одному кінці, а видалені – тільки з того ж кінця.

Черга

Черга – це структура даних, яка працює за принципом “перший увійшов – перший вийшов”. Елементи можуть бути додані до черги тільки на одному кінці, а видалені – тільки з іншого кінця.

Дек

Дек – це структура даних, яка може бути використана як стек або черга. Елементи можуть бути додані або видалені з будь-якого кінця.

Тепер, коли ми зрозуміли, що ці структури даних означають, ми можемо перейти до обходу кожної з них.

Обхід лінійного списку

Обхід за допомогою циклу while

Один з найпростіших способів обійти лінійний список – використовувати цикл while. Починаємо з першого вузла та переходимо до наступного вузла за допомогою вказівника, доки не досягнемо останнього вузла.

current_node = head
while current_node is not None:
    # робимо щось з поточним вузлом
    current_node = current_node.next

Обхід за допомогою циклу for

Можна також обійти лінійний список за допомогою циклу for. Використовуючи функцію range, ми можемо змусити цикл перебирати всі індекси списку та отримати поточний вузол за допомогою оператора [ ].

for i in range(len(linked_list)):
    current_node = linked_list[i]
    # робимо щось з поточним вузлом

for i in range(len(stack)-1, -1, -1):
    current_node = stack[i]
    # робимо щось з поточним вузлом

Обхід черги

Чергу також можна обійти за допомогою циклів while та for. Однак, черга працює за принципом “перший увійшов – перший вийшов”, тому ми повинні звертатися до елементів черги знизу вгору.

while len(queue) > 0:
    current_node = queue.pop(0)
    # робимо щось з поточним вузлом

for i in range(len(queue)):
current_node = queue[i]
# робимо щось з поточним вузлом

Обхід деку

Дек можна обійти за допомогою тих самих циклів while та for, що і стек. Проте, оскільки дек дозволяє додавати та видаляти елементи як з початку, так і з кінця, ми можемо звертатися до елементів деку в будь-якому порядку.

while len(deque) > 0:
    current_node = deque.popleft() #або deque.pop()
    # робимо щось з поточним вузлом

for i in range(len(deque)):
    current_node = deque[i]
    # робимо щось з поточним вузлом

Приклад обходу деку

Розглянемо простий приклад обходу деку за допомогою циклу while. Нехай ми маємо дек, що містить наступні елементи: 1, 2, 3, 4, 5.

from collections import deque

deque_example = deque([1, 2, 3, 4, 5])

while len(deque_example) > 0:
    current_node = deque_example.popleft()
    print(current_node)

У результаті виконання цього коду ми отримаємо наступний вивід:

1
2
3
4
5

Висновок

Обхід лінійних структур даних, таких як списки, стеки, черги та деки, є важливою операцією при роботі з даними. Ми можемо обходити ці структури за допомогою різних циклів та виконувати над елементами різні операції. Використання правильного методу для обходу структури даних залежить від її типу та особливостей її реалізації. Використання цих методів може допомогти у вирішенні різних задач при програмуванні та аналізі даних.