Стекте оның стек төбесі деп аталатын жалғыз позициясына қатынай
алуға қызмет көрсету көрсетілген пәннің күшінде. Бұл позицияда уақыт
бойынша стекке соңғы келіп түскен элемент бар.
Сонымен қатар стекті фукнционалды түрде баланың "пирамидасы"
ретінде елестетуге болады. Біз стекке жаңа элементті жазғанда (пирамиданың
өзегіне жаңа сақина кигіземіз), ол алдындағы төбенің үстіне орналасады да
(алдында кигізілген сақинаның үстіне), стек төбесінде енді өзі жатады.
Элементті тек қана стек төбесінен таңдауға болады (пирамидадан тек қана ең
жоғарғы, өзекке бәрінен кеш кигізілген сақинаны алуға болады). Сонда
таңдалған элемент стектен алынып тасталады да, ал оның төбесінде таңдап
алынған элементтің алдында стекке енгізілген элемент қалады (яғни, үстінде
алынған сақина жатқан сақинасы). Стектің логикалық құрылымы
келесідегідей түрде болады:
Сур.6
Мұндағы E
1
, Е
2
, .... E
n
- әрбіреуінде бір немесе бірнеше мәліметтер өрісі
болатын стек элементтері. Стектің элементтеріне қолданылатын маңызды
опреациялар (қосу және алу) оның төбесінен жүргізіледі, сонымен қатар
әрбір мезетте алып тастау үшін E
n
элементіне ғана қатынауға болады.
Стек төбесі арнайы көрсеткіш көмегімен адрестеледі. Стекке жаңа
элементті қосу келесі түрде жасалады. Басында көрсеткіш слоттың немесе
ұяшықтың ұзындығы бойынша "жоғары" орналасады, сосын көрсеткіштің
мәні бойынша стекке жаңа элемент туралы ақпарат орналасады.
Стектен элементті алып тастағанда бірінші көрсеткіштің мәні бойынша
алып тасталатын элемент туралы ақпарат оқылады да, сосын көрсеткіш бір
слотқа "төмен" ығысады.
Егер көрсеткіш стектің соңына қатысты бір ұяшықтың ұзындығына
төмен ығысса, стек бос деп есептеледі.
Элементтерді қосу мен алудан басқа стекке басқа да операцияларды
жасауға болады: стекті тазалау және стек көлемін тексеру (яғни, ондағы
элементтер саны).
Стектің физикалық құрылымы.
Стекті сақтау үшін машинаның жадында кейбір элементтердің
максималды санын орналастыру үшін жеткілікті үлкен тұтас облыс бөлінеді.
Бұл облыстың адресінің шекті мәндері стектің физикалық құрылымының
параметрлері болып табылады. Егер толтыру процесінде көрсеткіш жоғарғы
шекарадан асып кетсе, онда стек толып кетеді де, жаңа элементті енгізу
мүмкін емес болады. Егер толып кетпесе, бос слоттарға қосуға болады.
Осылайша, стек ұзындығы оны қолдануда өзгере алса да, бірақ бұл
өзгерістер бөлінген жадының бөлігінің белгіленген шекарасынан шығып
кетпеу керек. Сондықтан стек – жартылайстатикалық құрылым. Стектің
физикалық құрылымы әдетте дескрипторлармен толтырылады, онда: стек
аты, жадыдағы физикалық құрылымның шектері, көрсеткіш және элементтің
бейнеленуі бар
Сур. 7
Кезек – сызықты тізбекті тізім, бұнда элементтерді қосу тізбектің
соңында жасалады (кезектің аяғында), ал жою – басында (кезектің
басында).
Кезекте қызмет көрсету пәні келесі принциппен өрнектеледі
FIFO (First - In - First - Out) -
"бірінші келдің – бірінші кеттің".
Теміржол аналогиясы бойынша – бір бағыттағы жолдың сызықты
бөлімі.
Сур.8
Кезектің басы мен соңының индикациясы үшін екі көрсеткіш
ұйымдастырылады.
Қарапайым кезектің схемасы:
Сур. 9
Ұяшықтардың немесе слоттардың шекті тізбегі белгіленеді. A
1
, А
2
, ...,
А
max
- адрестер, f- кезектің басындағы элементтің көрсеткіші, f – соңындағы
элементтен кейінгі бірінші бос слотты адрестейді..
Кезектерге қолданылатын негізгі опреациялар – элементтерді қосу мен
жою..
Қосу кезінде жаңа элемент г көрсеткішімен адрестелетін слотқа
енгізіледі, содан кейін келесі бос слотқа итеру қажет болады. (схемада -
оңға).
Кезектен элементті алып тастағанда f көрсеткішімен адрестелетін
элемент алынып тасталады, одан кейін келесі толтырылған слотқа көшеді.
Басқа мүмкін опреациялар: ағымдағы ұзындықты тексеру және тазалау.
Әрине, кезекке жаңа элементтерді қосу процесінде ерте ме, кеш пе
толып кетеді. Бұл кезектен элементтер жойыла ма, жойылмай ма, оған
байланысты емес. Яғни, г көрсеткіші жадының белгіленген шекарасынан
шығып кетеді.
Бұл жағдайды бодырмауға болады, егер А
max
кейін г-ны A
i
адресті
слотқа көшірсе. Осылайша ұйымдастырылған кезек сақиналы деп аталады.
Ол мына схема бойынша жұмыс істейді:
Сур. 10
Бұндай кезекте кез келген қатынас мүмкін:
ff=r, (бос кезек)
f>r.
Дек (ағылшыншадан deque -double ended queue) – элементтерді қосу да,
жою да тізімнің кез келген шегінен жүзеге аса алатын екі шегі бар сызықты
тізбекті тізім.
Дек – үшеуінің ішіндегі неғұрлым жалпы құрылым. Стек пен кезектің
қосындысы болып табылады. Дек құрылымын имитациялайды, мысалы,
теміржол разъезінің схемасы
Дербес жағдай:
1) шектелген кірісі бар дек;
2) шектелген шығысы бар дек болып табылады.
Бірінші жағдайда жолдың жоғарғы бөлігі жабық, екінші жағдайда –
төменгі.
Дектің логикалық және физикалық құрылымы кезектің логикалық
және физикалық құрылымдарымен бірдей. Бірақ басы мен соңының орнына
дек үшін оң және сол шек деп айту қабылданған.
Декке қолданылатын операциялар – элементерді қосу және алу. Олар
кезекке қолданылатын операциялардың жалпылануы мен дамуы болып
табылады.
4.2 Жартылайстатикалық құрылымдарды массив
көмегімен көрсету.
Стек көрсетілімі
Стектің типтік көрсетілімі – стекке сілтелетін элементтердің неғұрлым
аз емес саны бар массив.
Кезекті элемент үшін осы элементке арналған бір t көрсеткіші болса
болды.
Стек бос болғанда, t = 0.
Бейнелеу:
Const ms= 100;
var stack : array [1..ms] of tt;
Достарыңызбен бөлісу: |
