Скитания на товарни вагони

Преди да се задълбочим в стека, нека се задълбочим в работата на железницата. Знаете ли как железничарите доставят товарен вагон от точка "А" до точка "Б"? „Много е просто“, казвате вие, „те се вкопчват във влака и го влачат!“ След това погледнете фиг. 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, тъй като оригиналният влак се третира като непразен стек.