Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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



Черга містить елементи, які розміщуються один за одним у ланцюжок (рис.5.1). Черга має початок і кінець. Додавати нові елементи можна тільки в кінець черги, забирати елементи можна тільки з початку. Із середини черги видаляти елементи не можна.

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

 

 

Рисунок 5.1 – Логічне представлення черги

 

У принципі, можна було б дозволити додавати елементи в обидва кінці черги та забирати їх також з обох кінців. Така структура даних у програмуванні теж існує, її назву – "дек", від англ. Double Ended Queue, тобто черга із двома кінцями. Дек застосовується значно рідше, ніж черга.

Черга практично завжди пов'язана з обслуговуванням запитів, у тих випадках, коли вони не можуть бути виконані миттєво. Черга підтримує також порядок обслуговування запитів.

Стек – найбільш популярна та, навіть, найважливіша структура даних у програмуванні. Стек – це запам'ятовуючий пристрій, з якого елементи вибираються у порядку, зворотному їхньому додаванню. Це так би мовити – неправильна черга, у якій першим обслуговують того, хто встав до неї останнім. У програмістській літературі загальноприйнятими є абревіатури, що позначають дисципліну роботи черги та стека. Дисципліна роботи черги позначається FIFO, що означає першим прийшов – першим будеш обслужений (First In First Out). Дисципліна роботи стека позначається LIFO, останнім прийшов – першим будеш обслужений (Last In First Out).

Стек можна представити у вигляді трубки з підпруженим дном, яка розміщена вертикально. Верхній кінець трубки відкритий, до нього можна додавати, або, як говорять, заштовхувати елементи (push). При вибиранні елементів зі стека вони як би виштовхуються нагору (pop).

 

  Рисунок 5.2 – Логічне представлення стека

 

 

Прикладом стека може служити стіг сіна, стопка паперів на столі, стопка тарілок та інше.

У програмуванні досить часто розглядають структуру більше складну, ніж проста множина: навантажена множина. Нехай кожний елемент множини втримується в ньому разом з додатковою інформацією, що називають навантаженням елемента. При додаванні елемента до множини необхідно також вказувати навантаження, що він несе. Такі структури називають Відображенням (Map) або Словником (Dictionary). Дійсно, елементи множини як би відображаються на навантаження, що вони несуть (відмітимо, що в математиці поняття функції або відображення визначається строго як множина пар; першим елементом кожної пари є конкретне значення аргументу функції, другим – значення, на яке функція відображає аргумент). В інтерпретації Словника елемент множини – це іноземне слово, навантаження елемента – це переклад слова на відповідну мову (зрозуміло, переклад може включати кілька варіантів, але тут переклад розглядається як єдиний текст).

Підкреслимо, що всі елементи знаходяться в навантаженій множині в одному екземплярі, тобто різні елементи множини не можуть бути рівні один одному. На відміну від самих елементів, їхнє навантаження може збігатися (так, різні іноземні слова можуть мати однаковий переклад). Тому іноді елементи навантаженої множини називають ключами, їхнє навантаження — значеннями ключів. Кожний ключ унікальний. Прийнято говорити, що ключі відображаються на їхні значення.

Іще одним прикладом навантаженої множини є множина банківських рахунків. Банківський рахунок – це унікальний ідентифікатор, що складається з 20 десяткових цифр. Навантаження рахунку – це вся інформація, що йому відповідає, тобто ім'я, адреса власника рахунку, код валюти, сума остачі, інформація про останні транзакції та інше.

Найбільше часто застосовувана операція в навантаженій множині – це визначення навантаження для заданого елемента x (значення ключа x). Реалізація цієї операції включає пошук елемента x у множині, тому ефективність будь-якої реалізації множини визначається насамперед швидкістю пошуку.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.