Практикада маалымат структуралары: стектер, кезектер жана Big-O интуициясы
Тапшырмага туура контейнер тандасаңыз - код тез жана түшүнүктүү болот. Туура эмесин тандасаңыз - маалымат көбөйгөн сайын API жайлап калат.
Map жана Set) - бир нерсени ачкыч боюнча заматта табуу керек болгондо. Ар бир операциянын баасын - анын Big-O - түшүнүү коддун 10 элементте жана 10 миллиондо кандай иштээрин алдын ала айтууга мүмкүндүк берет.
- стекти (LIFO) ишке ашырып, аны артка кайтаруу тарыхы үчүн колдоно аласыз;
- кезекти (FIFO) ишке ашырып, аны тапшырма кезеги үчүн колдонуп,
shift()тузагынан качасыз; Set/Mapзаматта издөө, кайталанмаларды жоюу жана санаа үчүн колдоносуз;- Big-O белгилөөсүн окуп, интуиция боюнча
O(1),O(n)жанаO(n^2)айырмалайсыз; - кокустан пайда болгон
O(n^2)циклин хеш-таблица аркылууO(n)өтмөгү менен алмаштырасыз.
1. Стек - акыркы киргени биринчи чыгат
Стек - бул үймөк. Сиз push менен үстүнө кошуп, pop менен үстүнөн аласыз. Эң акыркы койгон нерсеңиз - биринчи аласыз: LIFO (Last In, First Out).
Салыштыруу. Табактардын үймөгүн элестетиңиз. Таза табакты үстүнө коёсуз; кийинки аласыз турган табак - дал ошол жаңы койгонуңуз. Ортосунан табак сууруп албайсыз.
Турмуштагы колдонуу: артка кайтаруу тарыхы. Ар бир текст редактору артка кайтаруу стегин сактайт. Ар бир түзөтүү үстүнө коюлат. Ctrl+Z баскандагыда редактор эң акыркы түзөтүүнү алып (pop) аны артка кайтарат. Эң жаңы өзгөртүү дайыма үстүндө болгондуктан, артка кайтаруу - бир арзан pop операциясы.
JavaScript-те кадимки массив мурдатан эле стек болуп саналат: arr.push(x) аягына кошот, arr.pop() аягынан алат, экөө тең O(1) - массивдин өлчөмүнө карабай туруктуу убакыт. Кичине класска ороо операцияларга түшүнүктүү аттарды берет:
class Stack {
constructor() { this.items = []; }
push(x) { this.items.push(x); }
pop() { return this.items.pop(); } // үстүнкүсүн алып + кайтаруу
peek() { return this.items[this.items.length - 1]; } // карап коюу, албай
get size() { return this.items.length; }
}Негизги тартип: стек сизге бир гана үстүн кармоого уруксат берет. Бул чектөө - артыкчылык: ал структураны тез, ниетиңизди айкын кармайт.