Stacks, опашки, декември

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

(Според операция метод за добавяне и изтриване на елементи)

Stack Queue декември

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

Използват и други имена стека - магазин и се обръщат за функционирането printsipuLIFO (Last-In-First-Out - "последен в - първо изключено"). Програмиране система на блока, ориентирани езици (Pascal, C и др.) Използва стека за поместване на локални променливи и процедурите на други софтуерни блокове. Във всяка активация процедура памет на своите локални променливи, разпределени в стека; в края на тази процедура, паметта се освобождава. Както винаги, когато процедурата се спазва стриктно гнездене, в горната част на комина е винаги в паметта, локални променливи, съдържащи активния в момента процедура.

Опашка - това е линейна списък с променлива дължина, където елемент превключвател се извършва само с една ръка списъка (тази посока често се нарича края на опашката или опашката) и изключение - от друга страна (наречен в началото на опашката или главата).

Опашки се наричат ​​още "spiskamitipaFIFO» (първи - В - Първи- Out - «първи дошъл - първи изключени").

Първоначално стрелките за начало и край точка до началото на зоната на паметта на. Равенството на двете стрелки (в някоя от тяхната стойност) е знака на празна опашка.

Декември (от английски DEQ -. Двойна край опашката, т.е. опашка с два края), е структура от данни, в която да добавяте или премахвате елементи и от двете страни.

Задачи, които изискват палубата структури, намиращи се в компютърните науки и програмиране, много по-малко, отколкото на задачите, изпълнявани в структурата на стека или опашката. Като правило, цялата организация на палубата се извършва от програмист без специални средства за системна поддръжка.

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

запис образуват аритметичен израз:

Инфикса - запис, в който се намира знака на аритметична операция между операндите (А + В).

Префикс - нотация, в която предхожда операция знака операнд (+ AB).

Postfix - запис, в който операциите по знаците, разположени зад операнди (AB +).

Забележка. префикс форма не е постфиксната огледален образ. Например:

* -аб + CD - префикс нотация;

AB-CD + * - Postfix нотация.

Една от основните причини, довели до появата на програмиране на високо ниво езици, са задачи, които изискват компютърни големи обеми от рутинни изчисления. Ето защо, езиците за програмиране прави искания максимално приближение изчисление рекордни форми на естествения език на математиката. В тази връзка, една от първите области на програмната система, образувана проучването на начини за изразяване. Има множество получените резултати, но най-широко използваният метод на разпространение чрез RPN (Postfix нотация), което предполага, полски математик J. Loukachevitch.

Преглед на първоначалната поредица от букви, от ляво на дясно, операнди се копират изходния низ и признаци на операция се записват в стека на базата на следните съображения:

Ако следващия знак от низа източник има отворена скоба, тя се вкарва на комина;

затваряща скоба избутва всички операции от стека в изходна линия до най-близкия скоба отваряне, се подпре с изходния низ не е пренаписан и унищожи един от друг;

операция избутва всички операции стека-големи или равни приоритет в низа за извеждане;

ако стека е празен, работата на входния низ се презаписва в стека.

Процесът на получаване RPN изрази (А + В) * (C + D) -E схематично представена в таблица