Стекът има само един край, отворен за натискане и изтласкване на елементите от данни, от друга страна. Опашката има два отвора за отваряне и премахване на елементите от данни.
Стекът и опашката са структури от данни, използвани за съхраняване на елементи от данни и всъщност се основават на някой еквивалент в реалния свят. Например, стека е купчина от компактдискове, където можете да извадите и поставите компактдиск през горната част на стека от компактдискове. По същия начин, опашката е опашка за билети за театър, където лицето, което стои на първо място, т.е. предната част на опашката, ще бъде връчено първо и новото пристигащо лице ще се появи в задната част на опашката (задния край на опашката).
Сравнителна таблица
| Основа за сравнение | купчина | Опашка |
|---|---|---|
| Принцип на работа | LIFO (последно на първо място) | FIFO (Първо на първо място) |
| структура | Същият край се използва за вмъкване и изтриване на елементи. | Един край се използва за вмъкване, т.е. заден край, а друг край се използва за изтриване на елементи, т.е. преден край. |
| Брой използвани указатели | един | Две (в случая с проста опашка) |
| Извършени операции | Push and Pop | Включване и отписване |
| Проучване на състоянието на празно състояние | Най-горе == -1 | Отпред == -1 || Отпред == отзад + 1 |
| Изследване на пълно състояние | Най-горе == Max - 1 | Заден == Max - 1 |
| варианти | Няма варианти. | Той има варианти като кръгова опашка, приоритетна опашка, двойно завършена опашка. |
| изпълнение | Опростено | Сравнително сложен |
Определение на стека
Стекът е непримитивна линейна структура на данните. Това е подреден списък, където се добавя новият елемент и съществуващия елемент се изтрива само от единия край, наречен горната част на стека (TOS). Тъй като цялото изтриване и вмъкване в стека се извършва от горната част на стека, последният добавен елемент ще бъде първият, който ще бъде премахнат от стека. Това е причината, поради която стекът се нарича тип LIFO.
Обърнете внимание, че елементът, който често се използва в стека, е най-горният елемент, докато последният наличен елемент е в дъното на стека.
пример
Някои от вас могат да ядат бисквити (или Poppins). Ако приемете, само една страна на капака е разкъсана и бисквитите се изваждат един по един. Това е, което се нарича popping, и по същия начин, ако искате да запазите някои бисквити за известно време по-късно, ще ги поставите обратно в опаковката чрез същия разкъсан край се нарича бутане.
Определение на опашката
Опашката е линейна структура на данните, която идва в категорията на непримитивния тип. Това е колекция от подобен тип елементи. Добавянето на нови елементи се извършва в единия край, наречен задния край. По същия начин, изтриването на съществуващите елементи става на другия край, наречен Front-end, и логически е списък от тип First in first out (FIFO).
пример
В нашия ежедневен живот се натъкваме на много ситуации, в които изчакваме желаната услуга, там трябва да влезем в линията на чакане за нашия ред да се обслужва. Тази чакаща опашка може да се разглежда като опашка.
Ключови разлики между стека и опашка
- Стекът следва LIFO механизма от друга страна Queue следва FIFO механизъм за добавяне и премахване на елементи.
- В стека, същият край се използва за вмъкване и изтриване на елементите. Напротив, в опашката се използват два различни края, за да се вмъкнат и изтрият елементите.
- Тъй като Stack има само един отворен край, това е причината да се използва само един указател, за да се отнася към горната част на стека. Но опашката използва две указатели за препращане на предната и задната част на опашката.
- Stack изпълнява две операции, известни като push и pop, докато в Queue е известен като enqueue и dequeue.
- Изпълнението на стека е по-лесно, докато изпълнението на опашката е трудно.
- Опашката има варианти като кръгова опашка, приоритетна опашка, двойно завършена опашка и т.н. За разлика от тях, стека няма варианти.
Реализация на стека
Стекът може да се приложи по два начина:
- Статичното изпълнение използва масиви за създаване на стек. Статичното изпълнение е техника, която не изисква усилия, но не е гъвкав начин на създаване, тъй като декларирането на размера на стека трябва да се направи по време на проектирането на програмата, след което размерът не може да се променя. Освен това статичната реализация не е много ефективна по отношение на използването на паметта. Тъй като масив (за реализиране на стека) се декларира преди началото на операцията (по време на проектирането на програмата). Сега, ако броят на елементите, които трябва да се сортират, е много по-малко в стека, статично разпределената памет ще бъде изгубена. От друга страна, ако след това има повече елементи, които да се съхраняват в стека, не можем да променим размера на масива, за да увеличим неговия капацитет, така че да може да побере нови елементи.
- Динамичната реализация се нарича също представяне на свързан списък и използва указатели за прилагане на типа на структурата на данните.
Изпълнение на опашката
Опашката може да бъде изпълнена по два начина:
- Статично изпълнение : Ако една опашка се реализира с използване на масиви, трябва да се гарантира точния брой елементи, които искаме да съхраним в опашката, тъй като размерът на масива трябва да се декларира по време на проектиране или преди започването на обработката. В този случай началото на масива ще се превърне в предната част на опашката и последното местоположение на масива ще действа като задната част на опашката. Следната връзка дава всички елементи, съществуващи в опашката, когато се използват масиви:
отпред - отзад + 1
Ако "заден <фронт", тогава няма да има елемент в опашката или опашката винаги ще бъде празна. - Динамична реализация : Прилагането на опашки с помощта на указатели, основният недостатък е, че възел в свързано представяне консумира повече място в паметта, отколкото съответния елемент в представянето на масива. Тъй като във всеки възел има поне две полета за полето за данни и други за съхраняване на адреса на следващия възел, докато в свързано представяне има само поле за данни. Заслугата за използването на свързаното представяне става очевидна, когато се изисква да се вмъкне или изтрие елемент в средата на група други елементи.
Операции по стека
Основните операции, които могат да се изпълняват по стека, са следните:
- PUSH : когато към горната част на стека е добавен нов елемент, той е известен като PUSH операция. Натискането на елемент в стека извиква добавянето на елемента, тъй като новият елемент ще бъде вмъкнат в горната част. След всяка операция на натискане, горната част се увеличава с една. Ако масивът е пълен и не може да бъде добавен нов елемент, той се нарича STACK-FULL условие или STACK OVERFLOW. PUSH OPERATION - функция в C:
Като се има предвид, че стека е деклариран катоint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP : Когато елемент е изтрит от горната част на стека, той е известен като POP операция. Стекът се намалява с един след всяка операция на поп. Ако в стека няма оставен елемент и попът се изпълнява, това ще доведе до условие STACK UNDERFLOW, което означава, че стека е Empty. ОПЕРАЦИЯ НА ПОЗИЦИ - функции в C:
Като се има предвид, че стека е деклариран катоint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
Операции на опашка
Основните операции, които могат да се извършват на опашката, са:
- Enqueue : За да вмъкнете елемент в опашката.
Опашката се декларира катоint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : За да изтриете елемент от опашката.
Опашката се декларира катоint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Приложения на Stack
- Анализиране в компилатор.
- Java виртуална машина.
- Отмяна в текстов редактор.
- Бутон Назад в уеб браузър.
- Език на PostScript за принтери.
- Прилагане на функционални повиквания в компилатор.
Приложения на опашка
- Буфери за данни
- Асинхронен трансфер на данни (IO файл, тръби, гнезда).
- Задаване на заявки за споделен ресурс (принтер, процесор).
- Анализ на трафика.
- Определете броя на касиерите, които ще имате в супермаркет.
заключение
Stack and Queue са линейни структури на данни, които се различават по определени начини като работен механизъм, структура, реализация, варианти, но и двете се използват за съхраняване на елементите в списъка и извършване на операции в списъка като добавяне и изтриване на елементите. Въпреки че има някои ограничения на простата опашка, която се възстановява чрез използване на други видове опашки.
