курсач (1). Программалау тілдері Таырыбы Стек. Стекпен жмыс. Дек. Декпен жмыс

• Название: Программалау тілдері Таырыбы Стек. Стекпен жмыс. Дек. Декпен жмыс
• Дата: 21.12.2021
• Размер: 0.79 Mb.
• Имя файла: курсач (1).docx
• Тип: Программа; #312412

Қазақстан Республикасы Білім және Ғылым министрлігі

Л.Н. Гумилев атындағы Еуразия Ұлттық университеті

Ақпараттық Технологиялар Факультеті

Ақпараттық Қауіпсіздік Кафедрасы
КУРСТЫҚ ЖҰМЫС

Пән атауы: «Алгоритм және программалау тілдері»

Тақырыбы: «Стек.Стекпен жұмыс. Дек. Декпен жұмыс»

Орындағандар: Досмұхаметова Балжан

Махамбет Нұрлыбек

Орынбасар Гульжазира
Қабылдаған: Сагиндыков Каким Молдабекович

Нұр-Сұлтан 2021

Мазмұны

Кіріспе

1.Стек ұғымына толық сипаттама беру бөлімі

1.1Негіздерімен танысу....................................................................................5

1.2 Стектің жадыда басқарылуы......................................................................7

1.3 Идеясын мысал бойынша ашу…………………………………………...9

1.4 Стек тәсілдерінің негізгі қызметтері және оларды программада қолдану.............................................................................................................10

2. Дек тақырыбына толық түсіндірме бөлімі

2.1 Дек интерфейсін пайымдау.....................................................................17

2.2 Дек тәсілдерінің негізгі қызметі..............................................................19

2.3 Тәсілдерін программада қолдану: add();remove(); get();........................22

Қорытынды.......................................................................................................26

Пайдаланған әдебиеттер тізімі........................................................................27

Кіріспе

Бұл курстық жұмыста алгоритмдер мен бағдарламалаудың концептуалды ұғымдарының бірі – стек пен дек қарастырылады. Стек және дек - жадтың ерекше аймақтары болып табылады. Бұл жад негізінен регистрлердің мазмұнын уақытша сақтау үшін қолданылады. Java Collection негізінен деректер құрылымын модельдейтін және жүзеге асыратын стек пен дек кластарын қамтамасыз етеді.

Тақырыптың өзектілігі: Заманауи ақпараттық технологиялар стек және дек арқылы жадыны тиімді басқаруға мүмкіндік береді. Орталық процессорда орындау үшін өте қарапайым және логикалық болады. Процессордың жылдамдығы мен жауап беру қабілетін арттырады, әсіресе байтты жаңарту циклінің уақыты өте аз болғандықтан. Стексіз рекурсия мүмкін емес, өйткені функцияға кез келген қайта енгізу ағымдағы күйді жоғарғы жағында сақтауды талап етеді және функциядан әрбір шыққанда бұл күйді жылдам қалпына келтіру керек.

Курстық жұмыстың мақсаты : Ақпараттық құрылымдарға қатысты теориялық материалмен танысу және Stack and Deque-тің қолданып жүрген программада қандай қызметтер атқаруын және тәсілдерін жеке-жеке талдау жайлы әзірлеу болды.

- Программада жүзеге асуы, жадыда басқарылуы туралы қарастыру;

- Түсіндерме идеясын мысал, диаграммалар арқылы жеткізу;

- Әр тәсілдерін жеке-жеке талдап және оларды мысал есептертермен көрсету;

- Негізгі қызметтерін программада қолдану;

Зерттеу міндеттері:

- Массивты стекте пайдалана отырып, есепті талдау

- try-catch, мұрагерлік, абстракт және интерфейсті пайдаланып, программа құру

- алгоритм күрделілігі анықтықталуы

- жады бойынша басқа программалау тілінде айырмашылықтың көрсетілуі

Зерттеу объектісі: теориялық материалды пайдалынып, бағдарламаны іске асыру болып табылады

Курстық жұмыстың құрылымы: жұмыс 2 бөлімнен тұрады: Стек ұғымына толық сипаттама беру бөлімі және Дек тақырыбына толық түсіндірме бөлімінен тұрады. Олар бірнеше бөлімшілерден құралған. Әр бөлімнің өзіндік мазмұны және мысал, диаграммалармен құрастырылған. Жұмыс соңында қортынды жазылып және пайдалынылған әдебиеттер тізімі шет елдің туынды кітаптарынан тұрғаны ескертілді.

Анықтама жеңілдігі үшін әрбір тізім үшін өмірлік мысалдар берілген. Байланысты таралу түсінігі беріліп, алынған білімді программалауда қолдануға мүмкіндік беретін динамикалық ақпараттық құрылым түсінігі қысқаша зерттеледі. Сонымен қатар, әрбір тізім нақтырақ және толық бөлек қарастырылады және белгілі бір жағдайларда тізімдерді пайдаланудың орындылығы көрсетіледі.

1.Стек ұғымына толық сипаттама беру бөлімі

1.1 Негіздерімен танысу

Стек - деректер құрылымдарының бірі. Яғни, деректер құрылымы - бұл деректерді сақтау әдісі: мысалы, байланыстырылған тізімдер, ағаштар, кезектер, жиындар, хэш кестелер, карталар және т.б. Стек Javа-да List интерфейсін қосымша жүзеге асыратын векторлық классты толықтырады. Клас негізі «соңғы келген-бірінші шығады» LIFO (Last In - First Out) принципіне негізделген. Негізгі операциясы – элементті стекке кірістіру (кіргізу) және стектен шығару – тек стектің жоғарғы жағында, яғни оның жоғарғы элементімен орындалады.

Стек деректер тізбегін сақтайды. Деректер келесідей байланыстырылған: әрбір элемент келесіде пайдаланылуы қажет элементке нұсқайды. Бұл сызықтық байланыс – деректер бірінен соң бірі жүреді және оларды бірінен соң бірін алу керек. Сіз буманың ортасынан ала алмайсыз. Стектің негізгі принципі - стекке жақында енгізілген деректер алдымен пайдаланылады. Неғұрлым тез ұяшыққа кірсе, соғұрлым кеш қолданылады. Пайдаланылғаннан кейін стек элементі жоғалады және келесі элемент жоғарғы болады. Стек-бұл сызықтық байланыстырылған тізімнің ерекше жағдайы, ол үшін элементтерді тек тізімнің бір ұшынан қосуға немесе жоюға рұқсат етіледі, бұл стек шыңы деп аталады.[1]

Деректерді стекпен ұйымдастыру мыналарды орындау қажет болғанда тиімді:

- параметрлерді пайдалана отырып қолданбалы әдістер арасында мәліметтер алмасу;

- әртүрлі өрнектерді талдау.

Бағдарламалауда стек әртүрлі тәсілдермен жүзеге асырылуы мүмкін, мысалы:

- статикалық массив ретінде;

- динамикалық массив ретінде;

- жеке байланыстырылған тізім ретінде;

- қосарланған тізім ретінде.

5

Стекке және оның элементтеріне келесі операцияларды орындауға болады:

- стекке элемент қосу (басу);

- элементті стектен шығару (жою) (поп);

- стектің жоғарғы жағындағы элементті стектен шығармай қарау

- стектің бос екенін тексеру;

- стектегі элементтердің санын анықтау;

- бүкіл стекті көрсету (қарау)

Программада Stack құру үшін, бірінші java util пакетіне импорт жасаймыз, сосын Stack классына объект енгіземіз. (1-сурет)

- Жаңа жолдан Stack деп жазылу қажет

- <тип данных> мұнда стекке сақталатын деректер түрін жазуымыз керек.

- <имя> стек атын беру

Stack STACK = new Stack();

1. 
   Сурет
   

1-сурет
6

1.2. Стектің жадыда басқарылуы

Мәндер немесе нысан сілтемелері бар жаңа әдіс шақырылғанда, олар үшін стектің жоғарғы жағында жад блогы бөлінеді. Бұдан біз стекке әдістерде жасалған қарабайыр айнымалылардың мәндерін, сондай-ақ әдіс сілтеме жасайтын үймедегі нысандарға сілтемелерді сақтайды деген қорытынды жасауға болады. Әдіс орындалуды аяқтаған кезде оның қажеттіліктері үшін бөлінген жад блогы (frame) тазартылады және келесі әдіс үшін бос орын қолжетімді болады. Бұл жағдайда бағдарлама ағыны осы әдіс шақырылған жерге оралады, содан кейін кодтың келесі жолына өтеді.

Біз қарастырғандардан басқа, стектің басқа қасиеттері де бар:

- Стек жаңа әдістер шақырылып, аяқталған сайын толтырылады және шығарылады.

- Стектегі айнымалылар оларға жасалған әдіс орындалғанша дейін сақталады

- Стек жады толы болса, Java java.lang.StackOverFlowError жібереді

- Жады орны үймеге (head) қарағанда бұл аймаққа жылдамырақ қол жеткізіледі.

- Ол ағынға қауіпсіз, өйткені әрбір ағын үшін бөлек стек жасалады [7]

Жоғарыда талқыланған ақпаратқа сүйене отырып, мысал кодында жадының қалай басқарылатынын талдайық:

class Person {
int id;
String name;

public Person(int id, String name) {
this.id = id;
this.name = name;
}}
public class PersonMan{
private static Person manPerson(int id, String name) {
return new Person(id, name);
}

public static void main(String[] args) {
int id = 18;


String name = "Askar";
Person person = null;
person = manPerson(id, name);
7

1. 
   main() әдісті орындауды бастамас бұрын, осы әдістің примитивтері мен сілтемелерін сақтау үшін стекте бос орын бөлінеді:
   

• 
  int түрінің idтікелей стекте сақталады;
  
• 
  Стекте String түріндегі name айнымалы атауы жасалады, бірақ «Askar» жолының өзі String pool (head бөлігі) деп аталатын аймақта сақталады;
  
• 
  Person типі сілтеме айнымалысы person да стек жадында жасалады, бірақ үймеде орналасқан нысанды көрсетеді;
  

2. 
   Стектің main() әдісінен Person (int, String) параметрлері бар конструкторды шақыру үшін main () әдіске алдыңғы шақырудың үстіне жад блогы бөлінеді, ол мыналарды сақтайды:
   

• 
  this - ағымдағы объектіге сілтеме;
  
• 
  қарапайым мән id ;
  

3. 
   main әдісте manPerson әдісі қосымша шақырылады, ол үшін стектегі жад блогы алдыңғы шақырудың үстіне бөлінеді. Бұл блок айнымалы мәндерді жоғарыда сипатталған тәсілмен қайтадан сақтайды.
   
4. 
   Person түріндегі жаңадан жасалған person объекті үшін барлық айнымалы мәндер үйме(head) жадында сақталады.
   

2-суретте жоғарылда келтірілген түсініктемелер бойынша сызба көрсетілген

2. 
   сурет
   

8

Стек Бағдарламалауда стекті пайдалану: Басқа тапсырмаға ауысу қажет болғанда әлі аяқталмаған жұмыстарды сақтау керек. Стек аяқталмаған жұмыстың күйін соңына дейін уақытша сақтау үшін пайдаланылады. Күйді сақтағаннан кейін компьютер басқа тапсырмаға ауысады. Орындалуының соңында күтудегі жұмыс күйі стектен қалпына келтіріледі және компьютер үзілген жұмысты жалғастырады.

Стек Бағдарламалауда стекті пайдалану: грамматикаларды талдауда (қарапайым алгебралық өрнектерден бағдарламалау тілдеріне дейін) нұсқаулықты орындау үлгісі ретінде рекурсияны модельдеу құралы ретінде қолданылады.

1.3. Идеясын мысал бойынша ашу


Стек идеясын түсіндірудің ең жақсы жолы - аналогияны пайдалану. Мысалға,келген хаттарды үстел үстіне үйіп тастап, жинақталған поштаны жоғарыдан төменге қарай реттеуде ең бірінші болып жатқан хатты алу. Біріншісін қарағаннан кейін келесі конвертке көшіп, оны қалған хаттар үстіне қояды. Сонда ең соңғы болып келген хат барлық конверттердің үстіне қойылады. Яғни стектің соңғы элементі жоғарғы болу үшін алдымен қалғандарының барлығын шығару керек (3-сурет)

Stack Workshop қолданбасы стектің қалай жұмыс істейтінін жақсырақ түсінуге көмектеседі. Терезеде қолданбаларда төрт түйме бар: New, Push, Pop және Peek

New Push Pop Peek Number:



4

Top 3 433

2 544

1 286

1. 
    255
   

3-сурет

9

Stack Workshop бағдарламасының орындалуы массивке негізделген, сондықтан терезеде көрсетілген ұяшықтар қатары. Дегенмен, стекке қол жеткізу оның үстіңгі шыңымен шектелген, сондықтан элементтерге индекс бойынша қол жеткізе алмаймыз. Стек тұжырымдамасы және оны жүзеге асыру үшін пайдаланылатын деректер құрылымы мүлдем басқа ұғымдар.

Стекте массивтегідей индекстер жоқ, яғни белгілі бір элементке сілтеме жасай алмайсыз. Себебі стек байланыстырылған тізімдерге салынған.

Кнопка Push

Кнопка Push жаңа элементтерді стекке енгізеді. Қызыл көрсеткіш әрқашан стектің жоғарғы жағын, яғни соңғы болып енгізілген элементті көрсетеді. Кірістіру процесіне назар аударсақ, көрсеткіш Top жоғары көтеріледі де, ал екінші элемент ұяшыққа салынады.Процесс солай қайталана береді.

Кнопка Pop

Деректер элементін стектің жоғарғы жағынан шығару үшін Pop түймесін баcу. Алдымен элемент Top сілтеме арқылы көрсетілген ұяшықтан шығарылады, содан кейін Top азаяды және жоғарғы орналасқан ұяшыққа ауыстырылады. Бұл әрекеттердің реті Push әрекеті үшін қолданылатын ретке қарама-қарсы. Top маркер төменде түскеннен кейін олардың позициялары, бұл элементтер қол жетімсіз болады. Соңғы элемент стектен шығарылғаннан кейін Top маркер төменгі ұяшықтың астында –1 белгісін көрсетеді. Бұл позиция стектің бос екендігінің белгісі. Бос стектен элементті шығаруға әрекеттенген кезде, бос стектен осындай хабарландыру шығады «Can’t pop: stack is empty».

Кнопка Peek

Элементтерді кірістіру және шығарып алу екі негізгі стек операциясы болып табылады. Дегенмен кейбір жағдайларда стектің жоғарғы жағындағы мәнді алып тастамай, оқу пайдалы болуы мүмкін. Peek түймесін бірнеше рет басу арқылы сіз Top элементінің мәні сан мәтін жолағына көшіріліп, бірақ элементтің өзі стекте қалатынын көресіз.[3]

1.4 Стек тәсілдерінің негізгі қызметтері және оларды программада қолдану

Жоғарыда келтірілген мысал stack тәсілдеріне байланысты жасалған болатын.

10

Қорытындылай келе, программада қолданыталын Stack тәсілдеріне мыналар жатады:

1. 
   push(Object element) (O(1))
   

Элементты стекка салады, жәнеде элемент қайтарады.

2. 
   peek()(O(1))
   

Стектің жоғарғы жағындағы элементті қайтарады, бірақ оны жоймайды.

3. 
   pop() (O(1))
   

Стектің жоғарғы жағындағы элементті қайтарады, процесс кезіңде жояды.

4. 
   boolean empty() (O(1))
   

Стек бос екенін тексереді. Стек бос болса, шын мәнін қайтарады (true). Стекте элементтер болса, жалған мәнін қайтарады (false).

5. 
   int search(Object element) (O(n))
   

Стектен элементті іздейді. Элемент табылса стектын жоғары жағынан қайтарылады. Табылмаған жағдайда 1 қайтарылады.

6. 
   Head() немесе Top()
   

Стектің жоғарғы жағында орналасқан элементті қараcтырады.

Осы операцияларды қолдана отырып әрқайсысын жеке-жеке программада іске асуын төменде қарастырамыз:

1) Элементтерді қосу: Элементті стекке қосу үшін push () әдісін қолдануға болады. Бұл push () әрекеті элементті стектің жоғарғы жағына итереді.

// стекті инициализациялау
Stack stack1 = new Stack();
Stack stack2 = new Stack();
// push методымен стекке элементтерди киргизу
stack1.push(25);
stack1.push("студент");
stack1.push("СИБ-29");
// 2ши стек элементтери
stack2.push("ФИТ");
stack2.push("ФЕН");
stack2.push("АСФ");
11

// Экранга 2 стекти шыгару
System.out.println(stack1);
System.out.println(stack2);
Консоль:

[25, студент, СИБ-29]

[ФИТ, ФЕН, АСФ]

Осы жерден алгоритм күрделігін анықтап кетсек: төмендегі сурет кейбір деректер құрылымдарын және олардың төрт операцияның әрқайсысы үшін қаншалықты күрделі екенін көрсетеді. (4-сурет)

Push() алгоритмнің күрделілігі O (1) – тұрақты. Себебі: операциялардың саны өспейді және кіріс деректерінің кез келген мәндері үшін тұрақты. Бөлім амалдар санын көрсетпейді, сондықтан күрделілік тұрақты болады.[6]
2) Элементке қол жеткізу: стектің бірінші элементін немесе стектің жоғарғы жағындағы элементті шығару үшін peek () әдісін қолдануға болады. Шығарылған элемент стектен жойылмайды.

Stack stack = new Stack();

// push() методымен стекке киргизу
stack.push("1st");
stack.push("2nd");
stack.push("3th");
stack.push("last element");
System.out.println("1st stack: " + stack);
// Сонгы элементты аныктау peek() метод
System.out.println("The element at the top of the"
+ " stack is: " + stack.peek());

// Операциядан кейнги стекты шыгару
System.out.println("Final Stack: " + stack);

12
Консоль:

1st stack: [1st, 2nd, 3th, last element]

The element at the top of the stack is: last element

Final Stack: [1st, 2nd, 3th, last element]

Peek() алгоритмнің күрделілігі O (n)-сызықтық. Себебі: тізімнің басындағы элементтерді өңдеу арқылы біз барлық кейінгі элементтердің индекстерін жаңартуымыз керек болғансон.

3) Стектен элементті жою үшін pop () әдісін қолданамыз. Элемент стектің жоғарғы жағынан шығарылады және жойылады. Шартты міндеті:

- Біз жоюымыз керек ұяшық - стектің шыңы болып табылады

- Жою керек ұяшық соңында немесе екі ұяшық арасында орналасуы

stack.push("23");
stack.push("14");
stack.push("5");
stack.push("18");
System.out.println("1st stack: " + stack);
// pop() метод аркылы стектен элементты жою
System.out.println("Popped element: "
+ stack.pop());
System.out.println("Popped element: "
+ stack.pop());
// Жана стекты шыгару
System.out.println("Stack after pop operation "
+ stack);

Консоль:

1st stack: [23, 14, 5, 18]

Popped element: 18

Popped element: 5

Stack after pop operation [23, 14]

Pop() алгоритмнің күрделілігі O (1) – тұрақты. Себебі: операциялардың саны өспейді және стекте элемент енгізілуі, жоюлуы,ізделіну операцияларына тұрақты болып келеді. Амалдар саны жоқ, сондықтан O(1)- const

13

4) Стектегі басқа операциялармен жұмыс:

- Стектың бостығын тексеру

- Стек өлшемін табу

- Стектегі ізделінген элементті көрсету

Stack stack = new Stack<>();
stack.push("pen");
stack.push("pencil");
stack.push("book");
stack.push("bag");
System.out.println("Stack : " + stack);
// Empty() тәсілімен стекке элементтерді кіргізіп және өшіре отырып,онын бостығын тексеру
System.out.println("Is Stack empty? : " + stack.isEmpty());
// Стек размерын size() аркылы табу
System.out.println("Size of Stack : " + stack.size());
// search() әдісі 1-ден бастап стектің жоғарғы жағындағы элемент орнын қайтарады
// Элемент стектен табылмаса -1 қайтарады
int position = stack.search("pencil"); //изделинис устиндеги элемент орнын жариялау
if(position != -1) {
System.out.println("Found the element \"pencil\" at position : " + position);
} else {
System.out.println("Element not found");
Консоль:

Stack : [pen, pencil, book, bag]

Is Stack empty? : false

Size of Stack : 4

Found the element "pencil" at position : 3
Алгоритм күрделігі: О(n)

https://github.com/NurlybekMakhambet/Staack

5. 
   Try| catch in Stack
   

//Стак класына обьект жасау
Stack stk = new Stack<>();
System.out.println("stack: " + stk);
//стекке сандар енгизу
pushelmnt(stk, 20);
pushelmnt(stk, 13);
pushelmnt(stk, 89);
pushelmnt(stk, 90);
pushelmnt(stk, 11);
pushelmnt(stk, 45);
pushelmnt(stk, 18);

14


//стектеги элементтерди шыгару
popelmnt(stk);
popelmnt(stk);

//try аркылы текскрип егер стекте элемент калмаса catch-пен тексерип егер ерекше баска ответ шыгып жатса System.out.println("empty stack") осы строканы шыгарамыз
try
{
popelmnt(stk);
}
catch (EmptyStackException e)
{
System.out.println("empty stack");
}
}
static void pushelmnt(Stack stk, int x)
{
//пуш адисин шакыру
stk.push(new Integer(x));
System.out.println("push -> " + x);
//жана косылган сандармен шыгару
System.out.println("stack: " + stk);
}
static void popelmnt(Stack stk)
{
System.out.print("pop -> ");
//поп методын шакыру
Integer x = (Integer) stk.pop();
System.out.println(x);
//поптан кейынгы калган сандарды шыгару
System.out.println("stack: " + stk);
}
Алгоритм күрделігі: О(1)

https://github.com/NurlybekMakhambet/trycatch
Енді массив арқылы стекті қалай жүзеге асыру керектігін талдап кетсек:

Төменде біз 10 элементі бар steck деп аталатын массив жасадық, сонымен қатар стектің жоғарғы элементін көрсететін i айнымалысын енгіздік. Элементті қосу үшін біз i-ді бір-бірден арттырамыз және элементті стектің [i] ұяшығына жазамыз. Элементті жою үшін біз жай ғана i-ді бір-бірден азайтамыз. Стектің жоғарғы элементіне сілтеме жасау үшін біз жай ғана массивтің i элементіне сілтеме жасаймыз. i айнымалысы push () және top () функцияларының орнын басты. Стектің бос екенін көру үшін біз жай ғана

i == -1 шартын тексереміз.

15

C++

#include

 

using namespace std;

 

int main() {

  int steck[10];

  int i = -1;  // стекты жарияладык

    

  for (int j = 0; j < 5; j++) {

    int a;

      

    cin >> a;      

 

    i++;  // 1 ге арттыру

      

    steck[i] = a;  // стекке элемент саламыз

  }

  

  if (i == -1) cout << "Стек бос";  

    

  cout << steck[i] << " стектин жогаргы элементи";

    

  cout << "Жогаргы элементин жоямыз»

    

  i--;  // 1 ге кемитемиз}
Екінші жолмен қарастырсақ:

using namespace std;

const int MAX_SIZE=10; //массивтеги элемент саны

struct my_stack //Стек курылымы

{

int data[MAX_SIZE];//Массив MAX_SIZE элемент санымен

int last; //Указатель стектин жогаргы жагына

};

void push(my_stack &s, int x)//Элементтер косу процедурасы

{

if (s.last==MAX_SIZE){ //Хабарландыру егер стек толы болса

cout<<"Stack толды";

return;}

s.data[s.last++]=x;

}

int pop(my_stack&s) //стек шыңынан элемент алу

{

return s.data[--s.last];//элемент шыңынан кайтару жолы

}

int main()

{

my_stack a;

a.last=0;

push(a,3);

push(a,6);

push(a,2);

cout<
2 программа шыгарады

cout<
6

cout<
3

} // Алгоритм күрделілігі: О(1)
16

Стекті push әдісімен толтыра отырып, біз әрбір жаңа элементті соңына дейін итереміз. стектің жоғарғы жағын шығару арқылы біз мәнді қайтарамыз,содан кейін сол элементті жойдық. Әрқайсысының күрделілігі O (1).

Жоғарыда стекті енгізудің екі әдісі талданды, яғни олар:

• 
  Java үлгісінде функцияларды пайдалану.
  
• 
  Массивті пайдалана отырып енгізу.
  

2. Дек тақырыбына толық түсіндірме бөлімі

2.1 Дек интерфейсін пайымдау

Java-да Deque - бұл кезек пен стекті біріктіретін деректер құрылымы және бұл java.util бумасына жататын Java интерфейсі және ол java.queue интерфейсін жүзеге асырады. Degue атауы «қос кезек» (“double-ended queue” )

мағынасын білдіреді. Дектің басы және аяқ жағынан элементтерді қосуға және жоюға болады. «Дәстүрлі» кезекте элементтерді жолдың соңына (соңғы элементтен кейін) қосасыз және элементтерді кезектің алдыңғы жағынан алып тастайсыз. Бұл принцип «First in First out» (FIFO) деп аталады және ол өмірде қарапайым кезек күтушілер қатары сияқты жұмыс істейді (5-сурет). Демек, бұл стек пен кезектің қоспасы ретінде орындалады. Оны кезек (FIFO) және стек (LIFO) орнына қолдануға болады. Дек Stack және LinkedList - тан қараған тезірек жұмыс жасайды.[1]



5-сурет

17

Дектің қасиеттеріне осылар жатады:

- Java тіліндегі Deque – іске асырулары өлшемі өзгертілетін массивке қолдау көрсететін интерфейс. Осылайша сізде шектеусіз мүмкіндіктер жинағы болады және қажеттіліктеріңізге сәйкес жаңа элементтерді қосуға болады.

- Бірнеше ағынды бір мезгілде қол жеткізуге Deque қолдау көрсетпейді

- Сыртқы синхрондау болмаған кезде Deque ағыны қауіпсіз емес.

- Deque массивінде нөлдік элементтерге рұқсат етілмейді.

Төмендегі диаграммада (6-сурет) deque иерархиясы көрсетілген. Төмендегі диаграммада көрсетілгендей, Deque интерфейсі кезек интерфейсіне дейін созылады, ол өз кезегінде жинақ интерфейсін кеңейтеді. LinkedList класы кезекті немесе декті модельдеу үшін қосарланған байланыстырылған тізімді пайдаланады. ArrayDeque класы массив ішіндегі элементтерді сақтайды.

Егер элементтер саны массив өлшемінен асып кетсе, жаңа массив бөлінеді және барлық элементтер жылжытылады. Бұл қажеттілік есебінен өседі деген сөз.



6-сурет

18

Deque интерфейс болғандықтан, deque түріндегі объект құру мүмкін емес. Объект жасау үшін бізге әрқашан осы тізімді кеңейтетін клас қажет. Сондай-ақ, Java -да жалпы модульдер енгізілгеннен кейін, Deque-де сақтауға болатын объект түрін шектеуге болады. Бұл қауіпсіз кезекті келесідей анықтауға болады:

// Obj- Декте сақталатын объект типі
Deque deque = жаңа массив ();
public class DequeExample {
public static void main(String[] args)
{
Deque deque = new LinkedList();
// String декте сакталатын объект типі

LinkedList класы декпен жұмыс істегенде жиі қолданылады. Ол элементтердің санына шектеусіз және екі шетінен элементтерді қосу және жоюдың жылдам әдістерін жүзеге асырады. ArrayDeque класы элемент шегі жоқ басқа іске асыру болып табылады. Ол жоғары өнімділік үшін индекстік қаптаманы жүзеге асырады. Барлық жинақ енгізулері сияқты, бұл іске асырулар да ағынмен қауіпсіз емес.[1]

2.2 Дек тәсілдерінің қызметі

Deque интерфейсі push, pop және pop сияқты жалпы стек әрекеттерін орындауға мүмкіндік беретін әдістерді анықтайды.

Deque Әдістері:

• 
  boolean offerFirst(E) Deque тізімінің аяқ жағына элемент қосады. Сәтті болғанда true мәнін қайтарады, егер бос орын жоқ болса, IllegalStateException шығарады
  

• 
  boolean offerFirst(E) Deque алдына элементті кірістіреді. Егер Deque сыйымдылығы толы болса немесе кірістіру сәтсіз болса, әдіс false ​​қайтарады, кері жағдайда true. (7-сурет)
  

19



7-сурет

• 
  boolean addLast(E) Deque соңына элемент кірістіреді. Бұл әдіс Deque толы болса, ерекше жағдайды шығарады. Егер кірістіру сәтті болса, әдіс "true" мәнін қайтарады.
  

• 
  boolean offerLast(E) Deque соңына элемент енгізеді. Егер Deque сыйымдылығы толы болса немесе кірістіру сәтсіз болса, әдіс false ​​қайтарады, кері жағдайда true қайтарады.(8-сурет)
  

8-сурет

• 
  E removeFirst()Deque-тегі бірінші элементті қайтарады және оны Deque ішінен жояды. Бұл әдіс Deque-те элемент болмаса, ерекше жағдайды шығарады
  
• 
  E pollFirst() Deque-тегі бірінші элементті қайтарады және оны Deque ішінен жояды. Бұл әдіс Deque-те элемент болмаса, null шығарады.(9-сурет)
  

(9-сурет)

20

• 
  E removeLast()Deque-тегі бірінші элементті қайтарады және оны Deque ішінен жояды. Бұл әдіс Deque-те элемент болмаса, ерекше жағдайды шығарады.
  

• 
  E pollLast() Deque-тегі бірінші элементті қайтарады және оны Deque ішінен жояды. Бұл әдіс Deque-те элемент болмаса, null шығарады (10-сурет)
  

10-сурет

• 
  E getFirst()Deque-тегі бірінші элементті қайтарады және оны Deque ішінен жояды. Бұл әдіс Deque-те элемент болмаса, ерекше жағдайды шығарады.
  

• 
  E peekFirst() Deque-тегі бірінші элементті қайтарады және оны Deque ішінен жояды. Бұл әдіс Deque-те элемент болмаса, null шығарады.(11-сурет)
  

11 - сурет

• 
  push (элемент) дек басына элемент қосады.
  
• 
  pop (элемент) элементті тақырыптан жояды және оны қайтарады
  

21

Ыңғайлы түрде операция түрлерін кесте түрінде:


get () әдісі анықталмаған, себебі element () әдісі Queue интерфейсінен мұраланған интерфейс әдісі болып табылады. Get әдістері removeXXX () әдістеріне ұқсас және декв бос болса, NoSuchElementException жіберіңіз. Бұл жағдайда peek әдістері нөлді қайтарады. Әрине, сіз нөлдік элементтерді қосуға болатындықтан, нөлдік элемент пен бос декті ажырата алмайсыз. Бұл жерде size () әдісі қолайлы.

iterator () әдісін және соңынан басына дейін кері іздеу үшін descedingIterator () әдісін пайдаланыңыз. Дегенмен, элементке оның орналасқан жері бойынша қол жеткізе алмайсыз, кем дегенде бұл механизм Deque интерфейсіне қосылмаған. Дегенмен, Deque интерфейсін жүзеге асыратын LinkedList класы List интерфейсі арқылы еркін элементке қол жеткізуге мүмкіндік береді, оны да жүзеге асырады. Кездейсоқ қол жеткізу талабын сақтамай, Deque интерфейсін тиімдірек енгізуге болады.[8]


:

Операция түрі	Бірінші элемент (Басы)	Соңғы элемент (соңы)
Элемент қосу	addFirst(e) offerFirst(e)	addLast(e) offerLast(e)
Элемент жою	removeFirst() pollFirst()	removeLast() pollLast()
Элементті тексеру	getFirst() peekFirst()	getLast() peekLast()

2.3 Тәсілдерін программада қолдану: add();remove();

1) Элементтерді қосу: декте элемент қосу үшін add () әдісін қолдануға болады. Стек пен дек арасындағы айырмашылық - декте қосу кез келген бағытта мүмкін болады. Сондықтан, екі шетіне элементтерді қосу үшін пайдаланылатын addFirst () және addLast () деп аталатын екі қол жетімді әдіс бар.


22

// декке иницилизация
Deque dq = new ArrayDeque();

// add() методын енгизу
dq.add("sabakta");
dq.addFirst("bugingi"); // дек тизимине биринши салынады
dq.add("kurstyk zhymys");
dq.addLast("korgau");// сонгы болып киреди
System.out.println(dq);

Консоль: бугинги сабакта курстык жумыс коргау

2) Элементтерді жою: Дектен элементті алып тастаудың әртүрлі әдістері бар. Біз екі жағынан да алып тастай алатындықтан, deque интерфейсі бізге removeFirst (), removeLast () әдістерін береді. Бұған қоса, бұл интерфейс бізге poll (), pop (), pollFirst (), pollLast () әдістерін ұсынады, онда pop () жарнама тақырыбын жою және қайтару үшін пайдаланылады. Дегенмен, сауалнама () пайдаланылады, себебі ол pop () функциясымен бірдей функцияны ұсынады және deque бос болғанда ерекше жағдайды қайтармайды.

// декке иницилизация
Deque dq = new ArrayDeque();
dq.add("students");
dq.addFirst("studying");
dq.addLast("in univer");

System.out.println(dq);

System.out.println(dq.pop());
System.out.println(dq.poll());

System.out.println(dq.pollFirst());// биринши элементын жою

System.out.println(dq.pollLast()); // элемент болмаса null шыгарады
}

Консоль: [studying, students, in univer]

Null

3) Deque қайталануы: Deque екі бағытта да қайталануы мүмкін болғандықтан, deque интерфейсінің итератор әдісі бізге қайталаудың екі әдісін береді. Біреуі басынан, екіншісі артқы жағынан.

23

// add() тасилин енгизу
dq.add("add");
dq.addFirst("pop");
dq.addLast("pull");

for (Iterator itr = dq.iterator();
itr.hasNext();) {//hasNext()шақырғанда, ол ақиқат мәнін қайтарады (себебі бізде сканер нысанында байланыстырылған s жолы бар).
System.out.print(itr.next() + " ");
}System.out.println();
for (Iterator itr = dq.descendingIterator();//бул итератор катарды элемент бойынша кери ретимен кайтарады
itr.hasNext();) {
System.out.print(itr.next() + " ");
}
} Консоль: pop add pull pull add pop

алгоритм күрделілігі: O(n^2)

Жоғарды түсіндіріліп кеткен бірнеше тәсілдерді қолданып, мысал есеп корсетсек:

Deque deque = new LinkedList();

// Ар турли жагдаймен декке элемент енгиземиз

deque.add(" 1 Hvost"); // сонына енгизу
deque.addFirst("2 (Head)");
deque.addLast(" 3 (Hvost)");
deque.push("4 (Head)"); // басына киргизу
deque.offer(" 5 (Hvost)");
deque.offerFirst("6 (Head)");
System.out.println(deque + "\n");
// Кезекпен декти сорттау



System.out.println("Durys Iterator tizimi");

Iterator iterator = deque.iterator();
while (iterator.hasNext()){//hasNext()шақырғанда, ол ақиқат мәнін қайтарады (себебі бізде сканер нысанында байланыстырылған s жолы бар).
System.out.println("\t" + iterator.next());

// Кери реттеги итератор тизимин шыгару

//бул итератор катарды элемент бойынша кери ретимен кайтарады
Iterator reverse = deque.descendingIterator();
System.out.println("Keri Iterator tizimi");

while (reverse.hasNext())
System.out.println("\t" + reverse.next());


24
// Peek биринши элементти жоймай кайтарады
// дектен
System.out.println("Peek " + deque.peek());
System.out.println("After peek: " + deque);

// Pop биринши элементти дектен жойып кайтарады
System.out.println("Pop " + deque.pop());
System.out.println("After pop: " + deque);
// Декте элементтер бар не жок екенин тексере аламыз
System.out.println("Teksery "+ deque.contains(" 3 (Hvost)"));
// Биринши жане сонгы элементты дектен оширу



deque.removeFirst();
deque.removeLast();
System.out.println("Deque after removing " + "first and last: " + deque);

https://github.com/NurlybekMakhambet/deque

Консоль: [6 (Head), 4 (Head), 2 (Head), 1 Hvost, 3 (Hvost), 5 (Hvost)]

Keri Iterator tizimi

5 (Hvost)

3 (Hvost)

1 Hvost

2 (Head)

4 (Head)

6 (Head)

Peek 6 (Head)

Pop 6 (Head)

After pop: [4 (Head), 2 (Head), 1 Hvost, 3 (Hvost), 5 (Hvost)]

Teksery: true

Deque after removing first and last: [2 (Head), 1 Hvost, 3 (Hvost)]

Алгоритм күрделілігі: O(n)

Себебі: Push() және Pop() алгоритмнің күрделілігі O (1) – тұрақты. Себебі: операциялардың саны өспейді және стекте элемент енгізілуі, жоюлуы,ізделіну операцияларына тұрақты болып келеді. Амалдар саны жоқ, сондықтан O(1)- const

Peek() алгоритмнің күрделілігі O (n)-сызықтық. Себебі: тізімнің басындағы элементтерді өңдеу арқылы біз барлық кейінгі элементтердің индекстерін жаңартуымыз керек болғансон.

Есептеу жолы бойынша O(1) * O(1) * O(n)= O(n) [1]

25

Қорытынды

Топтық курстық жұмыста біз стек және дек ұғымдарын толық және көрнекті түрде ашуға тырыстық. Қазіргі ақпараттар технологиясындағы өзектілігі жайлы және және белгілі бір жағдайларда тізімдерді пайдаланудың орындылығы көрсетіледі.

Кіріспе бөліміндегі қойылған мақсаттар бойынша келесі міндеттер анықталды:

- Stack and deque ұғымдарына түсініктеме, прогаммада жариялану және жадыда басқарылуы жайлы таныстыру жүргізілді

- Программада қалай жүзеге асуын, қолданылатын аймақтары туралы қарастырдық

- Түсіндерме материал идеясын мысал, диаграммалар арқылы жеткізілді

- Тәсілдерін жеке-жеке талданып және мысал есептертермен программада көрсетілді

- Массивты стекте пайдалана отырып, есептер с++ тілінде талданды

- Әр көрсетілген есептің алгоритм күрделілігі анықталып отырды

Қосымша есепте біз шарт бойынша бірнеше классты мұрагерлеп, инкапсуляция және конструкторларды шақыру арқылы, дек пен кезекті пайдаланып тізім сонына элемент енгізу кодын жазып, гитхаб сілтемесіне жүктедік.

26

Қолданылған әдебиеттер тізімі

1. 
   Герберт Шилдт - Java 8 Толық шығарлымы (9 бөлімі), 2015
   
2. 
   Кэти Сьерра и Берт Бейтс – Java тілін оқу, 2012,
   
3. 
   Андасова.Б.З – Java программалау тілі/Астана: 2014/ ЕНУ
   
4. 
   Ж.К.Нурбекова, М.С. Сауханова- Программалау практикумы/ Астана: 2013/ ЕНУ
   
5. 
   Брюс Эккель - Философия Java ( 4 бөлімі)
   
6. 
   Майк МакГрат | Бастаушыларға Java тілінде бағдарламалау(2016)
   
7. 
   Си тілінде Бағдарламалау: Бағдарламалау бойынша әдістемелік ұсынымдар мен міндеттер/ Костюкова Н.И.
   
8. 
   Никлаус Вирт алгоритмдері және деректер құрылымы. Оберонға арналған жаңа нұсқа / Никлаус Вирт
   
9. 
   Бағдарламалау технологиялары: оқу құралы / Смирнов а. а., Хрипков Д. В.
   

27

Қосымша

Косымша есеп гитхаб сайтына жүктелінді:

https://github.com/DosBalzhan/QueueDeque/tree/master/src/com/company
Консоль:


28