Разлика между стека и опашката

Автор: Laura McKinney
Дата На Създаване: 2 Април 2021
Дата На Актуализиране: 11 Може 2024
Anonim
12 ЗАМКОВ, 12 ЗАМКОВ Найди отличия УРОВЕНЬ 2
Видео: 12 ЗАМКОВ, 12 ЗАМКОВ Найди отличия УРОВЕНЬ 2

Съдържание


И Stack, и Queue са непримитивните структури от данни. Основните разлики между стека и опашката са, че стекът използва LIFO (последен в първи изход) метод за достъп и добавяне на елементи от данни, докато Queue използва FIFO (First in first out) метод за достъп и добавяне на елементи от данни.

Стекът има само един край отворен за натискане и изскачане на елементите с данни от друга страна, опашката има и двата края отворени за въвеждане и премахване на елементите от данни.

Стека и опашката са структурите от данни, използвани за съхранение на елементи от данни и всъщност се основават на някакъв еквивалент в реалния свят. Например, стекът е стек от CD, от който можете да извадите и поставите CD през горната част на стека от компактдискове. По подобен начин опашката е опашка за билети за театър, при която човекът, стоящ на първо място, т.е. предната част на опашката ще бъде обслужена първо, а новият пристигнал ще се появи в задната част на опашката (задната част на опашката).


  1. Сравнителна диаграма
  2. дефиниция
  3. Ключови разлики
  4. изпълнение
  5. Операции
  6. Приложения
  7. заключение

Сравнителна диаграма

Основа за сравнениекупчина Опашка
Принцип на работаLIFO (Последно в първи изход)FIFO (първи в първи изход)
структураСъщият край се използва за вмъкване и изтриване на елементи.Един край се използва за вмъкване, т.е. заден край, а друг край се използва за изтриване на елементи, т.е. преден край.
Брой използвани указателиединДве (В прост случай на опашката)
Извършени операцииPush and Pop Enqueue и dequeue
Изследване на празно състояниеНай-горе == -1Фронт == -1 || Отпред == отзад + 1
Изследване на пълно състояние
Най-горе == Макс - 1Отзад == Макс - 1
вариантиТя няма варианти.Има варианти като кръгова опашка, приоритетна опашка, опашка с двойно завършване.
изпълнениеПо-простСравнително сложен


Дефиниция на Stack

Стека е непримитивна линейна структура на данни. Това е подреден списък, където новият елемент се добавя и съществуващият елемент се изтрива само от единия край, наречен като върха на стека (TOS). Тъй като цялото изтриване и вмъкване в стек се извършва от горната част на стека, последният добавен елемент ще бъде първият, който ще бъде премахнат от стека. Това е причината стека да се нарича тип Last-in-First-out (LIFO) от списъка.

Обърнете внимание, че елементът, до който често се достига в стека, е най-горният елемент, докато последният наличен елемент е в долната част на стека.

пример

Някои от вас може да ядат бисквити (или Poppins). Ако предполагате, само едната страна на корицата е разкъсана, а бисквитите се изваждат едно по едно. Това е така нареченото пукане и по подобен начин, ако искате да запазите някои бисквити за известно време по-късно, ще ги върнете обратно в опаковката през същия разкъсан край се нарича бутане.

Определение на опашката

Опашката е линейна структура на данните, идва в категорията на непримитивния тип. Това е колекция от подобни видове елементи. Добавянето на нови елементи става в единия край, наречен заден край. По същия начин изтриването на съществуващите елементи става в другия край, наречен Front-end, и логично е тип от списъка First in first out (FIFO).

пример

В ежедневния си живот се сблъскваме с много ситуации, в които изчакваме желаната услуга, там трябва да влезем в чакащата линия, за да дойде редът ни, за да бъдем обслужени. Тази опашка за чакане може да се мисли като опашка.

  1. Stack следва LIFO механизма, от друга страна Queue следва FIFO механизма за добавяне и премахване на елементи.
  2. В стек, същия край се използва за вмъкване и изтриване на елементите. Напротив, в опашката за вмъкване и изтриване на елементи се използват два различни края.
  3. Тъй като Stack имат само един отворен край, това е причината да се използва само един показалец за препратка към горната част на стека. Но опашката използва два указателя за препращане на предния и задния край на опашката.
  4. Stack извършва две операции, известни като push and pop, докато в Queue е известен като enqueue и dequeue.
  5. Изпълнението на стека е по-лесно, докато прилагането на опашката е сложно.
  6. Опашката има варианти като кръгова опашка, приоритетна опашка, опашка с двойно завършване и др. За разлика от тях стека няма варианти.

Изпълнение на стека

Стекът може да се приложи по два начина:

  1. Статично изпълнение използва масиви за създаване на стек. Статичното внедряване е макар и безпроблемна техника, но не е гъвкав начин на създаване, тъй като декларирането на размера на стека трябва да се направи по време на проектирането на програмата, след което размерът не може да се променя. Освен това статичното внедряване не е много ефективно по отношение на използването на паметта. Тъй като масив (за изпълнение на стек) е деклариран преди началото на операцията (по време на проектиране на програмата). Сега, ако броят на елементите за сортиране е много по-малък в стека, статично разпределената памет ще се изхаби. От друга страна, ако има повече елементи, които да се съхраняват в стека, тогава не можем да променим размера на масива, за да увеличим капацитета му, така че да може да побере нови елементи.
  2. Динамично изпълнение се нарича също свързано представяне на списък и използва указатели за реализиране на стека тип структура на данни.

Изпълнение на опашката

Опашката може да бъде реализирана по два начина:

  1. Статично изпълнение: Ако опашката се реализира с помощта на масиви, точният брой елементи, които искаме да съхраним в опашката, трябва да бъде сигурен преди, защото размерът на масива трябва да бъде деклариран по време на проектиране или преди да започне обработката. В този случай началото на масива ще стане предната част на опашката, а последното местоположение на масива ще действа като задната част на опашката. Следното съотношение дава всички елементи съществуват в опашката, когато се реализират с масиви:
    отпред - отзад + 1
    Ако "отзад <отпред", няма да има елемент от опашката или опашката винаги ще бъде празна.
  2. Динамично изпълнение: Реализиране на опашки с помощта на указатели, основният недостатък е, че възел в свързано представяне консумира повече място в паметта, отколкото съответстващ елемент в представянето на масива. Тъй като във всеки възел има поне две полета, едно за полето за данни, а друго за съхранение на адреса на следващия възел, докато в свързано представяне има само поле за данни. Предимството на използването на свързаното представяне става очевидно, когато е необходимо да се вмъкне или изтрие елемент в средата на група от други елементи.

Операции в стека

Основните операции, които могат да бъдат оперирани върху стека са, както следва:

  1. PUSH: когато нов елемент е добавен в горната част на стека е известен като PUSH операция. Натискането на елемент в стека предизвиква добавяне на елемента, тъй като новият елемент ще бъде вмъкнат в горната част. След всяка операция на натискане горната част се увеличава с една. Ако масивът е пълен и не може да се добави нов елемент, той се нарича STACK-FULL условие или STACK OVERFLOW. PUSH OPERATION - функция в C:
    Като се има предвид стека е деклариран като
    int stack, top = -1;
    невалиден тласък ()
    {
    елемент int;
    ако (отгоре <4)
    {
    f ("Въведете номера");
    сканиране ("% d", & елемент);
    отгоре = отгоре + 1;
    стек = елемент;
    }
    още
    {
    f ("Стека е пълен");
    }
    }
  2. POP: Когато един елемент се изтрие от горната част на стека, той е известен като POP операция. Стекът се намалява с един, след всяка поп операция. Ако в стека не е оставен елемент и се изпълнява поп, тогава това ще доведе до STACK UNDERFLOW условие, което означава, че стекът ви е празен. POP OPERATION - функции в C:
    Като се има предвид стека е деклариран като
    int stack, top = -1;
    нищожен поп ()
    {
    елемент int;
    ако (отгоре> = 4)
    {
    item = стек;
    отгоре = отгоре - 1;
    f ("Изтритият номер е =% d", елемент);
    }
    още
    {
    f ("Стекът е празен");
    }
    }

Операции на опашка

Основните операции, които могат да се извършват на опашка са:

  1. Поставяне в опашката: За да вмъкнете елемент в опашка. Функция за операция в C:
    Опашката е декларирана като
    int опашка, отпред = -1 и отзад = -1;
    невалиден добавяне ()
    {
    елемент int;
    ако (отзад <4)
    {
    f ("Въведете номера");
    сканиране ("% d", & елемент);
    ако (отпред == -1)
    {
    предна = 0;
    отзад = 0;
    }
    още
    {
    отзад = отзад + 1;
    }
    опашка = елемент;
    }
    още
    {
    f ("Опашката е пълна");
    }
    }
  2. Dequeue: За да изтриете елемент от опашката. Функция за операция в C:
    Опашката е декларирана като
    int опашка, отпред = -1 и отзад = -1;
    невалидно изтриване ()
    {
    елемент int;
    ако (отпред! = -1)
    {
    артикул = опашка;
    ако (отпред == отзад)
    {
    предна = -1;
    заден = -1;
    }
    още
    {
    отпред = отпред + 1;
    f ("Изтритият номер е =% d", елемент);
    }
    }
    още
    {
    f ("Опашката е празна");
    }
    }

Приложения на Stack

  • Разбор в компилатор.
  • Java виртуална машина.
  • Отменете в текстов процесор.
  • Бутон за връщане в уеб браузър.
  • PostScript език за ers.
  • Изпълнение на функционални обаждания в компилатор.

Приложения на опашката

  • Буфери на данни
  • Асинхронен трансфер на данни (файл IO, тръби, гнезда).
  • Разпределяне на заявки на споделен ресурс (er, процесор).
  • Анализ на трафика.
  • Определете броя на касите, които да имат в супермаркет.

заключение

Stack и Queue са линейни структури от данни, които се различават по определени начини като работещ механизъм, структура, изпълнение, варианти, но и двете се използват за съхраняване на елементите в списъка и извършване на операции в списъка като добавяне и изтриване на елементите. Въпреки че има някои ограничения на простата опашка, която се възстановява чрез използване на други видове опашка.