Головна

Списки. Стек. черга

  1. В першу чергу, це викликано наявністю великих обсягом капіталів, одержуваних в основних сферах бізнесу, і обмеженнями їх подальшої експансії.
  2. У свою чергу, щодо визнання рішень іноземних судів російське законодавство визнає дві категорії, залежно від змісту рішення.
  3. Вкладені списки.
  4. Друга черга ЄАІС
  5. Лінійно-стадіальної розуміння історії і радянська (нині російська) історіологіі стародавнього світу взагалі, історіологіі Стародавнього Сходу в першу чергу
  6. Мислення підрозділяється на теоретичне і практичне. У свою чергу теоретичне може бути понятійним і образним, а практичне - наочно-образним і наочно-дієвим.
  7. Обидва ці напрямки пов'язані, в першу чергу, з дослідженням

Черга - це лінійний список інформації, робота з якої відбувається за принципом "першим прийшов - першим вийшов". Це означає, що перший поміщений в чергу елемент буде отримано з неї першим, другий поміщений елемент буде витягнутий другим і т.д. Це єдиний спосіб роботи з чергою; довільний доступ до окремих елементів забороняється.

12.1.1. Циклічна чергу.

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

Найчастіше циклічні черги застосовуються в операційних системах для зберігання інформації, яка обліковується і записується в дискові файли або на консоль. Циклічні черги також використовуються в програмах обробки реального часу, які повинні продовжувати обробляти інформацію, буферізіруя при цьому запити на введення / виведення. Багато текстові процесори використовують цей прийом під час переформатування абзацу або вирівнювання рядка. Введений текст не відображається на екрані до закінчення процесу. Для цього прикладна програма повинна перевіряти натискання клавіш під час виконання іншого завдання. Якщо будь-яка клавіша була натиснута, введений символ швидко поміщається в чергу, і процес триває. Після його завершення символи витягуються з черги.

12.2. Стек.

Стек (stack) є ніби протилежністю черзі, оскільки він працює за принципом "останнім прийшов - першим вийшов" (last-in, first-out, LIFO) [1]. Щоб наочно уявити собі стек, згадайте стопку тарілок. Перша тарілка, що стоїть на столі, буде використана останньої, а остання тарілка, покладена наверх - першої. Стеки часто застосовуються в системному програмному забезпеченні.

Прекрасний приклад використання стека - калькулятор з чотирма діями. Більшість сучасних калькуляторів сприймають стандартну запис виразів, звану інфіксной записом, загальна форма якої виглядає як операнд-оператор-операнд. Наприклад, щоб скласти 100 і 200, необхідно ввести 100, натиснути кнопку "плюс" ( "+"), потім ввести 200 і натиснути кнопку "дорівнює" ( "="). Навпаки, у багатьох ранніх калькуляторах (і деяких з вироблених сьогодні) застосовується Постфіксний запис, в якій спочатку вводяться обидва операнди, а потім оператор. Наприклад, щоб скласти 100 і 200 в постфіксной записи, необхідно ввести 100, потім 200, а потім натиснути клавішу "плюс". У цьому методі операнди при введенні заталкиваются в стек. При введенні оператора операнди витягуються (виштовхуються) з стека, а результат буде втягнений знов у стек. Одна з переваг постфіксной форми полягає в легкості введення довгих складних виразів.

12.3. Перелік.

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

Пов'язані списки можуть бути одинзв'язного і двусвязного [1]. Однозв'язний список містить посилання на наступний елемент даних. Двусвязний список містить посилання як на наступний, так і на попередній елементи списку. Вибір типу застосовуваного списку залежить від конкретного завдання.

Операції зі списками:

- впорядкування

- Вставка / видалення елементів

- Зміна адреси наступного елемента

- Робота з підрядками



типи даних | Дерева. графи

Сигнали і дані | Штучний інтелект. Інформаційне суспільство | кількість інформації | Склад персонального комп'ютера і характеристики основних пристроїв | Процесор, Оперативна пам'ять | Зовнішня пам'ять з файлової організацією | Сканер і принтер | Інтерпретація і компіляція | асемблер | Процеси. Послідовний. Розгалужених. |

© um.co.ua - учбові матеріали та реферати