PHP Master | Struktur Data untuk PHP Devs: Stacks dan Bigleues-tutorial php-php.cn

PHP Master | Struktur Data untuk PHP Devs: Stacks dan Bigleues Struktur data, atau jenis data abstrak (ADT), adalah model yang ditakrifkan oleh koleksi operasi yang boleh dilakukan dengan sendirinya dan dibatasi oleh kekangan terhadap kesan operasi tersebut. Ia mewujudkan dinding antara apa yang boleh dilakukan kepada data yang mendasari dan bagaimana ia dilakukan. Kebanyakan kita sudah biasa dengan susunan dan beratur dalam penggunaan sehari -hari biasa, tetapi apa yang beratur pasar raya dan mesin layan diri ada kaitan dengan struktur data? Mari kita ketahui. Dalam artikel ini saya akan memperkenalkan anda kepada dua jenis data abstrak asas - timbunan dan giliran - yang mempunyai asal -usul mereka dalam penggunaan sehari -hari.

Takeaways Key

Jenis data abstrak (ADT) adalah model yang ditakrifkan oleh satu set operasi yang boleh dilakukan pada mereka. Tumpukan dan beratur adalah ADT asas dengan asal -usul dalam penggunaan sehari -hari. Dalam Sains Komputer, timbunan adalah koleksi berurutan di mana objek terakhir yang diletakkan adalah yang pertama dikeluarkan (LIFO), manakala barisan beroperasi pada asas pertama, pertama keluar (FIFO).

Stack boleh dilaksanakan menggunakan tatasusunan, kerana mereka sudah menyediakan operasi push dan pop. Operasi asas yang menentukan timbunan termasuk init (buat timbunan), tolak (tambahkan item ke bahagian atas), pop (keluarkan item terakhir ditambah), atas (lihat item di atas tanpa mengeluarkannya), dan isEmpty (kembali Sama ada timbunan tidak mengandungi item lagi).

Pelanjutan SPL dalam PHP menyediakan satu set struktur data standard, termasuk kelas SPLSTACK. Kelas SPLSTACK, yang dilaksanakan sebagai senarai yang berkaitan dengan dua kali ganda, menyediakan keupayaan untuk melaksanakan timbunan yang boleh dilalui. Kelas ReadingList, yang dilaksanakan sebagai splstack, boleh melintasi timbunan ke hadapan (top-down) dan mundur (bottom-up).

Baris, satu lagi jenis data abstrak, beroperasi pada asas pertama, pertama keluar (FIFO). Operasi asas yang menentukan barisan termasuk init (buat barisan), enqueue (tambahkan item ke akhir), dequeue (keluarkan item dari depan), dan isEmpty (kembali sama ada barisan tidak mengandungi item lagi). Kelas Splqueue dalam PHP, juga dilaksanakan menggunakan senarai yang berkaitan dengan dua kali ganda, membolehkan pelaksanaan barisan.

Stacks
Dalam penggunaan yang sama, timbunan adalah timbunan objek yang biasanya diatur dalam lapisan - contohnya, timbunan buku di meja anda, atau timbunan dulang di kafeteria sekolah. Dalam istilah sains komputer, timbunan adalah koleksi berurutan dengan harta tertentu, di dalamnya, objek terakhir yang diletakkan pada timbunan, akan menjadi objek pertama yang dikeluarkan. Harta ini biasanya dirujuk sebagai yang terakhir di luar , atau lifo. Mesin layan diri, cip, dan rokok beroperasi pada prinsip yang sama; Item terakhir yang dimuatkan di rak dibekalkan terlebih dahulu. Dalam istilah abstrak, timbunan adalah senarai linear item di mana semua penambahan kepada ("tolak") dan penghapusan dari ("pop") senarai itu terhad kepada satu hujung - ditakrifkan sebagai "atas" (dari timbunan ). Operasi asas yang menentukan timbunan adalah:

init - Buat timbunan.

tolak - tambahkan item ke bahagian atas timbunan.

Pop - Keluarkan item terakhir yang ditambahkan ke bahagian atas timbunan.

atas - lihat item di bahagian atas timbunan tanpa mengeluarkannya.

isEmpty - kembali sama ada timbunan tidak mengandungi item lagi.

Tumpukan juga boleh dilaksanakan untuk mempunyai kapasiti maksimum. Sekiranya timbunan penuh dan tidak mengandungi slot yang cukup untuk menerima entiti baru, ia dikatakan sebagai limpahan - oleh itu frasa "limpahan timbunan". Begitu juga, jika operasi pop dicuba pada timbunan kosong maka "stack underflow" berlaku. Mengetahui bahawa timbunan kami ditakrifkan oleh harta LIFO dan beberapa operasi asas, terutamanya PUSH dan POP, kami dapat dengan mudah melaksanakan timbunan menggunakan tatasusunan sejak tatasusunan sudah menyediakan operasi push dan pop. Inilah yang kelihatan seperti timbunan kami:
<?php class ReadingList { protected $stack; protected $limit; public function __construct($limit = 10) { // initialize the stack $this->stack = array(); // stack can only contain this many items $this->limit = $limit; } public function push($item) { // trap for stack overflow if (count($this->stack) < $this->limit) { // prepend item to the start of the array array_unshift($this->stack, $item); } else { throw new RunTimeException('Stack is full!'); } } public function pop() { if ($this->isEmpty()) { // trap for stack underflow throw new RunTimeException('Stack is empty!'); } else { // pop item from the start of the array return array_shift($this->stack); } } public function top() { return current($this->stack); } public function isEmpty() { return empty($this->stack); } }
Salin selepas log masuk
Salin selepas log masuk
Salin selepas log masuk
Dalam contoh ini, saya telah menggunakan array_unshift () dan array_shift (), bukannya array_push () dan array_pop (), supaya elemen pertama timbunan selalu menjadi bahagian atas. Anda boleh menggunakan array_push () dan array_pop () untuk mengekalkan konsistensi semantik, dalam hal ini, elemen Nth timbunan menjadi bahagian atas. Ia tidak membezakan sama ada cara kerana keseluruhan tujuan jenis data abstrak adalah untuk abstrak manipulasi data dari pelaksanaannya yang sebenarnya. Mari tambahkan beberapa item ke timbunan:
<?php $myBooks = new ReadingList(); $myBooks->push('A Dream of Spring'); $myBooks->push('The Winds of Winter'); $myBooks->push('A Dance with Dragons'); $myBooks->push('A Feast for Crows'); $myBooks->push('A Storm of Swords'); $myBooks->push('A Clash of Kings'); $myBooks->push('A Game of Thrones');
Salin selepas log masuk
Salin selepas log masuk
Salin selepas log masuk
Untuk mengeluarkan beberapa item dari timbunan:
<?php echo $myBooks->pop(); // outputs 'A Game of Thrones' echo $myBooks->pop(); // outputs 'A Clash of Kings' echo $myBooks->pop(); // outputs 'A Storm of Swords'
Salin selepas log masuk
Salin selepas log masuk
Mari lihat apa yang ada di bahagian atas timbunan:
<?php echo $myBooks->top(); // outputs 'A Feast for Crows'
Salin selepas log masuk
Salin selepas log masuk
Bagaimana jika kita mengeluarkannya?
<?php echo $myBooks->pop(); // outputs 'A Feast for Crows'
Salin selepas log masuk
Dan jika kita menambah item baru?
<?php $myBooks->push('The Armageddon Rag'); echo $myBooks->pop(); // outputs 'The Armageddon Rag'
Salin selepas log masuk
Anda dapat melihat timbunan beroperasi pada dasar pertama. Apa yang terakhir ditambah ke timbunan adalah yang pertama dikeluarkan. Sekiranya anda terus memaparkan item sehingga timbunan kosong, anda akan mendapat pengecualian runtime bawah aliran.
PHP Fatal error: Uncaught exception 'RuntimeException' with message 'Stack is empty!' in /home/ignatius/Data Structures/code/array_stack.php:33 Stack trace: #0 /home/ignatius/Data Structures/code/example.php(31): ReadingList->pop() #1 /home/ignatius/Data Structures/code/array_stack.php(54): include('/home/ignatius/...') #2 {main} thrown in /home/ignatius/Data Structures/code/array_stack.php on line 33
Salin selepas log masuk
Oh, hello ... PHP telah memberikan jejak stack yang menunjukkan program panggilan pelaksanaan program sebelum dan sehingga pengecualian!
splstack
Sambungan SPL menyediakan satu set struktur data standard, termasuk kelas SPLSTACK (Php5> = 5.3.0). Kita boleh melaksanakan objek yang sama, walaupun lebih tersembunyi, menggunakan splstack seperti berikut:
<?php class ReadingList extends SplStack { }
Salin selepas log masuk
Kelas SPLSTACK melaksanakan beberapa kaedah lagi daripada yang telah ditakrifkan pada asalnya. Ini kerana Splstack dilaksanakan sebagai senarai yang berkaitan dengan dua kali ganda, yang menyediakan keupayaan untuk melaksanakan timbunan yang boleh dilalui. Senarai yang dipautkan, yang merupakan satu lagi jenis data abstrak itu sendiri, adalah koleksi objek linear (nod) yang digunakan untuk mewakili urutan tertentu, di mana setiap nod dalam koleksi mengekalkan penunjuk ke nod seterusnya dalam koleksi. Dalam bentuk yang paling mudah, senarai yang dipautkan kelihatan seperti ini:

PHP Master | Struktur Data untuk PHP Devs: Stacks dan Bigleues Dalam senarai yang berkaitan dengan dua kali ganda, setiap nod mempunyai dua petunjuk, masing-masing menunjuk ke nod seterusnya dan sebelumnya dalam koleksi. Struktur data jenis ini membolehkan traversal di kedua -dua arah.

PHP Master | Struktur Data untuk PHP Devs: Stacks dan Bigleues Node yang ditandai dengan salib (x) menandakan nod null atau sentinel - yang menunjuk hujung laluan traversal (iaitu terminator jalan). Oleh kerana ReadingList dilaksanakan sebagai splstack, kita boleh melintasi timbunan ke hadapan (top-down) dan ke belakang (bottom-up). Mod Traversal lalai untuk splstack adalah LIFO:

<span><span><?php
</span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) < $this->limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span>

~~Salin selepas log masuk~~

Untuk melintasi timbunan dalam urutan terbalik, kami hanya menetapkan mod Iterator ke FIFO (pertama, pertama keluar):
<?php $myBooks = new ReadingList(); $myBooks->push('A Dream of Spring'); $myBooks->push('The Winds of Winter'); $myBooks->push('A Dance with Dragons'); $myBooks->push('A Feast for Crows'); $myBooks->push('A Storm of Swords'); $myBooks->push('A Clash of Kings'); $myBooks->push('A Game of Thrones');
Salin selepas log masuk
Salin selepas log masuk
Salin selepas log masuk

beratur
Sekiranya anda pernah berada di barisan di checkout pasar raya, maka anda akan tahu bahawa orang pertama dalam talian akan disampaikan terlebih dahulu. Dalam istilah komputer, barisan adalah satu lagi jenis data abstrak, yang beroperasi pada pertama di luar asas, atau FIFO. Inventori juga diuruskan secara fifo, terutamanya jika barang -barang tersebut bersifat mudah rosak. Operasi asas yang menentukan barisan adalah:

init - Buat giliran.

enqueue - tambahkan item ke "akhir" (ekor) barisan.

Dequeue - Keluarkan item dari "depan" (kepala) barisan.

isempty - kembali sama ada barisan mengandungi tidak lagi item.

Oleh kerana Splqueue juga dilaksanakan dengan menggunakan senarai yang berkaitan dengan ganda, makna semantik atas dan pop dibalikkan dalam konteks ini. Mari kita mentakrifkan semula kelas bacaan kami sebagai barisan:
<?php class ReadingList { protected $stack; protected $limit; public function __construct($limit = 10) { // initialize the stack $this->stack = array(); // stack can only contain this many items $this->limit = $limit; } public function push($item) { // trap for stack overflow if (count($this->stack) < $this->limit) { // prepend item to the start of the array array_unshift($this->stack, $item); } else { throw new RunTimeException('Stack is full!'); } } public function pop() { if ($this->isEmpty()) { // trap for stack underflow throw new RunTimeException('Stack is empty!'); } else { // pop item from the start of the array return array_shift($this->stack); } } public function top() { return current($this->stack); } public function isEmpty() { return empty($this->stack); } }
Salin selepas log masuk
Salin selepas log masuk
Salin selepas log masuk
SpldoublyLinkedList Juga melaksanakan antara muka ArrayaCcess supaya anda juga boleh menambah item ke Splqueue dan Splstack sebagai Elemen Array:
<?php $myBooks = new ReadingList(); $myBooks->push('A Dream of Spring'); $myBooks->push('The Winds of Winter'); $myBooks->push('A Dance with Dragons'); $myBooks->push('A Feast for Crows'); $myBooks->push('A Storm of Swords'); $myBooks->push('A Clash of Kings'); $myBooks->push('A Game of Thrones');
Salin selepas log masuk
Salin selepas log masuk
Salin selepas log masuk
Untuk mengeluarkan item dari hadapan barisan:
<?php echo $myBooks->pop(); // outputs 'A Game of Thrones' echo $myBooks->pop(); // outputs 'A Clash of Kings' echo $myBooks->pop(); // outputs 'A Storm of Swords'
Salin selepas log masuk
Salin selepas log masuk
enqueue () adalah alias untuk menolak (), tetapi perhatikan bahawa dequeue () bukan alias untuk pop (); Pop () mempunyai makna dan fungsi yang berbeza dalam konteks barisan. Jika kami telah menggunakan pop () di sini, ia akan mengeluarkan item dari hujung (ekor) barisan yang melanggar peraturan FIFO. Begitu juga, untuk melihat apa yang ada di hadapan (kepala) barisan, kita perlu menggunakan bawah () bukannya atas ():
<?php echo $myBooks->top(); // outputs 'A Feast for Crows'
Salin selepas log masuk
Salin selepas log masuk

Ringkasan
Dalam artikel ini, anda telah melihat bagaimana jenis data abstrak dan barisan abstrak digunakan dalam pengaturcaraan. Struktur data ini adalah abstrak, di mana ia ditakrifkan oleh operasi yang boleh dilakukan dengan sendirinya, dengan itu mewujudkan dinding antara pelaksanaannya dan data yang mendasari. Struktur ini juga dikekang oleh kesan operasi sedemikian: anda hanya boleh menambah atau mengeluarkan item dari bahagian atas timbunan, dan anda hanya boleh mengeluarkan item dari hadapan barisan, atau menambah item ke bahagian belakang barisan. imej oleh Alexandre Dulaunoy melalui Flickr
Soalan Lazim (Soalan Lazim) Mengenai Struktur Data PHP

Apakah jenis struktur data yang berlainan dalam php?

php menyokong beberapa jenis struktur data, termasuk tatasusunan, objek, dan sumber. Array adalah struktur data yang paling biasa dan serba boleh dalam PHP. Mereka boleh memegang apa -apa jenis data, termasuk tatasusunan lain, dan boleh diindeks atau bersekutu. Objek dalam PHP adalah contoh kelas, yang boleh mempunyai sifat dan kaedah. Sumber adalah pembolehubah khas yang memegang rujukan kepada sumber luaran, seperti sambungan pangkalan data. Terakhir, pertama keluar) prinsip. Dalam PHP, anda boleh menggunakan kelas Splstack untuk melaksanakan timbunan. Anda boleh menolak elemen ke timbunan menggunakan kaedah push (), dan elemen pop dari timbunan menggunakan kaedah pop ().

Apakah perbezaan antara tatasusunan dan objek dalam php? Array dan objek dalam PHP adalah kedua -dua jenis struktur data, tetapi mereka mempunyai beberapa perbezaan utama. Array adalah senarai nilai yang mudah, manakala objek adalah contoh kelas dan boleh mempunyai sifat dan kaedah. Array boleh diindeks atau bersekutu, sementara objek selalu menggunakan kekunci rentetan. Array lebih serba boleh dan lebih mudah digunakan, sementara objek memberikan lebih banyak struktur dan enkapsulasi.

Bagaimana saya boleh menggunakan struktur data untuk meningkatkan prestasi kod PHP saya? Sebagai contoh, jika anda perlu menyimpan sejumlah besar elemen dan kerap mencari unsur -unsur tertentu, menggunakan jadual hash atau set boleh menjadi lebih cepat daripada menggunakan array. Begitu juga, jika anda perlu sering menambah dan mengalih keluar unsur -unsur di kedua -dua hujungnya, menggunakan deque boleh lebih cekap daripada menggunakan array. Dalam PHP adalah struktur data yang melaksanakan senarai dikaitkan dua kali ganda. Ia membolehkan anda menambah, mengeluarkan, dan mengakses elemen di kedua -dua hujung senarai dalam masa yang berterusan. Ia juga menyediakan kaedah untuk melelehkan unsur -unsur dalam senarai, dan untuk menyusun unsur -unsur. FIFO (pertama dalam, pertama keluar) prinsip. Dalam PHP, anda boleh menggunakan kelas Splqueue untuk melaksanakan barisan. Anda boleh memupuk unsur -unsur ke dalam barisan menggunakan kaedah enqueue (), dan elemen dequeue dari barisan menggunakan kaedah dequeue (). 🎜> Stack dan giliran adalah kedua -dua jenis struktur data, tetapi mereka mempunyai perbezaan utama dalam bagaimana elemen ditambah dan dikeluarkan. Tumpukan mengikuti prinsip LIFO (terakhir, pertama keluar), yang bermaksud bahawa elemen terakhir yang ditambah adalah yang pertama dikeluarkan. Satu barisan, sebaliknya, mengikuti prinsip FIFO (pertama dalam, keluar pertama), yang bermaksud bahawa elemen pertama yang ditambah adalah yang pertama dikeluarkan.

Kelas Splheap dalam PHP adalah struktur data yang melaksanakan timbunan. Tumpukan adalah sejenis pokok binari di mana setiap nod induk kurang daripada atau sama dengan nod anaknya. Anda boleh menggunakan kelas SPLHEAP untuk membuat t-s-sheap atau max-shap, dan untuk menambah, mengeluarkan, dan mengakses unsur-unsur dalam timbunan. >

menggunakan struktur data dalam PHP boleh memberikan beberapa faedah. Mereka boleh membantu anda mengatur data anda dengan cara yang lebih cekap dan logik, yang boleh menjadikan kod anda lebih mudah difahami dan diselenggara. Mereka juga boleh meningkatkan prestasi kod anda, terutamanya apabila berurusan dengan sejumlah besar data atau operasi kompleks. struktur data di mana setiap nod mempunyai paling banyak dua kanak -kanak, yang disebut sebagai anak kiri dan anak yang tepat. Dalam PHP, anda boleh melaksanakan pokok binari menggunakan kelas yang mempunyai sifat untuk nilai nod dan anak -anak kiri dan kanan. Anda kemudian boleh menggunakan kaedah untuk menambah, mengeluarkan, dan mencari nod di dalam pokok.

Atas ialah kandungan terperinci PHP Master | Struktur Data untuk PHP Devs: Stacks dan Bigleues. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!