Kadalasan, ang prinsipyo ng pagpapatakbo ng stack ay inihambing sa isang stack ng mga plato: upang kunin ang pangalawa mula sa itaas, kailangan mong alisin ang tuktok.
Sa ilang mga wika (halimbawa, Lisp, Python), anumang listahan ay maaaring tawaging stack, dahil ang mga pop at push operation ay magagamit para sa kanila. Sa C++, ang karaniwang aklatan ay may klase na may ipinatupad na istraktura at pamamaraan. atbp.
Encyclopedic YouTube
1 / 3
Informatics. Mga istruktura ng data: Stack. Foxford Online Learning Center
#9. Stack / 1. Assembler at mga pamamaraan / Programming mula sa simula
Mga pangunahing kaalaman sa mga network ng data. modelo ng OSI at salansan Mga protocol ng TCP IP. Mga Pangunahing Kaalaman sa Ethernet.
Mga subtitle
Stack ng software
Organisasyon sa memorya
Kadalasan, ang isang stack ay ipinapatupad bilang isang one-way na listahan (bawat elemento sa listahan ay naglalaman, bilang karagdagan sa impormasyong nakaimbak sa stack, isang pointer sa susunod na elemento ng stack).
Ngunit ang stack ay madalas ding matatagpuan sa isang one-dimensional na array na may mga order na address. Ang samahan ng stack na ito ay maginhawa kung ang isang elemento ng impormasyon ay sumasakop sa memorya nakapirming dami mga salita, halimbawa, 1 salita. Tinatanggal nito ang pangangailangang mag-imbak ng isang tahasang pointer sa susunod na elemento ng stack sa isang elemento ng stack, na nakakatipid ng memorya. Sa kasong ito, ang stack pointer ( Stack Pointer, - SP) ay karaniwang isang rehistro ng processor at tumuturo sa address ng head ng stack.
Halimbawa, ipagpalagay na ang ulo ng stack ay matatagpuan sa isang mas mababang address, ang mga sumusunod na elemento ay matatagpuan sa pagtaas ng mga address. Sa bawat oras na ang isang salita ay itinulak sa stack, ang SP ay unang binabawasan ng 1 at pagkatapos ay ang address mula sa SP ay isinusulat sa memorya. Sa bawat oras na may lumabas na salita mula sa stack, babasahin muna nito ang kasalukuyang address mula sa SP at pagkatapos ay dinadagdagan ng 1 ang mga nilalaman ng SP.
Kapag nag-aayos ng isang stack bilang isang unidirectional na listahan, ang halaga ng variable ng stack ay isang pointer sa tuktok nito - ang address ng tuktok. Kung ang stack ay walang laman, ang pointer value ay NULL.
Isang halimbawa ng pagpapatupad ng stack sa C:
struct stack (char * data; struct stack * next; );
Stack Operations
Mayroong tatlong posibleng operasyon sa stack: pagdaragdag ng elemento (aka pushing), pag-alis ng elemento (pop) at pagbabasa ng head element (peek).
Kapag tinutulak (push) ang isang bagong elemento ay idinagdag, na tumuturo sa elemento na dating ulo. Bagong elemento ngayon ay nagiging ulo.
Kapag nagtanggal ng isang elemento (pop), ang una ay aalisin, at ang isa kung saan ang bagay na ito ay may pointer (ang susunod na elemento) ay nagiging ulo. Sa kasong ito, ibinabalik ang halaga ng inalis na elemento.
void push (STACK * ps, int x) // Pagdaragdag ng bagong elemento sa stack( kung ( ps -> laki == STACKSIZE ) // Umaapaw ba ang stack?( fputs ( "Error: stack overflow \n " , stderr ); abort (); ) else ( ps -> items [ ps -> size ++ ] = x ; ) ) int pop ( STACK * ps ) // Alisin mula sa stack( kung ( ps -> laki == 0 ) // Walang laman ba ang stack?( fputs ( "Error: stack underflow \n " , stderr ); abort (); ) else ( return ps -> items [ -- ps -> size ]; ) )
Saklaw ng aplikasyon
Ang programming view ng isang stack ay ginagamit upang tumawid sa mga istruktura ng data, tulad ng isang puno o graph. Kapag gumagamit recursive function Gagamitin din ang stack, ngunit ang uri ng hardware nito. Bilang karagdagan sa mga layuning ito, ang stack ay ginagamit upang ayusin
Nagaganap ang mga katulad na proseso sa panahon ng pagkagambala ng hardware (X86 processor na may pagkagambala ng hardware awtomatikong sine-save ang rehistro ng bandila sa stack). Bilang karagdagan, ang mga compiler ay naglalagay ng mga lokal na variable ng procedure sa stack (kung ang processor ay may access sa isang random na lokasyon ng stack).
Bago magamit ang stack, dapat itong masimulan upang ang mga rehistro ng SS:ESP ay tumuturo sa address ng stack head sa pisikal na lugar. RAM, at para sa pag-iimbak ng data sa stack kinakailangan na magreserba ng kinakailangang bilang ng mga cell ng memorya (malinaw naman, ang stack sa ROM, natural, ay hindi maaaring ayusin). Mga programa sa aplikasyon, bilang panuntunan, mula sa operating system makatanggap ng handa-kainin na stack. Sa protektadong processor mode, ang task state segment ay naglalaman ng apat na stack segment selector (para sa iba't ibang antas mga pribilehiyo), ngunit isang stack lang ang ginagamit sa isang pagkakataon.
Ang stack ay isang programming phenomenon at isang natural na solusyon. Ang Stack ay agad na pumasok sa negosyo ng computer at naging "katutubong", na parang dito nagsimula ang lahat.
Kung walang stack, hindi gumagana ang processor, walang recursion, at imposibleng ayusin ang mahusay na mga tawag sa pag-andar. Ang anumang algorithm ay maaaring gawin nang walang pila, listahan, koleksyon, array, o sistema ng mga organisadong bagay, ngunit walang gumagana nang walang memorya at isang stack, kasama ang lahat ng nasa itaas.
Sa madaling araw ng simula: processor, memory at stack
Ang ideal na memorya ay nagbibigay ng direktang pagtugon sa halaga - ito ang mga antas ng makina at wika mataas na antas. Sa unang kaso, sunud-sunod na umuulit ang processor sa pamamagitan ng mga address ng memorya at nagsasagawa ng mga tagubilin. Sa pangalawang kaso, ang programmer ay nagmamanipula ng mga array. Ang parehong mga episode ay naglalaman ng:
- address = halaga;
- index = halaga.
Ang address ay maaaring ganap at kamag-anak, ang index ay maaaring digital at nauugnay. Ang address at index ay maaaring maglaman ng isa pang address kaysa sa isang halaga, ngunit ito ang mga detalye ng hindi direktang pagtugon. Kung walang memorya, hindi gagana ang isang processor, at kung walang isang stack ng mga command at data, ito ay tulad ng isang bangka na walang mga sagwan.
Ang isang salansan ng mga plato ay isang tradisyonal na kuwento tungkol sa kakanyahan ng isang salansan: ang konsepto ng salansan at pagsasalin sa karaniwang kamalayan. Hindi ka maaaring kumuha ng isang plato mula sa ibaba, maaari mo lamang itong kunin mula sa itaas, at pagkatapos ay ang lahat ng mga plato ay magiging buo.
Anuman ang huli sa stack ay mauuna. Ang perpektong solusyon. Sa esensya, ang stack, bilang isang pagsasalin ng isang aksyon patungo sa isa pa, ay binabago ang ideya ng isang algorithm bilang isang pagkakasunud-sunod ng mga operasyon.
Ang kakanyahan at konsepto ng isang stack
Ang processor at memorya ay ang pangunahing mga bloke ng gusali ng isang computer. Ang processor ay nagsasagawa ng mga tagubilin, nagmamanipula ng mga address ng memorya, at kinukuha at binabago ang mga halaga sa mga address na ito. Sa isang programming language, ang lahat ng ito ay binago sa mga variable at ang kanilang mga halaga. Ang esensya ng stack at ang konsepto ng last in first out (LIFO) ay nananatiling hindi nagbabago.
Ang acronym na LIFO ay hindi na ginagamit nang madalas gaya ng dati. Marahil dahil ang mga listahan ay na-transform sa mga bagay, at ang mga queu na first in first out (FIFO) ay ginagamit kung kinakailangan. Ang dynamics ng mga uri ng data ay nawala ang kaugnayan nito sa konteksto ng paglalarawan ng mga variable, ngunit nakuha ang kahalagahan nito sa oras ng pagpapatupad ng mga expression: ang uri ng isang data ay tinutukoy sa sandali ng paggamit nito, at hanggang sa sandaling iyon maaari mong ilarawan kahit ano at anumang paraan na gusto mo.
Kaya, stack - ano ito? Ngayon alam mo na na ito ay isang hindi naaangkop na tanong. Pagkatapos ng lahat, walang stack walang modernong programming. Anumang function na tawag ay nangangahulugan ng pagpasa ng mga parameter at isang return address. Ang isang function ay maaaring tumawag sa isa pang function - ito ay muling pagpasa ng mga parameter at isang return address. Ang pag-set up ng isang mekanismo para sa pagtawag ng mga halaga nang walang stack ay dagdag na trabaho, kahit na ang isang makakamit na solusyon ay tiyak na posible.
Maraming tao ang nagtatanong: "Stack - ano ito?" Sa konteksto ng isang function na tawag, binubuo ito ng tatlong aksyon:
- pag-save ng return address;
- pag-save ng lahat ng inilipat na variable o address sa kanila;
- function na tawag.
Kapag nakumpleto na ng tinatawag na function ang misyon nito, ibabalik lang nito ang kontrol sa return address. Ang isang function ay maaaring tumawag sa anumang bilang ng iba pang mga function, dahil ang limitasyon ay ang laki lamang ng stack.
Mga katangian ng stack
Ang isang stack ay hindi isang abstract na uri ng data, ngunit isang tunay na mekanismo. Sa antas ng processor, ito ay isang "engine" na pinipino at pinupunan ang gawain ng pangunahing ikot ng processor. Tulad ng bit arithmetic, ang stack ay kumukuha ng simple at halatang mga panuntunan ng operasyon. Ito ay maaasahan at ligtas.
Ang mga katangian ng isang stack ay ang laki nito at ang haba ng mga elemento nito. Sa antas ng processor, ang lahat ay tinutukoy ng bit capacity, memory addressing at ang physics ng pag-access dito. Kawili-wiling tampok at tradisyon: lumalaki ang stack pababa, iyon ay, patungo sa pagpapababa ng mga address ng memorya, at memorya ng programa at data - pataas. Ito ay karaniwan, ngunit hindi kinakailangan. Ang ibig sabihin dito ay mahalaga - siya ang huling dumating at naunang umalis. Ang nakakagulat na simpleng panuntunang ito ay nagbibigay-daan sa iyo na bumuo ng mga kawili-wiling algorithm na pangunahing gumagana sa mga wika mataas na antas. Ngayon hindi mo na itatanong, ano ang stack?
Walang kapintasang gawain hardware ay naging pamantayan sa napakatagal na panahon, ngunit nasa unahan teknolohiya ng impormasyon Ang ideya ng isang stack ay nakakakuha ng mga bago at promising application.
Mahalaga, hindi mahalaga kung ano ang stack sa antas ng processor. Ito ay isang likas na bahagi ng arkitektura ng computer. Ngunit sa programming, ang stack ay nakasalalay sa partikular na aplikasyon at kakayahan ng programmer.
Mga array, koleksyon, listahan, pila... Stack!
Madalas itanong ng mga tao ang tanong: "Stack - ano ito?" Ang "Programming" at "systematization" ay mga kawili-wiling konsepto: hindi sila magkasingkahulugan, ngunit napakalapit ng mga ito. Napakabilis ng narating ng programming na tila perpekto ang mga naabot. Malamang na hindi ito ang kaso. Pero halatang iba.
Ang ideya ng isang stack ay naging pamilyar hindi lamang sa antas ng iba't ibang mga programming language, kundi pati na rin sa antas ng kanilang mga disenyo at kakayahan para sa paglikha ng mga uri ng data. Ang anumang array ay may push at pop, at ang mga konsepto ng "ang una at huling elemento ng array" ay naging tradisyonal. Dati mayroon lamang mga elemento ng array, ngunit ngayon ay mayroong:
- mga elemento ng array;
- unang elemento ng array;
- ang huling elemento ng array.
Ang operasyon ng paglalagay ng isang elemento sa isang array ay gumagalaw sa pointer, at ang pagkuha ng isang elemento mula sa simula ng array o mula sa dulo nito ay gumagawa ng isang pagkakaiba. Sa pangkalahatan, ito ay ang parehong stack, ngunit inilapat sa iba pang mga uri ng data.
Ito ay lalo na kapansin-pansin na mga tanyag na wika ang programming ay walang stack construct. Ngunit ibinibigay nila ang kanyang ideya sa developer nang buo.
Ang stack ay isang koleksyon na ang mga elemento ay nakuha sa isang last-in, first-out na batayan. (Last-In-First-Out o LIFO). Nangangahulugan ito na magkakaroon lamang kami ng access sa huling idinagdag na elemento.
Hindi tulad ng mga listahan, hindi namin ma-access ang isang arbitrary na elemento ng stack. Maaari lamang kaming magdagdag o mag-alis ng mga elemento gamit ang mga espesyal na pamamaraan. Ang mga stack ay wala ring paraan na Naglalaman tulad ng mga listahan. Bilang karagdagan, ang stack ay walang iterator. Upang maunawaan kung bakit inilalagay ang gayong mga paghihigpit sa stack, tingnan natin kung paano ito gumagana at kung paano ito ginagamit.
Ang pinakakaraniwang pagkakatulad upang ipaliwanag ang isang stack ay isang stack ng mga plato. Hindi alintana kung gaano karaming mga plato ang nasa stack, maaari naming palaging alisin ang tuktok. Ang mga malinis na plato ay inilalagay sa ibabaw ng salansan sa parehong paraan, at palagi naming kukunin ang plato na huling inilagay muna.
Kung maglalagay tayo, halimbawa, isang pulang plato, pagkatapos ay isang asul, at pagkatapos ay isang berde, pagkatapos ay kailangan muna nating alisin ang berde, pagkatapos ay ang asul, at sa wakas ang pula. Ang pangunahing bagay na dapat tandaan ay ang mga plato ay palaging inilalagay sa ibabaw ng stack. Kapag may kumuha ng plato, inaalis din nila ito sa itaas. Lumalabas na ang mga plato ay na-disassemble sa kabaligtaran ng pagkakasunud-sunod kung saan sila inilagay.
Ngayong naiintindihan na natin kung paano gumagana ang isang stack, magpakilala tayo ng ilang termino. Ang operasyon ng pagdaragdag ng isang elemento sa stack ay tinatawag na "push", at ang pag-alis nito ay tinatawag na "pop". Ang huling elementong idinagdag ay tinatawag na tuktok ng stack, o "itaas", at maaaring matingnan gamit ang "peek" na operasyon. Tingnan natin ngayon ang template ng isang klase na nagpapatupad ng stack.
Salansan ang klase
Tinutukoy ng klase ng Stack ang mga paraan ng Push, Pop, Peek para sa pag-access ng mga elemento, at isang Count field. Sa pagpapatupad gagamitin namin ang LinkList
Pampublikong klase Stack ( LinkedList _items = bagong LinkedList(); public void Push(T value) ( Throw new NotImplementedException(); ) public T Pop() ( throw new NotImplementedException(); ) public T Peek() ( throw new NotImplementedException( ); public int Count ( get ; ) )
Paraan ng pagtulak
- Pag-uugali: Nagdaragdag ng elemento sa tuktok ng stack.
- Pagiging kumplikado: O(1).
Dahil gumagamit kami ng naka-link na listahan upang mag-imbak ng mga elemento, maaari lang kaming magdagdag ng bago sa dulo ng listahan.
Pampublikong void Push(T value) ( _items.AddLast(value); )
Paraan ng pop
- Pag-uugali: Tinatanggal ang isang elemento mula sa tuktok ng stack at ibinabalik ito. Kung walang laman ang stack, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
Ang push ay nagdaragdag ng mga elemento sa dulo ng listahan, kaya dadalhin din ang mga ito mula sa dulo. Kung ang listahan ay walang laman, ang isang pagbubukod ay itatapon.
Public T Pop() ( kung (_items.Count == 0) ( throw new InvalidOperationException("The stack is empty"); ) T resulta = _items.Tail.Value; _items.RemoveLast(); return result; )
Pamamaraan ng pagsilip
- Pag-uugali: Nagbabalik nangungunang elemento stack, ngunit hindi ito tinatanggal. Kung walang laman ang stack, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
Paraan ng pagbilang
- Pag-uugali: Ibinabalik ang bilang ng mga elemento sa stack.
- Pagiging kumplikado: O(1).
Bakit kailangan nating malaman kung gaano karaming mga elemento ang nasa stack kung wala pa rin tayong access sa mga ito? Sa field na ito maaari nating suriin kung mayroong mga elemento sa stack o kung ito ay walang laman. Ito ay lubhang kapaki-pakinabang kung isasaalang-alang iyon Paraan ng pop nagtatapon ng exception.
Halimbawa: calculator sa reverse Polish notation.
Ang isang klasikong halimbawa ng paggamit ng stack ay isang calculator sa reverse Polish, o postfix, notation. Dito nakasulat ang operator pagkatapos kanilang mga operand. Iyon ay, isinusulat namin:
<операнд> <операнд> <оператор>
sa halip na tradisyonal:
<операнд> <оператор> <операнд>
Sa madaling salita, sa halip na "4 + 2" ay isusulat namin ang "4 2 +". Kung interesado ka sa pinagmulan ng reverse Polish notation at ang pangalan nito, maaari mong malaman ang tungkol dito sa Wikipedia o sa isang search engine.
Paano kinakalkula ang reverse Polish notation at kung bakit ang stack ay lubhang kapaki-pakinabang kapag ginagamit ito ay malinaw na makikita mula sa sumusunod na algorithm:
Para sa bawat halaga ng pag-input kung ang halaga ay isang integer, itulak ang halaga sa operand stack kung hindi man kung ang halaga ay isang operator, i-pop ang kaliwa at kanang mga halaga mula sa stack suriin ang operator na itulak ang resulta sa stack pop na sagot mula sa stack .
Iyon ay, para sa expression na "4 2 +" ang mga aksyon ay magiging tulad ng sumusunod:
Push(4) push(2) push(pop() + pop())
Sa dulo magkakaroon ng isang halaga sa stack - 6.
Ang sumusunod ay buong code simpleng calculator, na nagbabasa ng expression (halimbawa, 4 2 +) mula sa console, hinahati ang input sa pamamagitan ng mga puwang (["4", "2", "+"]) at isinasagawa ang algorithm ng pagkalkula. Nagpapatuloy ang pagsusuri hanggang sa makatagpo ang salitang quit.
Void RpnLoop() ( while (true) ( Console.Write("> "); string input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") ( break; ) // Salansan ng mga halaga ay hindi pa naproseso Mga halaga ng stack = bagong Stack(); int value; if (int. TryParse(token, out value)) ( // ... ilagay ito sa stack. values.Push(value); ) else ( // kung hindi ay gawin ang operasyon... int rhs = values .Pop(); int lhs = values.Pop(); // ... at ibalik ang resulta (token) ( case "+": values.Push(lhs + rhs); break; case "-" : values.Push(lhs - rhs ); Kung ang operasyon ay hindi +, -, * o / throw new ArgumentException(string.Format("Unrecognized token: (0)", token) ) ) // Ang huling elemento sa stack ay ang resulta .Pop());
) )
Nakapila Ang mga pila ay halos kapareho ng mga stack. Hindi rin sila nagbibigay ng access sa isang arbitrary na elemento, ngunit, hindi tulad ng isang stack, ang mga elemento ay nakasalansan(enqueue) at umakyat(dequeue) mula sa iba't ibang dulo. Ang pamamaraang ito ay tinatawag na "first in, first out"(First-In-First-Out o FIFO)
. Iyon ay, kukunin namin ang mga elemento mula sa pila sa parehong pagkakasunud-sunod ng paglalagay namin sa kanila. Parang totoong pila o conveyor.
Ang mga pila ay kadalasang ginagamit sa mga programa upang magbigay ng buffer kung saan maaaring ilagay ang mga item para sa pagpoproseso sa ibang pagkakataon habang pinapanatili ang pagkakasunud-sunod ng pagdating ng mga ito. Halimbawa, kung ang database ay sumusuporta lamang sa isang koneksyon, maaari kang gumamit ng isang pila ng mga thread na, kakaiba, ay maghihintay ng kanilang pagkakataon upang ma-access ang database.
Klase sa pila
, dahil ito ay mga espesyal na layunin na koleksyon.
Public class Queue ( LinkedList _items = new LinkedList(); public void Enqueue(T value) ( throw new NotImplementedException(); ) public T Dequeue() ( throw new NotImplementedException(); ) public T Peek() ( throw new NotImplementedException( ); public int Count ( get ; ) )
- Pag-uugali: Paraan ng Enqueue
- Pagiging kumplikado: O(1).
Maaaring magdagdag ng mga bagong elemento ng pila sa simula ng listahan o sa dulo. Mahalaga lamang na ang mga elemento ay naabot mula sa kabaligtaran na gilid. Sa pagpapatupad na ito, magdaragdag kami ng mga bagong elemento sa simula ng panloob na listahan.
Pampublikong void Enqueue(T value) ( _items.AddFirst(value); )
Paraan ng dequeue
- Pag-uugali: Tinatanggal ang unang inilagay na elemento mula sa pila at ibinabalik ito. Kung ang pila ay walang laman, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
Dahil naglalagay kami ng mga elemento sa simula ng listahan, aalisin namin ang mga ito sa dulo. Kung ang listahan ay walang laman, ang isang pagbubukod ay itinapon.
Public T Dequeue() ( if (_items.Count == 0) ( throw new InvalidOperationException("The queue is empty"); ) T last = _items.Tail.Value; _items.RemoveLast(); return last; )
Pamamaraan ng pagsilip
- Pag-uugali: Ibinabalik ang elemento na ibabalik sa susunod na tawag sa paraan ng Dequeue. Ang pila ay nananatiling hindi nagbabago. Kung ang pila ay walang laman, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
Paraan ng pagbilang
- Pag-uugali:
- Pagiging kumplikado: O(1).
Two-way na pila
Two-way na pila (Double-ended na pila), o Dis (Deque), nagpapalawak sa gawi ng pila. Sa isang deque, maaari kang magdagdag o mag-alis ng mga elemento mula sa simula at dulo ng pila. Ang gawi na ito ay kapaki-pakinabang sa maraming gawain, gaya ng pag-iskedyul ng mga thread o pagpapatupad ng iba pang istruktura ng data. Sa ibang pagkakataon, titingnan natin ang pagpapatupad ng isang stack gamit ang isang deque.
Deque class
Ang klase ng Deque ay pinakamadaling ipatupad gamit ang isang dobleng naka-link na listahan. Pinapayagan ka nitong tingnan, tanggalin at magdagdag ng mga elemento sa simula at dulo ng listahan. Ang pangunahing pagkakaiba sa pagitan ng two-way queue at regular na queue ay ang Enqueue , Dequeue , at Peek na pamamaraan ay nahahati sa mga pares upang gumana sa magkabilang dulo ng listahan.
Pampublikong klase Deque ( LinkedList _items = bagong LinkedList(); public void EnqueueFirst(T value) ( Throw new NotImplementedException(); ) public void EnqueueLast(T value) ( Throw new NotImplementedException(); ) public T DequeueFirst( ) ( throw new NotImplementedException(); ) public T DequeueLast() ( throw new NotImplementedException(); ) public T PeekFirst() ( throw new NotImplementedException(); ) public T PeekLast() ( throw new NotImplementedException(); ) public int Bilangin (kunin; ) )
EnqueueFirst na pamamaraan
- Pag-uugali:
- Pagiging kumplikado: O(1).
EnqueueHuling paraan
- Pag-uugali:
- Pagiging kumplikado: O(1).
DequeueFirst paraan
- Pag-uugali: Nag-aalis ng elemento sa harap ng pila at ibinabalik ito. Kung ang pila ay walang laman, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
DequeueHuling paraan
- Pag-uugali:
- Pagiging kumplikado: O(1).
Pamamaraan ng PeekFirst
- Pag-uugali: Ibinabalik ang isang elemento mula sa simula ng queue nang hindi ito binabago. Kung ang pila ay walang laman, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
PeekLast na pamamaraan
- Pag-uugali:
- Pagiging kumplikado: O(1).
Paraan ng pagbilang
- Pag-uugali: Ibinabalik ang bilang ng mga elemento sa queue, o 0 kung walang laman ang queue.
- Pagiging kumplikado: O(1).
Halimbawa: Pagpapatupad ng Stack
Ang isang deque ay kadalasang ginagamit upang ipatupad ang iba pang mga istruktura ng data. Tingnan natin ang isang halimbawa ng pagpapatupad ng stack gamit ito.
Maaaring nagtataka ka kung bakit nagpapatupad ng stack batay sa isang queue sa halip na isang naka-link na listahan. Mayroong dalawang dahilan: pagganap at muling gamitin code. Ang isang naka-link na listahan ay may overhead ng paglikha ng mga node at walang garantiya ng lokalidad ng data: ang mga elemento ay maaaring matatagpuan kahit saan sa memorya, na nagiging sanhi ng malaking bilang mga miss at pagkasira ng performance sa antas ng processor. Ang isang mas mahusay na pagpapatupad ng isang deque ay nangangailangan ng isang array upang mag-imbak ng mga elemento.
Gayunpaman, ang pagpapatupad ng isang stack o queue gamit ang isang array ay hindi isang madaling gawain, ngunit ang pagpapatupad ng isang deque sa ganitong paraan at paggamit nito bilang batayan para sa iba pang mga istruktura ng data ay magbibigay sa amin ng mga seryosong benepisyo sa pagganap at magbibigay-daan sa aming muling gamitin ang code. Binabawasan nito ang mga gastos sa suporta.
Titingnan natin ang isang variant ng isang queue gamit ang isang array sa ibang pagkakataon, ngunit tingnan muna natin ang stack class gamit ang isang dequeue:
Pampublikong klase Stack ( Deque _items = new Deque(); public void Push(T value) ( _items.EnqueueFirst(value); ) public T Pop() ( return _items.DequeueFirst(); ) public T Peek() ( return _items .PeekFirst(); public int Count ( get ( return _items.Count; ) ) )
Tandaan na ang lahat ng paghawak ng error ay pinangangasiwaan na ngayon ng klase ng Deque, at bilang karagdagan, ang anumang pag-optimize ng queue ay makikita rin sa stack. Ang pagpapatupad ng regular na round-trip na pila ay napakasimple kaya iiwan namin ito bilang isang ehersisyo para sa mambabasa.
Pag-iimbak ng mga elemento sa isang array
Tulad ng nabanggit na, ang pagpapatupad ng isang queue gamit ang isang array ay may mga pakinabang nito. Mukhang simple, ngunit sa katunayan mayroong isang bilang ng mga nuances na kailangang isaalang-alang.
Tingnan natin ang mga problemang maaaring lumitaw at kung paano ito malulutas. Bilang karagdagan, kakailanganin namin ng impormasyon tungkol sa pagtaas ng panloob na array mula sa nakaraang artikulo sa mga dynamic na array.
Kapag ang isang queue ay ginawa, ang isang zero-length array ay nilikha sa loob nito. Ang mga pulang letrang "h" at "t" ay kumakatawan sa _head at _tail pointer, ayon sa pagkakabanggit.
Deque deq = bagong Deque(); deq.EnqueueFirst(1);
Deq.EnqueueLast(2);
Deq.EnqueueFirst(0);
Pakitandaan: ang index ng "ulo" ng pila ay tumalon sa simula ng listahan. Ngayon ang unang elemento na ibabalik kapag tinawag ang DequeueFirst na paraan ay 0 (index 3).
Deq.EnqueueLast(3);
Puno na ang array, kaya kapag nagdadagdag ng elemento ang mga sumusunod ay mangyayari:
- Tutukuyin ng algorithm ng paglago ang laki ng bagong array.
- Kokopyahin ang mga elemento sa bagong hanay mula ulo hanggang buntot.
- Isang bagong elemento ang idadagdag.
Ngayon tingnan natin kung ano ang mangyayari kapag inalis ang isang elemento:
Deq.DequeueFirst();
Deq.DequeueLast();
Pangunahing Punto: anuman ang kapasidad o kapunuan ng panloob na hanay, lohikal, ang mga nilalaman ng pila ay mga elemento mula sa "ulo" hanggang sa "buntot", na isinasaalang-alang ang "circularity". Ang pag-uugali na ito ay tinatawag ding "ring buffer".
Ngayon tingnan natin ang pagpapatupad.
Deque class (gamit ang array)
Ang interface ng isang array-based na pila ay kapareho ng sa kaso ng pagpapatupad ng naka-link na listahan. Hindi na namin uulitin. Gayunpaman, dahil ang listahan ay pinalitan ng isang array, nagdagdag kami ng mga bagong field - ang array mismo, ang laki nito at mga pointer sa "buntot" at "ulo" ng pila.
Pampublikong klase Deque ( T _items = bagong T; // Bilang ng mga elemento sa pila. int _size = 0; // Index ng unang (pinakamatandang) elemento. int _head = 0; // Index ng huling (pinakabago) na elemento . int _tail = -1;
Algoritmo ng paglago
kailan libreng espasyo sa panloob na array ay nagtatapos, kailangan itong dagdagan, ang mga elemento ay kinopya at ang mga pointer sa "buntot" at "ulo" ay na-update. Ginagawa ang operasyong ito kung kinakailangan habang nagdaragdag ng elemento. Ang startingIndex na parameter ay ginagamit upang ipahiwatig kung gaano karaming mga patlang ang dapat iwanang blangko sa simula (sa kaso ng pagdaragdag sa simula).
Pansinin kung paano kinukuha ang data kapag kailangan mong tumalon sa simula ng array kapag mula ulo hanggang buntot.
Private void allocateNewArray(int startingIndex) ( int newLength = (_size == 0) ? 4: _size * 2; T newArray = new T; kung (_size > 0) ( int targetIndex = startingIndex; // Kopyahin ang mga nilalaman... / / Kung ang array ay hindi naka-loop, kopyahin lamang ang mga elemento // Kung hindi, kopyahin mula sa ulo hanggang sa dulo, at pagkatapos ay mula sa simula ng array hanggang sa buntot (_buntot.< _head) { // Копируем _items.._items в newArray..newArray[N]. for (int index = _head; index < _items.Length; index++) { newArray = _items; targetIndex++; } // Копируем _items.._items в newArray.. for (int index = 0; index <= _tail; index++) { newArray = _items; targetIndex++; } } else { // Копируем _items.._items в newArray..newArray[N] for (int index = _head; index <= _tail; index++) { newArray = _items; targetIndex++; } } _head = startingIndex; _tail = targetIndex - 1; } else { // Массив пуст. _head = 0; _tail = -1; } _items = newArray; }
EnqueueFirst na pamamaraan
- Pag-uugali: Nagdaragdag ng elemento sa simula ng pila. Ang elementong ito ay kukunin mula sa susunod na pila kapag ang DequeueFirst na pamamaraan ay tinawag.
- Pagiging kumplikado:
EnqueueHuling paraan
- Pag-uugali: Nagdaragdag ng elemento sa dulo ng pila. Ang elementong ito ay kukunin mula sa susunod na pila kapag ang DequeueLast na pamamaraan ay tinawag.
- Pagiging kumplikado: O(1) sa karamihan ng mga kaso; O(n) kapag kailangan ang pagpapalawak ng array.
DequeueFirst paraan
- Pag-uugali: Tinatanggal ang isang elemento mula sa simula ng pila at ibinabalik ito. Kung ang pila ay walang laman, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
DequeueHuling paraan
- Pag-uugali: Tinatanggal ang isang elemento mula sa dulo ng pila at ibinabalik ito. Kung ang pila ay walang laman, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
Pamamaraan ng PeekFirst
- Pag-uugali: Ibinabalik ang elemento mula sa simula ng queue nang hindi ito binabago. Kung ang pila ay walang laman, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
PeekLast na pamamaraan
- Pag-uugali: Ibinabalik ang isang elemento mula sa dulo ng queue nang hindi ito binabago. Kung ang pila ay walang laman, inihagis ang InvalidOperationException.
- Pagiging kumplikado: O(1).
Paraan ng pagbilang
- Pag-uugali: Ibinabalik ang bilang ng mga elemento sa queue, o 0 kung walang laman ang queue.
- Pagiging kumplikado: O(1).
Itutuloy
Nakumpleto na namin ngayon ang ikaapat na bahagi ng aming serye ng mga artikulo. Sa loob nito ay tumingin kami sa mga stack at pila. Sa susunod ay magpapatuloy tayo sa binary search tree.
Gumagamit kami ng mga advanced na programming language na nagbibigay-daan sa amin na magsulat ng mas kaunting code at makakuha ng magagandang resulta. Kailangan mong magbayad para dito. Habang paunti-unti ang pakikitungo natin sa mga bagay na mababa ang antas, normal na marami sa atin ang hindi lubos na nauunawaan kung ano ang stack at heap, kung paano aktwal na gumagana ang compilation, kung ano ang pagkakaiba sa pagitan ng static at dynamic na pag-type, atbp. Hindi ko sinasabi na hindi alam ng lahat ng programmer ang tungkol sa mga konseptong ito - iniisip ko lang na minsan ay sulit na bumalik sa mga lumang bagay.
Ngayon ay pag-uusapan natin ang tungkol sa isang paksa lamang: stack at heap. Parehong ang stack at heap ay tumutukoy sa iba't ibang mga lokasyon kung saan nangyayari ang pamamahala ng memorya, ngunit ang diskarte para sa pamamahala na ito ay lubhang naiiba.
salansan
Ang stack ay isang lugar ng RAM na nilikha para sa bawat thread. Gumagana ito sa pagkakasunud-sunod ng LIFO (Last In, First Out), ibig sabihin, ang huling piraso ng memorya na itinulak sa stack ay ang unang nasa linya na lalabas sa stack. Sa tuwing magdedeklara ang isang function ng bagong variable, idinaragdag ito sa stack, at kapag wala sa saklaw ang variable na iyon (halimbawa, kapag natapos na ang function), awtomatiko itong aalisin sa stack. Kapag ang isang stack variable ay napalaya, ang memory area na iyon ay magiging available para sa iba pang stack variable.
Dahil sa ganitong uri ng stack, ang pamamahala ng memorya ay napaka-lohikal at madaling gawin sa CPU; nagreresulta ito sa mataas na bilis, lalo na dahil ang cycle ng oras ng pag-update ng stack byte ay napakaikli, ibig sabihin. ang byte na ito ay malamang na nakatali sa cache ng processor. Gayunpaman, mayroon ding mga disadvantages sa mahigpit na paraan ng pamamahala. Ang laki ng stack ay isang nakapirming halaga, at ang paglampas sa inilalaang limitasyon ng memorya sa stack ay magreresulta sa isang stack overflow. Nakatakda ang laki kapag ginawa ang stream, at ang bawat variable ay may maximum na laki depende sa uri ng data. Nagbibigay-daan ito sa iyong limitahan ang laki ng ilang variable (gaya ng mga integer), at pinipilit kang ideklara ang laki ng mas kumplikadong mga uri ng data (gaya ng mga array) nang maaga, dahil hindi papayagan ng stack na baguhin ito. Bilang karagdagan, ang mga variable na matatagpuan sa stack ay palaging lokal.
Sa huli, pinapayagan ka ng stack na pamahalaan ang memorya sa pinakamabisang paraan - ngunit kung kailangan mong gumamit ng mga dynamic na istruktura ng data o mga pandaigdigang variable, dapat mong tingnan ang heap.
Bunton
Ang heap ay isang memory store, na matatagpuan din sa RAM, na nagbibigay-daan sa memorya na dynamic na mailaan at hindi gumagana tulad ng isang stack: ito ay isang kamalig lamang para sa iyong mga variable. Kapag naglaan ka ng isang piraso ng memorya sa heap upang mag-imbak ng isang variable, maaari itong ma-access hindi lamang sa thread, ngunit sa buong application. Ito ay kung paano tinukoy ang mga pandaigdigang variable. Kapag natapos ang application, ang lahat ng inilalaan na lugar ng memorya ay ilalabas. Ang laki ng heap ay itinakda kapag nagsimula ang application, ngunit, hindi katulad ng stack, pisikal lang itong limitado, at ito ay nagbibigay-daan sa iyong lumikha ng mga dynamic na variable.
Nakikipag-ugnayan ka sa heap sa pamamagitan ng mga sanggunian, karaniwang tinatawag na mga pointer - ito ay mga variable na ang mga halaga ay mga address ng iba pang mga variable. Kapag lumikha ka ng isang pointer, itinuro mo ang isang lokasyon ng memorya sa heap, na nagtatakda ng paunang halaga ng variable at nagsasabi sa program kung saan maa-access ang halagang iyon. Dahil sa dynamic na katangian ng heap, ang CPU ay hindi nakikilahok sa kontrol nito; Sa mga wikang walang basurero (C, C++), kailangang manu-manong palayain ng developer ang mga lugar ng memorya na hindi na kailangan. Kung hindi ito gagawin, maaaring mangyari ang mga pagtagas ng memorya at pagkapira-piraso, na makabuluhang magpapabagal sa heap.
Kung ikukumpara sa stack, ang heap ay mas mabagal dahil ang mga variable ay nakakalat sa memorya sa halip na nakaupo sa tuktok ng stack. Ang maling pamamahala ng memorya sa heap ay humahantong sa pagbagal ng operasyon nito; gayunpaman, hindi nito binabawasan ang kahalagahan nito - kung kailangan mong gumamit ng mga dynamic o global variable, gumamit ng heap.
salansan
Ang stack ay ang pinakasikat at marahil ang pinakamahalagang istraktura ng data sa programming. Ang stack ay isang storage device kung saan aalisin ang mga elemento sa reverse order ng kanilang karagdagan. Parang irregular queue, kung saan ang unang ihain ay ang huling nakapasok. Sa literatura ng programming, ang mga pagdadaglat ay karaniwang tinatanggap upang tukuyin ang disiplina ng pila at stack. Ang disiplina sa pila ay itinalagang FIFO, na nangangahulugang Una Sa Unang Labas. Ang disiplina sa stack ay itinalagang LIFO, huling sa unang labas (Huling Sa Unang Out).
Ang stack ay maaaring isipin bilang isang tubo na may spring-loaded na ilalim, na matatagpuan patayo. Ang itaas na dulo ng tubo ay bukas, ang mga elemento ay maaaring idagdag, o, gaya ng sinasabi nila, itinulak dito. Ang pangkalahatang tinatanggap na mga terminong Ingles sa bagay na ito ay napakakulay; Ang isang bagong elementong idinaragdag ay nagtutulak sa mga elementong dati nang inilagay sa stack pababa sa isang posisyon. Kapag nag-pop ang mga elemento mula sa stack, itinutulak sila pataas, sa English pop (“shoot”).
Ang isang halimbawa ng isang stack ay isang haystack, isang stack ng mga papel sa isang table, isang stack ng mga plato, atbp. Dito nagmula ang pangalang stack, na nangangahulugang stack sa English. Ang mga plate ay tinanggal mula sa stack sa reverse order ng kanilang karagdagan. Tanging ang tuktok na plato ay naa-access, i.e. plato sa ibabaw ng stack. Ang isang magandang halimbawa ay isang railway dead end kung saan ang mga sasakyan ay maaaring isalansan.
Ang stack ay madalas na ginagamit, at sa iba't ibang sitwasyon. Ang mga ito ay nagkakaisa sa pamamagitan ng sumusunod na layunin: kailangan mong i-save ang ilang trabaho na hindi pa nakumpleto, kung kailangan mong lumipat sa isa pang gawain. Ang stack ay ginagamit upang pansamantalang iimbak ang estado ng isang gawain na hindi pa nakumpleto. Pagkatapos i-save ang estado, lumipat ang computer sa isa pang gawain. Sa pagkumpleto ng pagpapatupad nito, ang estado ng ipinagpaliban na gawain ay naibalik mula sa stack, at ang computer ay nagpapatuloy sa nagambalang operasyon.
Bakit ginagamit ang stack upang i-save ang estado ng isang nagambalang trabaho? Ipagpalagay natin na ang computer ay gumaganap ng gawain A. Sa panahon ng pagpapatupad nito, ang pangangailangan ay lumitaw upang maisagawa ang gawain B. Ang estado ng gawain A ay naaalala, at ang computer ay nagpapatuloy upang isagawa ang gawain B. Ngunit kahit na gumaganap ng gawain B, ang computer ay maaaring lumipat sa isa pang gawain C, at kakailanganin itong i-save ang estado ng gawain B bago lumipat sa C. Sa paglaon, sa pagkumpleto ng C, ang estado ng gawain B ay ibabalik muna, pagkatapos, sa pagkumpleto ng B, ang estado ng gawain A. Kaya, ang pagpapanumbalik ay nangyayari sa reverse order ng pag-save, na tumutugma sa stack na disiplina.
Pinapayagan ka ng stack na ayusin ang recursion, i.e. ang isang subroutine ay tumatawag sa sarili nito, direkta man o sa pamamagitan ng isang hanay ng iba pang mga tawag. Halimbawa, hayaan ang routine A na magsagawa ng algorithm na nakadepende sa isang input parameter X at posibleng sa estado ng global data. Para sa pinakasimpleng mga halaga ng X, ang algorithm ay ipinatupad nang direkta. Sa kaso ng mas kumplikadong mga halaga ng X, ang algorithm ay ipinatupad bilang isang pagbawas sa aplikasyon ng parehong algorithm para sa mas simpleng mga halaga ng X. Sa kasong ito, ang subroutine A ay nag-a-access mismo, na ipinapasa ang mas simpleng halaga ng X bilang isang parameter. Susunod, ang isang bagong hanay ng mga lokal na variable ay nilikha at isang variable na naglalaman ng bagong (mas simple) na halaga ng parameter X. Ang tinatawag na subroutine A ay gumagana sa bagong hanay ng mga variable nang hindi sinisira ang nakaraang set. Sa pagtatapos ng tawag, ang lumang hanay ng mga lokal na variable at ang lumang estado ng input parameter X ay ibinabalik mula sa stack, at ang routine ay nagpapatuloy mula sa kung saan ito tumigil.
Sa katunayan, hindi mo na kailangang i-save ang mga halaga ng mga lokal na variable ng subroutine sa stack sa isang espesyal na paraan. Ang katotohanan ay ang mga lokal na variable ng isang subroutine (i.e., ang panloob, gumaganang mga variable, na nilikha sa simula ng pagpapatupad nito at nawasak sa dulo) ay inilalagay sa isang stack na ipinatupad sa hardware batay sa ordinaryong RAM. Sa pinakadulo simula ng trabaho nito, ang subroutine ay kumukuha ng espasyo sa stack para sa mga lokal na variable nito ay karaniwang tinatawag na lugar ng memorya sa hardware stack lokal na variable block o sa Ingles frame("frame"). Sa pagtatapos ng trabaho nito, pinapalaya ng subroutine ang memorya sa pamamagitan ng pag-alis ng block ng mga lokal na variable nito mula sa stack.
Bilang karagdagan sa mga lokal na variable, ang mga return address para sa mga subroutine na tawag ay iniimbak sa hardware stack. Hayaang matawag ang isang subroutine sa isang punto sa programa A B. Bago tawagan ang subroutine B, ang address ng pagtuturo kasunod ng pagtuturo sa pagtawag sa B ay naka-imbak sa stack. Ito ang tinatawag na return address sa program A. Kapag natapos na ito, ipo-pop ng subroutine B ang return address ng program A mula sa stack at ibabalik ang kontrol sa address na iyon. Kaya, ang computer ay nagpapatuloy sa pagpapatupad ng program A, simula sa pagtuturo kasunod ng pagtuturo ng tawag. Karamihan sa mga processor ay may mga espesyal na tagubilin na sumusuporta sa pagtawag sa isang subroutine sa pamamagitan ng unang pagtulak ng return address sa stack at pagbabalik mula sa subroutine sa address na lumabas mula sa stack. Karaniwan ang tawag na utos ay tinatawag na tawag, ang pagbabalik na utos ay tinatawag na pagbabalik.
Ang mga parameter ng isang subroutine o function ay itinutulak din sa stack bago ito tawagin. Ang pagkakasunud-sunod kung saan ang mga ito ay inilalagay sa stack ay depende sa mga kumbensyon ng mataas na antas ng mga wika. Kaya, sa C o C++ na wika, ang unang argument ng isang function ay nasa tuktok ng stack, sa ibaba nito ay ang pangalawa, at iba pa. Sa Pascal, ito ay kabaligtaran: ang huling argumento ng function ay nasa tuktok ng stack. (Ito ang dahilan kung bakit, sa pamamagitan ng paraan, ang mga function na may variable na bilang ng mga argumento, tulad ng printf, ay posible sa C, ngunit hindi sa Pascal.)
Sa Fortran-4, isa sa pinakamatanda at pinakamatagumpay na programming language, ang mga argumento ay ipinapasa sa isang espesyal na lugar ng memorya, na maaaring hindi matatagpuan sa stack, dahil hanggang sa katapusan ng 70s ng ika-20 siglo ay mayroon pa ring mga computer tulad ng IBM 360 o ES na mga computer na walang stack ng pagpapatupad ng hardware. Ang mga return address ay hindi rin nakaimbak sa stack, ngunit sa mga memory cell na naayos para sa bawat subroutine. Tinatawag ng mga programmer ang naturang memorya na static sa kahulugan na ang mga static na variable ay palaging sumasakop sa parehong lugar sa memorya anumang oras sa panahon ng pagpapatupad ng programa. Kapag gumagamit lamang ng static na memorya, hindi posible ang recursion dahil ang mga dating halaga ng mga lokal na variable ay nawasak kapag may ginawang bagong tawag. Ang sanggunian na Fortran-4 ay gumamit lamang ng mga static na variable, at ipinagbabawal ang recursion. Hanggang ngayon, ang wikang Fortran ay malawakang ginagamit sa mga kalkulasyon ng siyentipiko at inhinyero, gayunpaman, ang modernong Fortran-90 na pamantayan ay nagpapakilala na ng stack memory, na inaalis ang mga pagkukulang ng mga naunang bersyon ng wika.
