Поневіряння товарного вагона
Перш, ніж заглибитись у стек, вникнемо в роботу залізниці. Ви знаєте, як залізничники доставляють товарний вагон із пункту «А» до пункту «Б»? "Дуже просто, - скажете, - чіпляють до складу і тягнуть!" Тоді погляньте на рис. 100.
1 У 3
Мал. 100 – Доставка вагонів між кількома станціями
Тут показано п'ять залізничних станцій, чотири з яких позначені цифрами, а п'ята – вузлова станція – літерою «У». Припустимо, що зі станції «1» треба доставити кілька десятків вагонів інші станції (у напрямку стрілок). З цих станцій також везуть вагони, але відповідних стрілок я не показав. Тягти вагони поодинці руйнівно! Тому їх збирають у потяги по кілька десятків вагонів. Накопичивши такий склад на станції «1», залізничники доставляють його на вузлову станцію; сюди стікаються склади з інших напрямів. На вузловій твориться найцікавіше,
— тут з одних складів формують інші для того, щоб тягнути їх далі в потрібному напрямку. Ця робота називається сортуванням складу. У нашій країні є сотні товарних станцій, багато з яких вузлові. Перш ніж потрапити за призначенням, вагон кочує між вузловими станціями через кілька сортувань. А ви кажете: просто, просто!
Але це ще приказка, казка попереду.
Черги та стеки
Сортувальна гірка
Отже, на вузлових станціях формують нові потяги для того, щоб кожен вагон прямував далі в потрібному напрямку. Для сортування влаштовані звані сортувальні гірки . Гірка - це трохи нахилена ділянка шляху; якщо відчепити від вагона, що стоїть на ньому, вагон, останній покотиться під гірку. Але покотиться недалеко, — під гіркою влаштовано кілька глухих кутів. Тупик - це звичайний стан програміста, алетут я говорю про інші безвиході, залізничні. Це ділянки колії, обмежені з одного боку земляним валом. Уткнувшись у цей вал, вагон зупиниться. Гірка з'єднується з глухими кутами залізничними стрілками, перемикаючи які можна направити вагон, що котиться з гірки, в той чи інший глухий кут (рис. 101).
Мал. 101 – Схема сортувальної гірки
Як сортують склад? Основну роботу виконують двоє: зчіпник та стрілочник (який завжди винен!). Від складу, що стоїть на гірці, зчіпник від'єднує по черзі вагон за вагоном і повідомляє стрілочнику по рації, до якого з глухих кутів направити черговий вагон, — тому залишається лише переводити свої стрілки. Вкотившись у глухий кут, вагон гальмується земляним валом або злегка співпадає з вагоном, що вже стоїть там, і автоматично зчепляється з ним. «Розкидавши» по глухих кутах один склад, на гірку викочують інший і продовжують сортування, поки в глухих кутах не сформуються нові склади, готові до подальшого шляху.
Наша мета: змоделювати сортувальну гірку, тобто створити програму, яка веде себе подібно до такої гірки. Вагони замінимо символами; отже, і склад і вагони, що стоять у глухих кутах, ми представимо рядками. Вважатимемо перший символ рядка першим вагоном складу, — він причеплений до локомотива. У глухому куті першим буде вагон, що стоїть біля земляного валу. Легко здогадатися, що обробляти вагони будемо за принципом стека, оскільки зчіпник завжди доступний тільки останній вагон.
Черги та стеки
Домовившись звідси, сформулюємо завдання остаточно. Дано рядок символів (склад), з якого треба сформувати три інші. Вагони, позначені великими літерами 'A'…'Z' відправимо на станцію «A»; інші, позначені маленькими літерами 'a'…'z' — поїдуть до станції «B», а треті, позначені цифрами'0'…'9', - до станції «C». Програма має сформувати три рядки – це знову зібрані склади. Перший символ у них,
- Це вагон, причеплений безпосередньо до локомотива.
Для вирішення завдання треба лише точно повторити дії зчіпника і стрілочника. «Відчіплятимемо» символи від рядка і «заштовхуватимемо» їх у стеки — це наші безвиході. Отже, треба збудувати механізм для стеків. Він буде схожий на механізм для черги: елементи зберігаємо у рядкових змінних, а для занесення та вилучення елементів із стеку заснуємо дві процедури. За традицією програмісти називають ці процедури так: Push – заштовхнути у стек, і Pop – виштовхнути зі стека.
Процедура заштовхування у стек Push приєднує символ до кінця рядка. Вона повторює процедуру встановлення у чергу, тільки називається інакше.
А функція виштовхування зі стека Pop повертає останній символ рядка, одночасно видаляючи його звідти. Якщо стек виявиться порожнім, функція повідомить про це. Подібність із функцією вилучення з черги очевидно, різниця лише позиції витягуваного символу: для черги це перший символ, а стека — останній.
Тепер вам не важко розібратися в наведеній нижче програмі P_45_2 . Зверніть увагу на відчеплення вагонів від вихідного складу: вона також виконується функцією виштовхування Pop, оскільки вихідний склад трактується як непустий стек.