Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00240 002718 12928863 na godz. na dobę w sumie
PHP 7. Algorytmy i struktury danych - ebook/pdf
PHP 7. Algorytmy i struktury danych - ebook/pdf
Autor: Liczba stron: 312
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-283-4086-2 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> webmasterstwo >> php - programowanie
Porównaj ceny (książka, ebook (-40%), audiobook).

Algorytmy i struktury danych leżą u podstaw programowania. Zrozumienie zasad rządzących tymi zagadnieniami jest koniecznym warunkiem opracowania prawidłowej i efektywnej aplikacji. Niestety, wielu programistów uznaje tę tematykę za zbyt złożoną czy zbyt banalną i nie poświęca jej wystarczającej uwagi. Takie podejście często się mści: modne narzędzia, frameworki czy technologie deweloperskie nie zapewnią sukcesu, jeśli projektant nie przemyśli zastosowanych algorytmów i struktur danych. Z tego obowiązku nie zwalniają nawet narzędzia wbudowane w język PHP!

Jeśli chcesz biegle posługiwać się algorytmami, wziąłeś do ręki właściwą książkę! Przedstawiono tu podstawy implementacji algorytmów i struktur danych w PHP, dzięki czemu poznasz rodzaje struktur i powody, dla których warto je wybierać, a także dowiesz się, gdzie i kiedy należy stosować poszczególne algorytmy. Znajdziesz tu dużo praktycznych przykładów, które uzupełniono rysunkami i wyczerpującym komentarzem. Przystępne i zrozumiałe wyjaśnienia ułatwią Ci szybkie przyswojenie prezentowanych koncepcji, nawet tak złożonych, jak programowanie dynamiczne, algorytmy zachłanne, algorytmy z nawrotami czy funkcyjne struktury danych.

Najważniejsze zagadnienia:

Algorytmy: poznaj, zrozum, stosuj!


Mizanur Rahman od 14 lat rozwija aplikacje w PHP. Jest znawcą Laravela, CodeIgnitera, Symfony, JavaScriptu, C, C++, Javy, Node.js, Socket.io i React.js. Jest właścicielem dwóch startupów technologicznych. Jest osobą niezwykle zaangażowaną w życie kilku społeczności programistycznych, takich jak PHPXperts, Agile Bangladesh czy Project Euler. Regularnie wygłasza referaty na różnych konferencjach i seminariach technologicznych. Wraz z żoną Nishą i dwoma synami, Adiyanem i Mikhaelem, mieszka w Dhace w Bangladeszu. Jego pasją są podróże po świecie.

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

Tytuł oryginału: PHP 7 Data Structures and Algorithms Tłumaczenie: Łukasz Suma ISBN: 978-83-283-4085-5 Copyright © Packt Publishing 2017 First published in the English language under the title „PHP 7 Data Structures and Algorithms - (9781786463890)”. Polish edition copyright © 2018 by Helion SA All rights reserved. All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from the Publisher. Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje naruszenie praw autorskich niniejszej publikacji. Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich właścicieli. Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Wydawnictwo HELION ul. Kościuszki 1c, 44-100 GLIWICE tel. 32 231 22 19, 32 230 98 63 e-mail: helion@helion.pl WWW: http://helion.pl (księgarnia internetowa, katalog książek) Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie/php7al Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Spis tre(cid:258)ci Wst(cid:218)p Rozdzia(cid:239) 1. Wprowadzenie do algorytmów i struktur danych Znaczenie algorytmów i struktur danych Znaczenie abstrakcyjnych typów danych (ADT) Ró(cid:285)ne struktury danych Struktura Tablica Lista jednokierunkowa Lista dwukierunkowa Stos Kolejka Zbiór Mapa (tablica asocjacyjna) Drzewo Graf Sterta (kopiec) Rozwi(cid:200)zywanie problemu — podej(cid:258)cie algorytmiczne Pisanie pseudokodu Przekszta(cid:239)canie pseudokodu w prawdziwy kod Analiza algorytmu Obliczanie z(cid:239)o(cid:285)ono(cid:258)ci Zrozumienie notacji du(cid:285)ego O Standardowa biblioteka PHP (SPL) i struktury danych Podsumowanie Rozdzia(cid:239) 2. Zrozumienie tablic PHP Zrozumienie tablic PHP w lepszy sposób Tablica liczbowa Tablica asocjacyjna Tablica wielowymiarowa 15 19 20 23 24 25 25 26 26 27 27 28 28 28 29 29 30 31 32 33 34 35 37 38 39 39 41 42 43 Poleć książkęKup książkę Spis tre(cid:286)ci U(cid:285)ywanie tablicy jako elastycznego sposobu przechowywania danych U(cid:285)ywanie wielowymiarowych tablic do reprezentowania struktur danych Tworzenie tablic o sta(cid:239)ym rozmiarze za pomoc(cid:200) klasy SplFixedArray Porównanie wydajno(cid:258)ci zwyk(cid:239)ych tablic PHP oraz tablic SplFixedArray Wi(cid:218)cej przyk(cid:239)adów zastosowania tablicy SplFixedArray Zrozumienie tablic mieszaj(cid:200)cych Implementacja struktury przy u(cid:285)yciu tablicy PHP Implementacja zbioru przy u(cid:285)yciu tablicy PHP Najlepsze zastosowanie tablicy PHP Czy tablica PHP jest zabójc(cid:200) wydajno(cid:258)ci? Podsumowanie Rozdzia(cid:239) 3. U(cid:285)ywanie list Czym jest lista? Ró(cid:285)ne typy list Lista dwukierunkowa Lista cykliczna Lista wielokierunkowa Wstawianie, usuwanie i wyszukiwanie elementu Wstawianie w(cid:218)z(cid:239)a na pierwszej pozycji Wyszukiwanie w(cid:218)z(cid:239)a Wstawianie przed okre(cid:258)lonym w(cid:218)z(cid:239)em Wstawianie po okre(cid:258)lonym w(cid:218)(cid:283)le Usuwanie pierwszego w(cid:218)z(cid:239)a Usuwanie ostatniego w(cid:218)z(cid:239)a Wyszukiwanie i usuwanie jednego w(cid:218)z(cid:239)a Odwracanie listy Pobieranie elementu z n-tej pozycji Zrozumienie z(cid:239)o(cid:285)ono(cid:258)ci list Sprawianie, aby lista by(cid:239)a iterowalna Budowanie listy cyklicznej Implementacja listy dwukierunkowej w PHP Operacje na li(cid:258)cie dwukierunkowej Wstawianie w(cid:218)z(cid:239)a na pierwszej pozycji Wstawianie w(cid:218)z(cid:239)a na ostatniej pozycji Wstawianie przed okre(cid:258)lonym w(cid:218)z(cid:239)em Wstawianie po okre(cid:258)lonym w(cid:218)(cid:283)le Usuwanie pierwszego w(cid:218)z(cid:239)a Usuwanie ostatniego w(cid:218)z(cid:239)a Wyszukiwanie i usuwanie jednego w(cid:218)z(cid:239)a Wy(cid:258)wietlanie listy od pocz(cid:200)tku do ko(cid:241)ca Wy(cid:258)wietlanie listy od ko(cid:241)ca do pocz(cid:200)tku Z(cid:239)o(cid:285)ono(cid:258)(cid:202) list dwukierunkowych U(cid:285)ywanie obiektów klasy PHP SplDoublyLinkedList Podsumowanie 6 44 45 47 48 51 53 54 55 57 57 58 59 59 63 63 63 64 64 65 65 66 67 67 68 69 69 70 71 72 73 75 75 76 76 77 78 78 79 79 80 80 80 81 82 Poleć książkęKup książkę Spis tre(cid:286)ci Rozdzia(cid:239) 4. Konstruowanie stosów i kolejek Zrozumienie stosu Implementacja stosu za pomoc(cid:200) tablicy PHP Zrozumienie z(cid:239)o(cid:285)ono(cid:258)ci operacji na stosie Implementacja stosu za pomoc(cid:200) listy U(cid:285)ywanie klasy SplStack nale(cid:285)(cid:200)cej do SPL Rzeczywiste zastosowanie stosu Dopasowywanie zagnie(cid:285)d(cid:285)onych nawiasów Zrozumienie kolejki Implementacja kolejki za pomoc(cid:200) tablicy PHP Implementacja kolejki za pomoc(cid:200) listy U(cid:285)ywanie klasy SplQueue nale(cid:285)(cid:200)cej do SPL Zrozumienie kolejki priorytetowej Sekwencja uporz(cid:200)dkowana Sekwencja nieuporz(cid:200)dkowana Implementacja kolejki priorytetowej za pomoc(cid:200) listy Implementacja kolejki priorytetowej za pomoc(cid:200) klasy SplPriorityQueue Implementacja kolejki cyklicznej Tworzenie kolejki dwustronnej Podsumowanie Rozdzia(cid:239) 5. Stosowanie algorytmów rekurencyjnych Zrozumienie rekurencji W(cid:239)a(cid:258)ciwo(cid:258)ci algorytmów rekurencyjnych Algorytmy rekurencyjne kontra algorytmy iteracyjne Implementacja ci(cid:200)gu Fibonacciego za pomoc(cid:200) rekurencji Implementacja obliczania NWD za pomoc(cid:200) rekurencji Ró(cid:285)ne rodzaje rekurencji Rekurencja liniowa Rekurencja binarna Rekurencja ogonowa Rekurencja wzajemna Rekurencja zagnie(cid:285)d(cid:285)ona Budowanie N-poziomowego drzewa kategorii za pomoc(cid:200) rekurencji Budowanie systemu zagnie(cid:285)d(cid:285)onych odpowiedzi na komentarze Wyszukiwanie plików i katalogów za pomoc(cid:200) rekurencji Analizowanie algorytmów rekurencyjnych Maksymalna g(cid:239)(cid:218)boko(cid:258)(cid:202) rekurencji w PHP U(cid:285)ywanie rekurencyjnych iteratorów SPL U(cid:285)ywanie wbudowanej funkcji PHP array_walk_recursive Podsumowanie 83 83 84 87 88 90 90 91 93 94 95 96 96 97 97 97 99 100 102 105 107 108 109 110 111 111 112 112 112 112 113 113 114 116 120 122 123 124 125 126 7 Poleć książkęKup książkę Spis tre(cid:286)ci Rozdzia(cid:239) 6. Zrozumienie i implementacja drzew Definicja i w(cid:239)a(cid:258)ciwo(cid:258)ci drzewa Implementacja drzewa przy u(cid:285)yciu j(cid:218)zyka PHP Ró(cid:285)ne typy struktur drzewiastych Drzewo binarne Drzewo binarne poszukiwa(cid:241) Samorównowa(cid:285)(cid:200)ce si(cid:218) drzewo binarne poszukiwa(cid:241) B-drzewo Drzewo N-arne Zrozumienie drzewa binarnego Implementacja drzewa binarnego Tworzenie drzewa binarnego za pomoc(cid:200) tablicy PHP Zrozumienie binarnego drzewa poszukiwa(cid:241) Wstawianie nowego w(cid:218)z(cid:239)a Wyszukiwanie w(cid:218)z(cid:239)a Wyszukiwanie warto(cid:258)ci minimalnej Wyszukiwanie warto(cid:258)ci maksymalnej Usuwanie w(cid:218)z(cid:239)a Konstruowanie binarnego drzewa poszukiwa(cid:241) Przechodzenie przez drzewo Przechodzenie bezpo(cid:258)rednie Przechodzenie z wyprzedzeniem Przechodzenie z opó(cid:283)nieniem Z(cid:239)o(cid:285)ono(cid:258)(cid:202) ró(cid:285)nych drzewiastych struktur danych Podsumowanie Rozdzia(cid:239) 7. U(cid:285)ywanie algorytmów sortowania Zrozumienie sortowania i jego rodzajów Zrozumienie sortowania b(cid:200)belkowego Implementacja sortowania b(cid:200)belkowego za pomoc(cid:200) j(cid:218)zyka PHP Z(cid:239)o(cid:285)ono(cid:258)(cid:202) sortowania b(cid:200)belkowego Poprawianie algorytmu sortowania b(cid:200)belkowego Zrozumienie sortowania przez wybieranie Implementacja sortowania przez wybieranie Z(cid:239)o(cid:285)ono(cid:258)(cid:202) sortowania przez wybieranie Zrozumienie sortowania przez wstawianie Implementacja sortowania przez wstawianie Z(cid:239)o(cid:285)ono(cid:258)(cid:202) sortowania przez wstawianie Zrozumienie technik sortowania wykorzystuj(cid:200)cych metod(cid:218) dziel i zwyci(cid:218)(cid:285)aj Zrozumienie sortowania przez scalanie Implementacja sortowania przez scalanie Z(cid:239)o(cid:285)ono(cid:258)(cid:202) sortowania przez scalanie Zrozumienie sortowania szybkiego Implementacja sortowania szybkiego Z(cid:239)o(cid:285)ono(cid:258)(cid:202) sortowania szybkiego Zrozumienie sortowania kube(cid:239)kowego U(cid:285)ywanie wbudowanych funkcji sortuj(cid:200)cych PHP Podsumowanie 8 127 128 130 132 132 133 133 135 135 135 136 138 140 141 141 142 142 142 143 151 151 152 153 154 155 157 157 158 159 161 161 165 167 167 168 170 171 171 171 173 174 175 176 178 178 179 180 Poleć książkęKup książkę Spis tre(cid:286)ci Rozdzia(cid:239) 8. Poznawanie technik wyszukiwania Wyszukiwanie liniowe Wyszukiwanie binarne Analiza algorytmu wyszukiwania binarnego Algorytm powtarzalnego wyszukiwania binarnego Przeszukiwanie nieposortowanej tablicy — czy nale(cid:285)y j(cid:200) najpierw posortowa(cid:202)? Wyszukiwanie interpolacyjne Wyszukiwanie wyk(cid:239)adnicze Wyszukiwanie przy u(cid:285)yciu tablicy mieszaj(cid:200)cej Wyszukiwanie w drzewach Przeszukiwanie wszerz Przeszukiwanie w g(cid:239)(cid:200)b Podsumowanie Rozdzia(cid:239) 9. W(cid:239)(cid:200)czanie grafów do akcji Zrozumienie w(cid:239)a(cid:258)ciwo(cid:258)ci grafów Wierzcho(cid:239)ek Kraw(cid:218)d(cid:283) S(cid:200)siedztwo Incydencja Stopie(cid:241) wchodz(cid:200)cy i stopie(cid:241) wychodz(cid:200)cy (cid:165)cie(cid:285)ka Typy grafów Grafy skierowane Grafy nieskierowane Grafy wa(cid:285)one Skierowane grafy acykliczne Reprezentowanie grafów w PHP Algorytmy BFS i DFS dla grafów Przeszukiwanie wszerz Przeszukiwanie w g(cid:239)(cid:200)b Sortowanie topologiczne przy u(cid:285)yciu algorytmu Kahna Wyznaczanie najkrótszej (cid:258)cie(cid:285)ki za pomoc(cid:200) algorytmu Floyda-Warshalla Wyznaczanie najkrótszej (cid:258)cie(cid:285)ki z pojedynczego (cid:283)ród(cid:239)a za pomoc(cid:200) algorytmu Dijkstry Wyznaczanie najkrótszej (cid:258)cie(cid:285)ki za pomoc(cid:200) algorytmu Bellmana-Forda Zrozumienie minimalnego drzewa rozpinaj(cid:200)cego Wyznaczanie minimalnego drzewa rozpinaj(cid:200)cego za pomoc(cid:200) algorytmu Prima Wyznaczanie minimalnego drzewa rozpinaj(cid:200)cego za pomoc(cid:200) algorytmu Kruskala Podsumowanie 181 181 183 187 187 190 191 192 193 194 194 198 203 205 205 206 206 207 208 208 208 209 209 209 210 210 211 212 212 214 216 218 221 224 227 228 231 233 9 Poleć książkęKup książkę Spis tre(cid:286)ci Rozdzia(cid:239) 10. Zrozumienie i u(cid:285)ywanie stert Czym jest sterta? Operacje na stercie Implementacja kopca binarnego w j(cid:218)zyku PHP Analiza z(cid:239)o(cid:285)ono(cid:258)ci operacji na stercie U(cid:285)ywanie sterty jako kolejki priorytetowej U(cid:285)ywanie sortowania przez kopcowanie U(cid:285)ywanie klas SplHeap, SplMaxHeap oraz SplMinHeap Podsumowanie Rozdzia(cid:239) 11. Rozwi(cid:200)zywanie problemów za pomoc(cid:200) technik zaawansowanych Memoizacja Algorytmy dopasowania do wzorca Implementacja algorytmu Knutha-Morrisa-Pratta Algorytmy zach(cid:239)anne Implementacja algorytmu kodowania Huffmana Zrozumienie programowania dynamicznego Dyskretny problem plecakowy Znajdowanie d(cid:239)ugo(cid:258)ci najd(cid:239)u(cid:285)szego wspólnego podci(cid:200)gu Sekwencjonowanie DNA przy u(cid:285)yciu programowania dynamicznego U(cid:285)ywanie algorytmu z nawrotami do rozwi(cid:200)zywania zagadek System rekomendacji u(cid:285)ywaj(cid:200)cy wspólnego filtrowania U(cid:285)ywanie filtrów Blooma i macierzy rzadkich Podsumowanie Rozdzia(cid:239) 12. Obs(cid:239)uga algorytmów i struktur danych przez j(cid:218)zyk PHP Wbudowane w j(cid:218)zyk PHP mo(cid:285)liwo(cid:258)ci zwi(cid:200)zane ze strukturami danych U(cid:285)ywanie tablicy PHP Klasy SPL Algorytmy wbudowane Mieszanie Wbudowane mo(cid:285)liwo(cid:258)ci dost(cid:218)pne dzi(cid:218)ki PECL Instalacja Interfejsy Wektor Mapa Zbiór Stos i kolejka Kolejka dwustronna Kolejka priorytetowa Podsumowanie 10 235 235 236 237 241 242 245 248 248 249 250 252 253 255 256 260 261 262 264 267 271 274 277 279 279 280 283 284 287 288 289 290 290 291 291 293 294 294 295 Poleć książkęKup książkę Spis tre(cid:286)ci Rozdzia(cid:239) 13. Funkcyjne struktury danych w j(cid:218)zyku PHP Zrozumienie programowania funkcyjnego w j(cid:218)zyku PHP Funkcje pierwszej klasy Funkcje wy(cid:285)szego rz(cid:218)du Funkcje czyste Funkcje lambda Domkni(cid:218)cia Rozwijanie funkcji Wykonania cz(cid:218)(cid:258)ciowe Rozpocz(cid:218)cie pracy z bibliotek(cid:200) Tarsana Implementacja stosu Implementacja kolejki Implementacja drzewa Podsumowanie Skorowidz 297 298 299 299 299 300 300 300 301 302 303 304 305 306 307 11 Poleć książkęKup książkę Poleć książkęKup książkę 4 Konstruowanie stosów i kolejek W codziennej praktyce najcz(cid:218)(cid:258)ciej u(cid:285)ywamy dwóch najbardziej popularnych struktur danych. Mo(cid:285)emy za(cid:239)o(cid:285)y(cid:202), (cid:285)e s(cid:200) one wzorowane na obiektach istniej(cid:200)cych w prawdziwym (cid:258)wiecie, maj(cid:200) jednak ogromny wp(cid:239)yw przede wszystkim na (cid:258)wiat komputerowy. Mówimy tu o stosie (ang. stack) i kolejce (ang. queue). W stosy codziennie uk(cid:239)adamy nasze ksi(cid:200)(cid:285)ki, pliki dokumentów, talerze i ubrania, podczas gdy z kolejkami mamy do czynienia przy kasach biletowych, na przystan- kach autobusowych czy na ta(cid:258)mach kasowych supermarketów. S(cid:239)yszeli(cid:258)my te(cid:285) o kolejkach komunikatów w j(cid:218)zyku PHP b(cid:218)d(cid:200)cych jedn(cid:200) z najcz(cid:218)(cid:258)ciej wykorzystywanych funkcji aplikacji biznesowych. W tym rozdziale przyjrzymy si(cid:218) ró(cid:285)nym implementacjom tych popularnych struktur danych, jakimi s(cid:200) stos i kolejka. Poznamy tu zwyk(cid:239)e kolejki, kolejki priorytetowe, kolejki cykliczne oraz kolejki dwustronne. Zrozumienie stosu Stos jest liniow(cid:200) struktur(cid:200) danych, która dzia(cid:239)a zgodnie z regu(cid:239)(cid:200) ostatni na wej(cid:258)ciu, pierwszy na wyj(cid:258)ciu (ang. Last-In, First-Out — LIFO). Oznacza to, (cid:285)e stos ma tylko jedn(cid:200) stron(cid:218), z której mo(cid:285)emy korzysta(cid:202), aby dodawa(cid:202) i usuwa(cid:202) elementy. Dodawanie elementów na stos okre(cid:258)lane jest jako odk(cid:239)adanie ich na stos lub umieszczanie na stosie (ang. push), a operacja usuni(cid:218)cia nosi nazw(cid:218) zdejmowania lub pobierania danych ze stosu (ang. pop). Jako (cid:285)e do dys- pozycji mamy tylko jeden koniec stosu, odk(cid:239)adanie i zdejmowanie realizowane jest zawsze w odniesieniu do tego ko(cid:241)ca. Element znajduj(cid:200)cy si(cid:218) na tym ko(cid:241)cu, czyli na samym wierzchu stosu, okre(cid:258)lany jest mianem szczytu lub wierzcho(cid:239)ka (ang. top) stosu. Je(cid:258)li przyjrzymy si(cid:218) przedstawionemu poni(cid:285)ej rysunkowi, mo(cid:285)emy zauwa(cid:285)y(cid:202), (cid:285)e ka(cid:285)da opera- cja od(cid:239)o(cid:285)enia elementu na stos i zdj(cid:218)cia go ze stosu powoduje, (cid:285)e wierzcho(cid:239)ek si(cid:218) zmienia. Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych Operacje na stosie przeprowadzane s(cid:200) zawsze na jego szczycie, nigdy na pocz(cid:200)tku lub w (cid:258)rodku. Musimy zachowa(cid:202) szczególn(cid:200) ostro(cid:285)no(cid:258)(cid:202) przy operacji zdejmowania elementu z pustego stosu oraz odk(cid:239)adania elementu na stos, gdy stos ten jest pe(cid:239)ny. Gdy próbujemy umie(cid:258)ci(cid:202) na stosie wi(cid:218)cej elementów, ni(cid:285) jest on w stanie przyj(cid:200)(cid:202), mo(cid:285)emy otrzyma(cid:202) b(cid:239)(cid:200)d przepe(cid:239)nienia stosu (ang. stack overflow error). Z wcze(cid:258)niejszego opisu wiemy ju(cid:285), (cid:285)e na stosie mo(cid:285)na wykona(cid:202) cztery podstawowe operacje: (cid:81) push: dodawanie elementu na szczyt stosu; (cid:81) pop: usuni(cid:218)cie elementu ze szczytu stosu; (cid:81) top: zwrócenie szczytowego elementu stosu; operacja ta nie jest to(cid:285)sama z poprzedni(cid:200), poniewa(cid:285) w jej przypadku element nie jest usuwany ze stosu, zwracana jest tylko jego warto(cid:258)(cid:202); (cid:81) isEmpty: sprawdzenie, czy stos jest pusty. Teraz zajmiemy si(cid:218) implementacj(cid:200) stosu w j(cid:218)zyku PHP, zrobimy to jednak na kilka ró(cid:285)nych sposobów. Najpierw spróbujemy zaimplementowa(cid:202) stos, korzystaj(cid:200)c z wbudowanej w PHP ta- blicy. Nast(cid:218)pnie przyjrzymy si(cid:218) sposobowi zbudowania stosu bez niej, lecz przy u(cid:285)yciu in- nych struktur danych, takich jak listy. Implementacja stosu za pomoc(cid:200) tablicy PHP Najpierw utworzymy interfejs stosu, z którego b(cid:218)dziemy korzystali, tworz(cid:200)c nasze ró(cid:285)ne im- plementacje, i który pomo(cid:285)e nam zapewni(cid:202), (cid:285)e wszystkie te implementacje w(cid:239)a(cid:258)ciwie wyko- nuj(cid:200) stawiane przed nimi zadanie. Prosty interfejs stosu wygl(cid:200)da nast(cid:218)puj(cid:200)co: 84 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek interface Stack { public function push(string $item); public function pop(); public function top(); public function isEmpty(); } Jak tu widzimy, w interfejsie uwzgl(cid:218)dniamy wszystkie funkcje stosu, poniewa(cid:285) implementuj(cid:200)- ca go klasa musi zawiera(cid:202) je wszystkie; w przeciwnym razie w czasie wykonania zg(cid:239)oszony zostanie b(cid:239)(cid:200)d krytyczny. Jako (cid:285)e nasz stos implementujemy za pomoc(cid:200) tablicy PHP, opraco- wuj(cid:200)c metody odpowiedzialne za operacje odk(cid:239)adania na stos, zdejmowania ze stosu i spraw- dzania warto(cid:258)ci elementu szczytowego, skorzystamy z pewnych istniej(cid:200)cych ju(cid:285) funkcji PHP. Stos zdefiniujemy w taki sposób, aby by(cid:202) w stanie okre(cid:258)li(cid:202) jego wielko(cid:258)(cid:202). Je(cid:258)li podj(cid:218)ta zosta- nie próba zdj(cid:218)cia elementu z naszego pustego stosu, zg(cid:239)oszony b(cid:218)dzie wyj(cid:200)tek niedoboru (ang. underflow exception), a je(cid:258)li spróbujemy umie(cid:258)ci(cid:202) na stosie wi(cid:218)cej elementów, ni(cid:285) jest on w stanie przyj(cid:200)(cid:202), pojawi si(cid:218) wyj(cid:200)tek przepe(cid:239)nienia (ang. overflow exception). Oto kod zapew- niaj(cid:200)cy implementacj(cid:218) stosu przy u(cid:285)yciu tablicy: class Books implements Stack { private $limit; private $stack; public function __construct(int $limit = 20) { $this- limit = $limit; $this- stack = []; } public function pop(): string { if ($this- isEmpty()) { throw new UnderflowException( Stos jest pusty ); } else { return array_pop($this- stack); } } public function push(string $newItem) { if (count($this- stack) $this- limit) { array_push($this- stack, $newItem); } else { throw new OverflowException( Stos jest pe(cid:239)ny ); } } 85 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych public function top(): string { return end($this- stack); } public function isEmpty(): bool { return empty($this- stack); } } Przeanalizujmy teraz nasz kod implementuj(cid:200)cy stos. Klasie stosu nadali(cid:258)my nazw(cid:218) Books, ale mogliby(cid:258)my nazwa(cid:202) j(cid:200) dowolnie inaczej, pod warunkiem (cid:285)e ta nazwa spe(cid:239)nia(cid:239)aby formalne wymogi j(cid:218)zyka. Implementacj(cid:218) zaczynamy od metody __construct, która umo(cid:285)liwia nam okre(cid:258)lenie maksymalnej liczby elementów przechowywanych na stosie. Domy(cid:258)ln(cid:200) warto(cid:258)ci(cid:200) jest tu 20. Nast(cid:218)pna metoda stanowi implementacj(cid:218) operacji zdejmowania elementu ze stosu: public function pop(): string { if ($this- isEmpty()) { throw new UnderflowException( Stos jest pusty ); } else { return array_pop($this- stack); } } Metoda pop zwraca (cid:239)a(cid:241)cuch znakowy, je(cid:258)li stos nie jest pusty. Sprawdzenie tego warunku od- bywa si(cid:218) za pomoc(cid:200) specjalnej metody, któr(cid:200) zdefiniowali(cid:258)my w klasie stosu. Je(cid:258)li stos jest pusty, zg(cid:239)oszony zostaje wyj(cid:200)tek UnderFlowException, zdefiniowany w SPL. Je(cid:258)li nie ma ele- mentu do zdj(cid:218)cia, mo(cid:285)emy w ten sposób sprawi(cid:202), aby ta operacja nie by(cid:239)a wykonywana. Je(cid:258)li stos nie jest pusty, korzystamy z zapewnianej przez PHP funkcji array_pop, aby zwróci(cid:202) ostatni element naszej tablicy. W metodzie push odbywa si(cid:218) dzia(cid:239)anie odwrotne do tego, które wykonuje metoda pop. Naj- pierw sprawdzamy, czy stos jest pe(cid:239)ny. Je(cid:258)li nie, dodajemy do jego ko(cid:241)ca element b(cid:218)d(cid:200)cy (cid:239)a(cid:241)- cuchem znakowym, korzystaj(cid:200)c w tym celu z zapewnianej przez PHP funkcji array_push. Je(cid:258)li stos jest pe(cid:239)ny, zg(cid:239)aszamy wyj(cid:200)tek OverFlowException, który zosta(cid:239) zdefiniowany w SPL. Metoda top zwraca element znajduj(cid:200)cy si(cid:218) na szczycie stosu. Metoda isEmpty umo(cid:285)liwia sprawdzenie, czy stos jest pusty. Poniewa(cid:285) korzystamy z j(cid:218)zyka PHP 7, u(cid:285)ywamy tu zarówno deklaracji typów skalarnych na poziomie metod, jak i typów warto(cid:258)ci zwracanych przez metody. Aby skorzysta(cid:202) z naszej zaimplementowanej w(cid:239)a(cid:258)nie klasy, musimy pomy(cid:258)le(cid:202) o przyk(cid:239)adzie, w którym mogliby(cid:258)my u(cid:285)y(cid:202) wszystkich zdefiniowanych dla niej operacji. Napiszmy niewielki program odwzorowuj(cid:200)cy stos ksi(cid:200)(cid:285)ek. Oto jego kod: try { $programmingBooks = new Books(10); $programmingBooks- push( Wprowadzenie do PHP7 ); 86 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek $programmingBooks- push( Mistrzowski JavaScript ); $programmingBooks- push( Samouczek MySQL Workbench ); echo $programmingBooks- pop(). \n ; echo $programmingBooks- top(). \n ; } catch (Exception $e) { echo $e- getMessage(); } Utworzyli(cid:258)my tu instancj(cid:218) stosu ksi(cid:200)(cid:285)ek, w której b(cid:218)dziemy przechowywa(cid:202) tytu(cid:239)y naszych ksi(cid:200)(cid:285)ek programistycznych. Wykonali(cid:258)my te(cid:285) trzy operacje od(cid:239)o(cid:285)enia elementu na stos. Ostatni(cid:200) umieszczon(cid:200) na nim ksi(cid:200)(cid:285)k(cid:200) by(cid:239) Samouczek MySQL Workbench . Gdy po tych trzech operacjach umieszczenia elementu na stosie wykonali(cid:258)my operacj(cid:218) zdj(cid:218)cia z niego elementu, zwrócony zosta(cid:239) ten w(cid:239)a(cid:258)nie tytu(cid:239). Nast(cid:218)puj(cid:200)ce po tym wywo(cid:239)anie metody top zwróci(cid:239)o tytu(cid:239) Mistrzowski JavaScript , który by(cid:239) w tym momencie szczytowym elementem stosu. Ca(cid:239)y kod umie(cid:258)cili(cid:258)my w bloku try...catch, dzi(cid:218)ki czemu mo(cid:285)emy obs(cid:239)u(cid:285)y(cid:202) wyj(cid:200)tek, który mo(cid:285)e zosta(cid:202) zg(cid:239)oszony w momencie wyst(cid:200)pienia przepe(cid:239)nienia lub niedoboru. Wykonanie przed- stawionego powy(cid:285)ej fragmentu kodu powoduje wy(cid:258)wietlenie na ekranie nast(cid:218)puj(cid:200)cych danych wyj(cid:258)ciowych: Samouczek MySQL Workbench Mistrzowski JavaScript Przyjrzyjmy si(cid:218) teraz z(cid:239)o(cid:285)ono(cid:258)ci ró(cid:285)nych operacji na stosie, który przed chwil(cid:200) zaimple- mentowali(cid:258)my. Zrozumienie z(cid:239)o(cid:285)ono(cid:258)ci operacji na stosie Poni(cid:285)ej zosta(cid:239)y zebrane z(cid:239)o(cid:285)ono(cid:258)ci czasowe ró(cid:285)nych operacji na stosie. W najgorszym przy- padku s(cid:200) one nast(cid:218)puj(cid:200)ce: Operacja Z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasowa pop push top isEmpty O(1) O(1) O(1) O(1) Jako (cid:285)e w przypadku stosu operujemy zawsze tylko na jednym ko(cid:241)cu struktury, je(cid:258)li chcemy wyszuka(cid:202) element w stosie, musimy przeszuka(cid:202) ca(cid:239)(cid:200) tworz(cid:200)c(cid:200) go list(cid:218). To samo dotyczy do- st(cid:218)pu do okre(cid:258)lonego elementu nale(cid:285)(cid:200)cego do stosu. Wykonywanie tego typu operacji jest dobr(cid:200) praktyk(cid:200), lecz je(cid:258)li ju(cid:285) koniecznie chcemy je przeprowadza(cid:202), musimy pami(cid:218)ta(cid:202), (cid:285)e ich z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasowa bierze si(cid:218) nie tylko z ogólnych operacji na stosie. 87 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych Operacja Z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasowa dost(cid:218)p wyszukiwanie O(n) O(n) Z(cid:239)o(cid:285)ono(cid:258)(cid:202) pami(cid:218)ciowa stosu wynosi zawsze O(n). Jak dot(cid:200)d dowiedzieli(cid:258)my si(cid:218), jak mo(cid:285)na zaimplementowa(cid:202) stos, u(cid:285)ywaj(cid:200)c tablicy PHP oraz wbudowanych w j(cid:218)zyk funkcji array_pop i array_push. Mogliby(cid:258)my jednak zignorowa(cid:202) fakt istnienia tych funkcji i zaimplementowa(cid:202) stos, korzystaj(cid:200)c z operacji wykonywanych na tabli- cy r(cid:218)cznie, mogliby(cid:258)my te(cid:285) u(cid:285)y(cid:202) wbudowanych funkcji array_shift oraz array_unshift. Implementacja stosu za pomoc(cid:200) listy W rozdziale 3. pt. „U(cid:285)ywanie list” dowiedzieli(cid:258)my si(cid:218), jak tworzy(cid:202) listy. Przekonali(cid:258)my si(cid:218), (cid:285)e korzystaj(cid:200)c z listy, mo(cid:285)emy wstawia(cid:202) w(cid:218)z(cid:239)y na jej ko(cid:241)cu, usuwa(cid:202) je z tego ko(cid:241)ca, wstawia(cid:202) w (cid:258)rodku listy i na jej pocz(cid:200)tku itd. Je(cid:258)li we(cid:283)miemy pod uwag(cid:218) jedynie operacje wstawiania elementów na ko(cid:241)cu listy oraz usuwanie ich z jej ko(cid:241)ca, b(cid:218)dziemy mieli do czynienia ze struktur(cid:200) danych przypominaj(cid:200)c(cid:200) stos. U(cid:285)yjmy zatem opracowanej w poprzednim rozdziale klasy LinkedList, aby zaimplementowa(cid:202) stos. Oto odpowiedni kod: class BookList implements Stack { private $stack; public function __construct() { $this- stack = new LinkedList(); } public function pop(): string { if ($this- isEmpty()) { throw new UnderflowException( Stos jest pusty ); } else { $lastItem = $this- top(); $this- stack- deleteLast(); return $lastItem; } } public function push(string $newItem) { $this- stack- insert($newItem); } 88 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek public function top(): string { return $this- stack- getNthNode($this- stack- getSize())- data; } public function isEmpty(): bool { return $this- stack- getSize() == 0; } } Przeanalizujmy ka(cid:285)dy blok kodu tworz(cid:200)cego nasz(cid:200) now(cid:200) klas(cid:218), aby zrozumie(cid:202), co si(cid:218) w niej dzieje. Je(cid:258)li zaczniemy od pocz(cid:200)tku, zauwa(cid:285)ymy, (cid:285)e w metodzie __construct tworzony jest nowy obiekt klasy LinkedList i (cid:285)e jest on (zamiast tablicy, jak to by(cid:239)o w naszym poprzednim przyk(cid:239)adzie) przypisywany do w(cid:239)a(cid:258)ciwo(cid:258)ci $stack. Zak(cid:239)adamy tu, (cid:285)e klasa LinkedList zostaje za(cid:239)adowana automatycznie lub te(cid:285) odpowiedni plik jest w(cid:239)(cid:200)czony do skryptu. Skupmy si(cid:218) te- raz na operacji odk(cid:239)adania elementu na stos, która jest naprawd(cid:218) prosta. Musimy w jej przy- padku po prostu wstawi(cid:202) nowy w(cid:218)ze(cid:239) na list(cid:218). Jako (cid:285)e nie istniej(cid:200) (cid:285)adne ograniczenia dotycz(cid:200)ce d(cid:239)ugo(cid:258)ci listy, nie sprawdzamy tu przepe(cid:239)nienia. W naszej implementacji listy nie by(cid:239)o metody odpowiedzialnej za zwracanie ostatniego w(cid:218)z(cid:239)a. Mieli(cid:258)my mo(cid:285)liwo(cid:258)(cid:202) wstawienia ostatniego elementu i usuni(cid:218)cia poprzedniego ostatniego ele- mentu, tutaj jednak potrzebna nam jest metoda, która zwróci nam ostatni w(cid:218)ze(cid:239) bez usuwania go z listy. Aby j(cid:200) opracowa(cid:202), zapewniaj(cid:200)c tym samym mechanizm dzia(cid:239)ania metody top dla naszego stosu, mo(cid:285)emy skorzysta(cid:202) z metod getNthNode oraz getSize nale(cid:285)(cid:200)cych do implementa- cji klasy LinkedList. Mo(cid:285)emy w ten sposób pobra(cid:202) w(cid:218)ze(cid:239). Musimy tu jednak pami(cid:218)ta(cid:202) o tym, (cid:285)e chodzi nam o warto(cid:258)(cid:202) w(cid:218)z(cid:239)a b(cid:218)d(cid:200)c(cid:200) (cid:239)a(cid:241)cuchem znakowym, nie za(cid:258) o ca(cid:239)y obiekt w(cid:218)z(cid:239)a. To w(cid:239)a(cid:258)nie z tego powodu zwracamy warto(cid:258)(cid:202) odpowiedniej w(cid:239)a(cid:258)ciwo(cid:258)ci otrzymanego w(cid:218)z(cid:239)a. Podobnie jak metoda top, metoda pop równie(cid:285) musi zwróci(cid:202) dane ostatniego w(cid:218)z(cid:239)a, ta ostatnia ma go jednak jeszcze usun(cid:200)(cid:202) z listy. Aby wykona(cid:202) te operacje, korzystamy z metody top, a na- st(cid:218)pnie z metody deleteLast nale(cid:285)(cid:200)cej do klasy LinkedList. Teraz uruchommy przyk(cid:239)adowy kod, aby sprawdzi(cid:202) dzia(cid:239)anie zaimplementowanej przed chwil(cid:200) klasy BookList, która ma spe(cid:239)- nia(cid:202) funkcj(cid:218) stosu. Oto odpowiedni kod: try { $programmingBooks = new BookList(); $programmingBooks- push( Wprowadzenie do PHP7 ); $programmingBooks- push( Mistrzowski JavaScript ); $programmingBooks- push( Samouczek MySQL Workbench ); echo $programmingBooks- pop(). \n ; echo $programmingBooks- pop(). \n ; echo $programmingBooks- top(). \n ; } catch (Exception $e) { echo $e- getMessage(); } 89 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych Ten kod wygl(cid:200)da bardzo podobnie do poprzedniego przyk(cid:239)adu, który niedawno uruchomili(cid:258)my, tutaj jednak spróbowali(cid:258)my wykona(cid:202) dwie operacje zdj(cid:218)cia elementu ze stosu oraz jedn(cid:200) opera- cj(cid:218) odczytania danych elementu szczytowego. Dane wyj(cid:258)ciowe maj(cid:200) zatem nast(cid:218)puj(cid:200)c(cid:200) posta(cid:202): Samouczek MySQL Workbench Mistrzowski JavaScript Wprowadzenie do PHP7 Je(cid:258)li znamy podstawow(cid:200) zasad(cid:218) dzia(cid:239)ania stosu oraz sposób, w jaki mo(cid:285)na j(cid:200) zaimplemento- wa(cid:202) w praktyce, do utworzenia stosu mo(cid:285)emy u(cid:285)y(cid:202) tablicy, listy jednokierunkowej lub listy dwukierunkowej. Jako (cid:285)e mieli(cid:258)my si(cid:218) ju(cid:285) okazj(cid:218) pozna(cid:202) implementacj(cid:218) stosu za pomoc(cid:200) ta- blicy i listy jednokierunkowej, przyjrzyjmy si(cid:218) teraz implementacji tej struktury zapewnianej przez SPL, w przypadku której wykorzystywana jest tak naprawd(cid:218) lista dwukierunkowa. U(cid:285)ywanie klasy SplStack nale(cid:285)(cid:200)cej do SPL Je(cid:258)li nie chcemy tworzy(cid:202) od podstaw w(cid:239)asnej wersji stosu, mo(cid:285)emy skorzysta(cid:202) z jego imple- mentacji zapewnianej przez SPL. U(cid:285)ywa si(cid:218) jej bardzo (cid:239)atwo i wymaga ona napisania tylko nie- wielkiej ilo(cid:258)ci kodu. Jak ju(cid:285) wiemy, klasa SplStack korzysta z klasy SplDoublyLinkedList. Oferuje wszelkie niezb(cid:218)dne operacje, takie jak odk(cid:239)adanie elementu na stos, zdejmowanie go, prze- suwanie do przodu oraz do ty(cid:239)u itd. Aby opracowa(cid:202) przyk(cid:239)ad podobny do przedstawionego wcze(cid:258)niej, musimy tylko napisa(cid:202) nast(cid:218)puj(cid:200)ce wiersze kodu: $books = new SplStack(); $books- push( Wprowadzenie do PHP7 ); $books- push( Mistrzowski JavaScript ); $books- push( Samouczek MySQL Workbench ); echo $books- pop() . \n ; echo $books- top() . \n ; To prawda, (cid:285)e stos najpro(cid:258)ciej jest zbudowa(cid:202), korzystaj(cid:200)c z klasy SplStack. Mo(cid:285)emy jednak równie dobrze zaimplementowa(cid:202) go samodzielnie, u(cid:285)ywaj(cid:200)c tablicy PHP lub listy, a wybór rozwi(cid:200)zania zale(cid:285)y wy(cid:239)(cid:200)cznie od nas. Rzeczywiste zastosowanie stosu Stos ma wiele zastosowa(cid:241) w nowoczesnych aplikacjach i jest u(cid:285)ywany niemal wsz(cid:218)dzie, czego przyk(cid:239)adami mog(cid:200) by(cid:202) historia odwiedzanych stron przechowywana przez przegl(cid:200)dark(cid:218) in- ternetow(cid:200) oraz powszechnie wykorzystywany w (cid:258)rodowisku programistów (cid:258)lad stosu. Korzy- staj(cid:200)c ze stosu, spróbujemy teraz rozwi(cid:200)za(cid:202) pewien realny problem. 90 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek Dopasowywanie zagnie(cid:285)d(cid:285)onych nawiasów Pierwsz(cid:200) czynno(cid:258)ci(cid:200), któr(cid:200) musimy wykona(cid:202) przy rozwi(cid:200)zywaniu równa(cid:241) lub obliczaniu warto(cid:258)ci wyra(cid:285)e(cid:241) matematycznych, jest sprawdzenie poprawno(cid:258)ci zagnie(cid:285)d(cid:285)onych nawiasów. Je(cid:258)li nie s(cid:200) one zagnie(cid:285)d(cid:285)one prawid(cid:239)owo, wówczas oblicze(cid:241) mo(cid:285)e nie da(cid:202) si(cid:218) wykona(cid:202) lub ich wynik mo(cid:285)e by(cid:202) nieprawid(cid:239)owy. Przyjrzyjmy si(cid:218) kilku przyk(cid:239)adom: 8 * (9 -2) + { (4 * 5) / ( 2 * 2) } 5 * 8 * 9 / ( 3 * 2 ) ) [{ (2 * 7) + ( 15 - 3) ] Z przedstawionych tu wyra(cid:285)e(cid:241) tylko pierwsze jest poprawne; pozosta(cid:239)e dwa s(cid:200) nieprawid(cid:239)owe, poniewa(cid:285) nawiasy nie s(cid:200) w nich zagnie(cid:285)d(cid:285)one prawid(cid:239)owo. Aby stwierdzi(cid:202), czy nawiasy s(cid:200) po- prawnie zagnie(cid:285)d(cid:285)one, mo(cid:285)emy opracowa(cid:202) rozwi(cid:200)zanie wykorzystuj(cid:200)ce stos. Oto pseudokod opisuj(cid:200)cy algorytm takiego rozwi(cid:200)zania: valid = true s = empty stack for (each character of the string) { if(character = ( or { or [ ) s.push(character) else if (character = ) or } or ] ) { if(s is empty) valid = false last = s.pop() if(last is not opening parentheses of character) valid = false } } if(s is not empty) valid = false Je(cid:258)li przyjrzymy si(cid:218) temu pseudokodowi, oka(cid:285)e si(cid:218) on do(cid:258)(cid:202) nieskomplikowany. Jego dzia(cid:239)anie polega na tym, aby ignorowa(cid:202) wszelkie liczby, operandy i puste znaki wyst(cid:218)puj(cid:200)ce w (cid:239)a(cid:241)cu- chu tekstowym i bra(cid:202) pod uwag(cid:218) wy(cid:239)(cid:200)cznie nawiasy okr(cid:200)g(cid:239)e, klamrowe oraz kwadratowe. Je(cid:258)li w (cid:239)a(cid:241)cuchu pojawiaj(cid:200) si(cid:218) jakie(cid:258) nawiasy otwieraj(cid:200)ce, umieszczamy je na stosie. Je(cid:258)li wy- st(cid:218)puj(cid:200) tam nawiasy zamykaj(cid:200)ce, zdejmujemy elementy ze stosu. Je(cid:258)li nawias zdj(cid:218)ty ze stosu nie jest nawiasem otwieraj(cid:200)cym, który pasuje do znalezionego nawiasu zamykaj(cid:200)cego, wów- czas wyra(cid:285)enie jest niepoprawne. Je(cid:258)li (cid:239)a(cid:241)cuch jest prawid(cid:239)owy, na ko(cid:241)cu p(cid:218)tli stos powinien by(cid:202) pusty. Je(cid:258)li nie jest, to mamy jakie(cid:258) nadmiarowe nawiasy, a zatem wyra(cid:285)enie jest niepra- wid(cid:239)owe. Przekszta(cid:239)(cid:202)my teraz ten algorytm w program: function expressionChecker(string $expression): bool { $valid = TRUE; $stack = new SplStack(); for ($i = 0; $i strlen($expression); $i++) { $char = substr($expression, $i, 1); switch ($char) { 91 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych case ( : case { : case [ : $stack- push($char); break; case ) : case } : case ] : if ($stack- isEmpty()) { $valid = FALSE; } else { $last = $stack- pop(); if (($char == ) $last != ( ) || ($char == } $last != { ) (cid:180)|| ($char == ] $last != [ )) { $valid = FALSE; } } break; } if (!$valid) break; } if (!$stack- isEmpty()) { $valid = FALSE; } return $valid; } Uruchommy teraz t(cid:218) funkcj(cid:218), podaj(cid:200)c jej trzy przedstawione wcze(cid:258)niej wyra(cid:285)enia: $expressions = []; $expressions[] = 8 * (9 -2) + { (4 * 5) / ( 2 * 2) } ; $expressions[] = 5 * 8 * 9 / ( 3 * 2 ) ) ; $expressions[] = [{ (2 * 7) + ( 15 - 3) ] ; foreach ($expressions as $expression) { $valid = expressionChecker($expression); if ($valid) { echo Wyra(cid:285)enie jest prawid(cid:239)owe \n ; } else { echo Wyra(cid:285)enie jest nieprawid(cid:239)owe \n ; } } Wykonanie tego fragmentu kodu spowoduje wy(cid:258)wietlenie na ekranie nast(cid:218)puj(cid:200)cych danych wyj(cid:258)ciowych, które s(cid:200) w stu procentach zgodne z naszymi oczekiwaniami: Wyra(cid:285)enie jest prawid(cid:239)owe Wyra(cid:285)enie jest nieprawid(cid:239)owe Wyra(cid:285)enie jest nieprawid(cid:239)owe 92 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek Zrozumienie kolejki Kolejka to nast(cid:218)pna specjalna, liniowa struktura danych, dzia(cid:239)aj(cid:200)ca jednak zgodnie z zasad(cid:200) pierwszy na wej(cid:258)ciu, pierwszy na wyj(cid:258)ciu (ang. First-In, First-Out — FIFO). Operacje od- bywaj(cid:200) si(cid:218) na dwóch ko(cid:241)cach kolejki: jeden z nich s(cid:239)u(cid:285)y do dodawania elementów, a drugi do usuwania. Odró(cid:285)nia to kolejk(cid:218) od stosu, w przypadku którego obydwa te dzia(cid:239)ania odbywa(cid:239)y si(cid:218) tylko na jednym ko(cid:241)cu. Wstawianie elementów do kolejki odbywa si(cid:218) zawsze z ty(cid:239)u lub na ko(cid:241)cu kolejki. Usuwanie elementów przeprowadza si(cid:218) na jej pocz(cid:200)tku czy te(cid:285) z przodu. Ope- racja dodawania nowego elementu do kolejki znana jest jako zakolejkowanie (ang. enqueue), a operacj(cid:218) usuwania mo(cid:285)na okre(cid:258)li(cid:202) s(cid:239)owem „wykolejkowanie”, „zdekolejkowanie” lub po prostu jako obs(cid:239)ug(cid:218) elementu (ang. dequeue). Pobieranie elementu znajduj(cid:200)cego si(cid:218) na po- cz(cid:200)tku kolejki bez usuwania go znane jest jako zerkanie lub podgl(cid:200)danie (ang. peek) i stanowi operacj(cid:218) analogiczn(cid:200) do operacji wykonywanej na stosie przez metod(cid:218) top. Sposób dzia(cid:239)ania kolejki zosta(cid:239) przedstawiony na rysunku poni(cid:285)ej. Interfejs kolejki powinien mie(cid:202) nast(cid:218)puj(cid:200)c(cid:200) definicj(cid:218): interface Queue { public function enqueue(string $item); public function dequeue(); public function peek(); public function isEmpty(); } Podobnie jak to by(cid:239)o w przypadku stosu, kolejk(cid:218) mo(cid:285)emy zaimplementowa(cid:202) na ró(cid:285)ne sposo- by. Najpierw zrealizujemy j(cid:200) za pomoc(cid:200) tablicy PHP, nast(cid:218)pnie przy u(cid:285)yciu klasy LinkedList, a na koniec — korzystaj(cid:200)c z klasy SplQueue. 93 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych Implementacja kolejki za pomoc(cid:200) tablicy PHP Teraz zajmiemy si(cid:218) implementacj(cid:200) kolejki przy u(cid:285)yciu tablicy PHP. Wiemy ju(cid:285), (cid:285)e mo(cid:285)emy zastosowa(cid:202) funkcj(cid:218) array_push w celu dodania elementu na ko(cid:241)cu tablicy. Aby usun(cid:200)(cid:202) jej pierwszy element, mo(cid:285)na skorzysta(cid:202) z funkcji array_shift zapewnianej przez PHP. Pierwszy element kolejki da si(cid:218) podejrze(cid:202) za pomoc(cid:200) funkcji current. W zwi(cid:200)zku z powy(cid:285)szym kod na- szej kolejki mo(cid:285)e wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: class AgentQueue implements Queue { private $limit; private $queue; public function __construct(int $limit = 20) { $this- limit = $limit; $this- queue = []; } public function dequeue(): string { if ($this- isEmpty()) { throw new UnderflowException( Kolejka jest pusta ); } else { return array_shift($this- queue); } } public function enqueue(string $newItem) { if (count($this- queue) $this- limit) { array_push($this- queue, $newItem); } else { throw new OverflowException( Kolejka jest pe(cid:239)na ); } } public function peek(): string { return current($this- queue); } public function isEmpty(): bool { return empty($this- queue); } } Kierujemy si(cid:218) tu t(cid:200) sam(cid:200) regu(cid:239)(cid:200), zgodnie z któr(cid:200) post(cid:218)powali(cid:258)my, tworz(cid:200)c nasz stos. Definiu- jemy zatem kolejk(cid:218) o sta(cid:239)ej wielko(cid:258)ci (czy te(cid:285) d(cid:239)ugo(cid:258)ci), sprawdzaj(cid:200)c, czy nie mamy do czy- nienia z przepe(cid:239)nieniem lub niedoborem. W celu sprawdzenia naszej implementacji kolejki utwórzmy kolejk(cid:218) agentów telefonicznego centrum obs(cid:239)ugi. Oto kod, w którym przeprowa- dzane s(cid:200) poszczególne operacje na kolejce: 94 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek try { $agents = new AgentQueue(10); $agents- enqueue( Franek ); $agents- enqueue( Janek ); $agents- enqueue( Krzysiek ); $agents- enqueue( Adrian ); $agents- enqueue( Micha(cid:239) ); echo $agents- dequeue(). \n ; echo $agents- dequeue(). \n ; echo $agents- peek(). \n ; } catch (Exception $e) { echo $e- getMessage(); } W wyniku wykonania tego kodu na ekranie pojawi(cid:200) si(cid:218) nast(cid:218)puj(cid:200)ce dane wyj(cid:258)ciowe: Franek Janek Krzysiek Implementacja kolejki za pomoc(cid:200) listy Tak jak to by(cid:239)o w przypadku stosu, równie(cid:285) tutaj do opracowania kolejki zamierzamy u(cid:285)y(cid:202) na- szej implementacji listy zaprezentowanej w rozdziale 3. pt. „U(cid:285)ywanie list”. Mo(cid:285)emy tu u(cid:285)y(cid:202) metody insert do wstawiania elementów zawsze na ko(cid:241)cu kolejki, metody deleteFirst, aby obs(cid:239)u(cid:285)y(cid:202) operacj(cid:218) usuwania elementów z kolejki, za(cid:258) metody getNthNode do podgl(cid:200)dania pierw- szego elementu. Oto przyk(cid:239)adowa implementacja kolejki przy u(cid:285)yciu listy jednokierunkowej: class AgentQueue implements Queue { private $limit; private $queue; public function __construct(int $limit = 20) { $this- limit = $limit; $this- queue = new LinkedList(); } public function dequeue(): string { if ($this- isEmpty()) { throw new UnderflowException( Kolejka jest pusta ); } else { $lastItem = $this- peek(); $this- queue- deleteFirst(); return $lastItem; } } 95 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych public function enqueue(string $newItem) { if ($this- queue- getSize() $this- limit) { $this- queue- insert($newItem); } else { throw new OverflowException( Kolejka jest pe(cid:239)na ); } } public function peek(): string { return $this- queue- getNthNode(1)- data; } public function isEmpty(): bool { return $this- queue- getSize() == 0; } } U(cid:285)ywanie klasy SplQueue nale(cid:285)(cid:200)cej do SPL Je(cid:258)li nie chcemy m(cid:218)czy(cid:202) si(cid:218) implementacj(cid:200) funkcji kolejki i nie mamy problemu z zastosowa- niem rozwi(cid:200)zania oferowanego przez bibliotek(cid:218) standardow(cid:200), mo(cid:285)emy u(cid:285)y(cid:202) klasy SplQueue do zaspokojenia naszych podstawowych potrzeb zwi(cid:200)zanych z tego rodzaju struktur(cid:200) danych. Musimy tylko pami(cid:218)ta(cid:202) o jednym: klasa SplQueue nie zapewnia funkcji podgl(cid:200)dania warto(cid:258)ci pierwszego elementu kolejki. Z tego powodu powinni(cid:258)my skorzysta(cid:202) z funkcji bottom w celu uzyskania pierwszego elementu kolejki. Oto prosta wykorzystuj(cid:200)ca obiekt klasy SplQueue im- plementacja kolejki reprezentuj(cid:200)cej przedstawiony wcze(cid:258)niej przyk(cid:239)ad AgentQueue: $agents = new SplQueue(); $agents- enqueue( Franek ); $agents- enqueue( Janek ); $agents- enqueue( Krzysiek ); $agents- enqueue( Adrian ); $agents- enqueue( Micha(cid:239) ); echo $agents- dequeue(). \n ; echo $agents- dequeue(). \n ; echo $agents- bottom(). \n ; Zrozumienie kolejki priorytetowej Kolejka priorytetowa (ang. priority queue) to specjalny rodzaj kolejki, w przypadku której elementy s(cid:200) wstawiane i usuwane zgodnie z priorytetem. W (cid:258)wiecie programowania kompu- terowego zastosowanie kolejki priorytetowej jest ogromne. Powiedzmy, (cid:285)e mamy bardzo du(cid:285)y system kolejkowania wiadomo(cid:258)ci poczty elektronicznej, który wykorzystujemy do rozsy(cid:239)ania 96 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek comiesi(cid:218)cznego biuletynu. Co gdy zachodzi potrzeba rozes(cid:239)ania do u(cid:285)ytkowników jakiej(cid:258) nie- zwykle pilnej wiadomo(cid:258)ci za pomoc(cid:200) tego systemu? Jako (cid:285)e zgodnie z ogóln(cid:200) zasad(cid:200) dzia(cid:239)ania kolejek ka(cid:285)dy element dodaje si(cid:218) na jej ko(cid:241)cu, dor(cid:218)czenie naszej wiadomo(cid:258)ci b(cid:218)dzie bardzo mocno opó(cid:283)nione. Aby rozwi(cid:200)za(cid:202) ten problem, mo(cid:285)emy skorzysta(cid:202) z kolejki priorytetowej. W takim przypadku do ka(cid:285)dego w(cid:218)z(cid:239)a przypisuje si(cid:218) pewien priorytet i wszystkie w(cid:218)z(cid:239)y sortuje si(cid:218) zgodnie z ich priorytetami. Element o wy(cid:285)szym priorytecie zostanie przeniesiony na pocz(cid:200)tek listy, w zwi(cid:200)zku z czym zostanie on obs(cid:239)u(cid:285)ony wcze(cid:258)niej ni(cid:285) w(cid:218)z(cid:239)y o ni(cid:285)szych priorytetach. Kolejk(cid:218) priorytetow(cid:200) mo(cid:285)na zbudowa(cid:202) na dwa sposoby. Sekwencja uporz(cid:200)dkowana Je(cid:258)li implementuj(cid:200)c kolejk(cid:218) priorytetow(cid:200), zdecydowali(cid:258)my si(cid:218) u(cid:285)y(cid:202) sekwencji uporz(cid:200)dkowa- nej (ang. ordered sequence), mo(cid:285)emy w jej przypadku zastosowa(cid:202) porz(cid:200)dek rosn(cid:200)cy lub ma- lej(cid:200)cy. Dobr(cid:200) stron(cid:200) korzystania z tego rodzaju sekwencji jest to, (cid:285)e mo(cid:285)emy szybko w niej znale(cid:283)(cid:202) lub z niej usun(cid:200)(cid:202) element o najwy(cid:285)szym priorytecie; z(cid:239)o(cid:285)ono(cid:258)(cid:202) tego rodzaju operacji wynosi zaledwie O(1). Wi(cid:218)cej czasu zajmie jednak wstawianie elementu, poniewa(cid:285) b(cid:218)dzie ono wymaga(cid:239)o sprawdzenia ka(cid:285)dego elementu kolejki w celu umieszczenia nowego w(cid:218)z(cid:239)a w miejscu odpowiednim ze wzgl(cid:218)du na jego priorytet. Sekwencja nieuporz(cid:200)dkowana Zastosowanie sekwencji nieuporz(cid:200)dkowanej (ang. unordered sequence) nie zmusza nas do przechodzenia przez ka(cid:285)dy element kolejki w celu umieszczenia w niej nowo dodanego ele- mentu. Dodaje si(cid:218) go do ko(cid:241)ca kolejki, zgodnie z ogóln(cid:200) zasad(cid:200) dzia(cid:239)ania kolejek. Dzi(cid:218)ki temu z(cid:239)o(cid:285)ono(cid:258)(cid:202) operacji kolejkowania wynosi O(1). Je(cid:258)li jednak chcemy wyszuka(cid:202) lub usun(cid:200)(cid:202) element o najwy(cid:285)szym priorytecie, musimy przej(cid:258)(cid:202) przez ka(cid:285)dy element kolejki, aby znale(cid:283)(cid:202) w(cid:239)a(cid:258)ciwy w(cid:218)ze(cid:239). Co za tym idzie, rozwi(cid:200)zanie to nie jest najlepsze, gdy chodzi o operacje wyszukiwania. Teraz zajmiemy si(cid:218) pisaniem kodu implementuj(cid:200)cego kolejk(cid:218) priorytetow(cid:200) przy u(cid:285)yciu upo- rz(cid:200)dkowanej sekwencji realizowanej za pomoc(cid:200) listy. Implementacja kolejki priorytetowej za pomoc(cid:200) listy Jak dot(cid:200)d listy, z którymi mieli(cid:258)my do czynienia, w ka(cid:285)dym swoim w(cid:218)(cid:283)le przechowywa(cid:239)y tyl- ko jedn(cid:200) warto(cid:258)(cid:202) stanowi(cid:200)c(cid:200) dane w(cid:218)z(cid:239)a. Teraz zachodzi potrzeba zapisania innej warto(cid:258)ci, która okre(cid:258)la priorytet. Aby to osi(cid:200)gn(cid:200)(cid:202), musimy zmieni(cid:202) implementacj(cid:218) naszej klasy ListNode w nast(cid:218)puj(cid:200)cy sposób: 97 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych class ListNode { public $data = NULL; public $next = NULL; public $priority = NULL; public function __construct(string $data = NULL, int $priority = NULL) { $this- data = $data; $this- priority = $priority; } } Dzi(cid:218)ki temu zarówno dane, jak i priorytet stanowi(cid:200) teraz elementy sk(cid:239)adowe naszego w(cid:218)z(cid:239)a. Aby uwzgl(cid:218)dnia(cid:202) priorytet podczas wstawiania nowych w(cid:218)z(cid:239)ów, musimy równie(cid:285) zmieni(cid:202) implementacj(cid:218) metody insert nale(cid:285)(cid:200)cej do klasy LinkedList. Oto zmodyfikowany kod: public function insert(string $data = NULL, int $priority = NULL) { $newNode = new ListNode($data, $priority); $this- _totalNode++; if ($this- _firstNode === NULL) { $this- _firstNode = $newNode; } else { $previous = $this- _firstNode; $currentNode = $this- _firstNode; while ($currentNode !== NULL) { if ($currentNode- priority $priority) { if ($currentNode == $this- _firstNode) { $previous = $this- _firstNode; $this- _firstNode = $newNode; $newNode- next = $previous; return; } $newNode- next = $currentNode; $previous- next = $newNode; return; } $previous = $currentNode; $currentNode = $currentNode- next; } } return TRUE; } Jak wida(cid:202), nasza metoda insert zosta(cid:239)a zmieniona w taki sposób, aby przyjmowa(cid:202) w roli ar- gumentów zarówno dane, jak i priorytet, a tak(cid:285)e aby uwzgl(cid:218)dnia(cid:202) je w czasie realizowania ope- racji. Jak zwykle pierwszym dzia(cid:239)aniem jest tu utworzenie nowego w(cid:218)z(cid:239)a i zinkrementowanie licznika w(cid:218)z(cid:239)ów. Przy wstawianiu istniej(cid:200) trzy mo(cid:285)liwe sytuacje: 98 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek (cid:81) Lista jest pusta, dlatego nowy w(cid:218)ze(cid:239) staje si(cid:218) pierwszym w(cid:218)z(cid:239)em listy. (cid:81) Lista nie jest pusta, ale nowy element ma najwy(cid:285)szy priorytet, dlatego staje si(cid:218) pierwszym w(cid:218)z(cid:239)em, a element, który wcze(cid:258)niej nim by(cid:239), znajduje si(cid:218) po nowo wstawionym. (cid:81) Lista nie jest pusta, a nowy element nie ma najwy(cid:285)szego priorytetu, dlatego zostaje wstawiony gdzie(cid:258) w (cid:258)rodku listy, a by(cid:202) mo(cid:285)e na jej ko(cid:241)cu. Tworz(cid:200)c nasz(cid:200) implementacj(cid:218), uwzgl(cid:218)dnili(cid:258)my wszystkie te trzy przypadki. Dzi(cid:218)ki temu ele- ment o najwy(cid:285)szym priorytecie mamy zawsze na pocz(cid:200)tku kolejki. Uruchommy teraz przy- k(cid:239)ad z kolejk(cid:200) AgentQueue zbudowan(cid:200) na bazie naszego nowego kodu, tak jak zosta(cid:239)o to poka- zane poni(cid:285)ej. try { $agents = new AgentQueue(10); $agents- enqueue( Franek , 1); $agents- enqueue( Janek , 2); $agents- enqueue( Krzysiek , 3); $agents- enqueue( Adrian , 4); $agents- enqueue( Micha(cid:239) , 2); $agents- display(); echo $agents- dequeue(). \n ; echo $agents- dequeue(). \n ; } catch (Exception $e) { echo $e- getMessage(); } Gdyby(cid:258)my nie korzystali z priorytetów, wówczas nasza kolejka powinna zawiera(cid:202) elementy u(cid:239)o(cid:285)one w nast(cid:218)puj(cid:200)cym porz(cid:200)dku: Franek, Janek, Krzysiek, Adrian i Micha(cid:239). Poniewa(cid:285) jednak dodali(cid:258)my priorytety, dane wyj(cid:258)ciowe wygl(cid:200)daj(cid:200) jak ni(cid:285)ej. Adrian Krzysiek Janek Micha(cid:239) Franek Jako (cid:285)e element Adrian ma najwy(cid:285)szy priorytet, jest umieszczony na pocz(cid:200)tku kolejki, cho(cid:202) zosta(cid:239) do niej wstawiony jako czwarty. Implementacja kolejki priorytetowej za pomoc(cid:200) klasy SplPriorityQueue J(cid:218)zyk PHP zapewnia wsparcie dla implementacji kolejki priorytetowej za pomoc(cid:200) SPL. Do utworzenia tego rodzaju struktury danych mo(cid:285)emy wykorzysta(cid:202) klas(cid:218) SplPriorityQueue. Oto ta sama kolejka, któr(cid:200) implementowali(cid:258)my w poprzednim przyk(cid:239)adzie za pomoc(cid:200) listy, zrealizowana jednak tym razem przy u(cid:285)yciu rozwi(cid:200)zania zapewnianego przez SPL: 99 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych class MyPQ extends SplPriorityQueue { public function compare($priority1, $priority2) { return $priority1 = $priority2; } } $agents = new MyPQ(); $agents- insert( Franek , 1); $agents- insert( Janek , 2); $agents- insert( Krzysiek , 3); $agents- insert( Adrian , 4); $agents- insert( Micha(cid:239) , 2); // Tryb ekstrakcji $agents- setExtractFlags(MyPQ::EXTR_BOTH); // Przej(cid:286)cie do SZCZYTU $agents- top(); while ($agents- valid()) { $current = $agents- current(); echo $current[ dane ] . \n ; $agents- next(); } Przedstawiony powy(cid:285)ej kod wygeneruje te same dane wyj(cid:258)ciowe co przyk(cid:239)ad wykorzystuj(cid:200)cy list(cid:218). Dodatkow(cid:200) przewag(cid:200) rozwi(cid:200)zania polegaj(cid:200)cego na u(cid:285)yciu klasy MyPQ rozszerzaj(cid:200)cej klas(cid:218) SplPriorityQueue jest to, (cid:285)e mo(cid:285)emy tu wybra(cid:202) sposób sortowania elementów (tj. to, czy maj(cid:200) by(cid:202) one u(cid:239)o(cid:285)one w kolejno(cid:258)ci rosn(cid:200)cej, czy te(cid:285) malej(cid:200)cej). W tym przyk(cid:239)adzie wybrali(cid:258)my po- rz(cid:200)dek malej(cid:200)cy, korzystaj(cid:200)c z dost(cid:218)pnego w PHP operatora po(cid:239)(cid:200)czonego porównania, zwa- nego ze wzgl(cid:218)du na swój wygl(cid:200)d operatorem statku kosmicznego (ang. spaceship operator). Kolejki priorytetowe s(cid:200) zwykle implementowane za pomoc(cid:200) sterty. Gdy przejdziemy do rozdzia(cid:239)u po(cid:258)wi(cid:218)- conego stercie, zajmiemy si(cid:218) równie(cid:285) implementacj(cid:200) kolejki priorytetowej przy u(cid:285)yciu tej struktury danych. Implementacja kolejki cyklicznej Korzystaj(cid:200)c ze standardowej kolejki, za ka(cid:285)dym razem gdy usuwamy z niej element, musimy odpowiednio przesun(cid:200)(cid:202) ca(cid:239)(cid:200) kolejk(cid:218). Aby rozwi(cid:200)za(cid:202) ten problem, mo(cid:285)emy skorzysta(cid:202) z kolej- ki cyklicznej (ang. circular queue), w której po ko(cid:241)cu nast(cid:218)puje pocz(cid:200)tek, dzi(cid:218)ki czemu po- wstaje ko(cid:239)o czy te(cid:285) cykl. Ten szczególny typ kolejki wymaga specjalnych oblicze(cid:241) wykonywanych przy operacjach dodawania elementu do kolejki i usuwania elementu z kolejki, a zwi(cid:200)zanych 100 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek z jej ko(cid:241)cem, pocz(cid:200)tkiem oraz wielko(cid:258)ci(cid:200). Kolejki cykliczne maj(cid:200) zawsze sta(cid:239)y rozmiar i znane s(cid:200) tak(cid:285)e jako bufory cykliczne (ang. circular buffers) lub bufory pier(cid:258)cieniowe (ang. ring buffers). Na zamieszczonym poni(cid:285)ej rysunku przedstawiony zosta(cid:239) schemat dzia(cid:239)ania kolejki cyklicznej. Kolejk(cid:218) cykliczn(cid:200) mo(cid:285)na zaimplementowa(cid:202) za pomoc(cid:200) tablicy PHP. Mo(cid:285)e ona by(cid:202) w tym celu wydajnie wykorzystana, poniewa(cid:285) musimy tu obliczy(cid:202) pozycje ko(cid:241)ca i pocz(cid:200)tku kolejki. Oto przyk(cid:239)ad kolejki cyklicznej: class CircularQueue implements Queue { private $queue; private $limit; private $front = 0; private $rear = 0; public function __construct(int $limit = 5) { $this- limit = $limit; $this- queue = []; } public function size() { if ($this- rear $this- front) return $this- rear - $this- front; return $this- limit - $this- front + $this- rear; } public function isEmpty() { return $this- rear == $this- front; } public function isFull() { $diff = $this- rear - $this- front; if ($diff == -1 || $diff == ($this- limit - 1)) return true; return false; } 101 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych public function enqueue(string $item) { if ($this- isFull()) { throw new OverflowException( Kolejka jest pe(cid:239)na. ); } else { $this- queue[$this- rear] = $item; $this- rear = ($this- rear + 1) $this- limit; } } public function dequeue() { $item = ; if ($this- isEmpty()) { throw new UnderflowException( Kolejka jest pusta ); } else { $item = $this- queue[$this- front]; $this- queue[$this- front] = NULL; $this- front = ($this- front + 1) $this- limit; } return $item; } public function peek() { return $this- queue[$this- front]; } } Poniewa(cid:285) uznajemy 0 za znacznik pocz(cid:200)tku kolejki, jej ca(cid:239)kowity rozmiar b(cid:218)dzie wynosi(cid:239) limit -1. Tworzenie kolejki dwustronnej Do tej pory implementowali(cid:258)my kolejki, których jedna strona, okre(cid:258)lana jako koniec lub ty(cid:239) (ang. rear), u(cid:285)ywana by(cid:239)a do dodawania elementów, za(cid:258) druga, znana jako pocz(cid:200)tek lub przód (ang. front), umo(cid:285)liwia(cid:239)a usuwanie elementów. Ogólnie rzecz bior(cid:200)c, ka(cid:285)da strona kolejki po- winna by(cid:202) zatem wykorzystywana w konkretnym celu. Co jednak, gdyby(cid:258)my chcieli dodawa(cid:202) i usuwa(cid:202) elementy z obu stron kolejki? Da si(cid:218) to zrobi(cid:202) za pomoc(cid:200) tzw. kolejki dwustronnej, okre(cid:258)lanej te(cid:285) jako kolejka podwójna (ang. double-ended queue, deque). W kolejce takiej oby- dwie strony mog(cid:200) by(cid:202) u(cid:285)ywane do operacji dodawania i usuwania w(cid:218)z(cid:239)ów. Je(cid:258)li spojrzymy na nasz(cid:200) implementacj(cid:218) kolejki wykorzystuj(cid:200)c(cid:200) list(cid:218), przekonamy si(cid:218), (cid:285)e mo(cid:285)na w jej przypadku wstawia(cid:202) element na pierwszym i na ostatnim miejscu oraz usuwa(cid:202) element z pierwszego i ostatniego miejsca. Tworz(cid:200)c now(cid:200) klas(cid:218) kolejki dwustronnej z wykorzystaniem tych mo(cid:285)li- wo(cid:258)ci, mo(cid:285)emy (cid:239)atwo osi(cid:200)gn(cid:200)(cid:202) cel, o który nam chodzi. Sposób dzia(cid:239)ania tego rodzaju kolejki zosta(cid:239) pokazany poni(cid:285)ej. 102 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek Oto implementacja kolejki dwustronnej: class DeQueue { private $limit; private $queue; public function __construct(int $limit = 20) { $this- limit = $limit; $this- queue = new LinkedList(); } public function dequeueFromFront(): string { if ($this- isEmpty()) { throw new UnderflowException( Kolejka jest pusta ); } else { $lastItem = $this- peekFront(); $this- queue- deleteFirst(); return $lastItem; } } public function dequeueFromBack(): string { if ($this- isEmpty()) { throw new UnderflowException( Kolejka jest pusta ); } else { $lastItem = $this- peekBack(); $this- queue- deleteLast(); return $lastItem; } } public function enqueueAtBack(string $newItem) { if ($this- queue- getSize() $this- limit) { $this- queue- insert($newItem); } else { throw new OverflowException( Kolejka jest pe(cid:239)na ); } } public function enqueueAtFront(string $newItem) { if ($this- queue- getSize() $this- limit) { 103 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych $this- queue- insertAtFirst($newItem); } else { throw new OverflowException( Kolejka jest pe(cid:239)na ); } } public function peekFront(): string { return $this- queue- getNthNode(1)- data; } public function peekBack(): string { return $this- queue- getNthNode($this- queue- getSize())- data; } public function isEmpty(): bool { return $this- queue- getSize() == 0; } } Skorzystamy teraz z naszej nowej klasy, aby sprawdzi(cid:202) operacje na kolejce dwustronnej: try { $agents = new DeQueue(10); $agents- enqueueAtFront( Franek ); $agents- enqueueAtFront( Janek ); $agents- enqueueAtBack( Krzysiek ); $agents- enqueueAtBack( Adrian ); $agents- enqueueAtFront( Micha(cid:239) ); echo $agents- dequeueFromBack() . \n ; echo $agents- dequeueFromFront() . \n ; echo $agents- peekFront() . \n ; } catch (Exception $e) { echo $e- getMessage(); } Je(cid:258)li przyjrzymy si(cid:218) temu przyk(cid:239)adowi kodu, zauwa(cid:285)ymy, (cid:285)e najpierw jest w nim dodawany na pocz(cid:200)tku kolejki element Franek, a potem równie(cid:285) na pocz(cid:200)tku element Janek. Sekwencja wygl(cid:200)da zatem teraz nast(cid:218)puj(cid:200)co: Janek, Franek. Nast(cid:218)pnie z ty(cid:239)u kolejki dodajemy element Krzysiek, a potem Adrian. W wyniku tego otrzymujemy sekwencj(cid:218): Janek, Franek, Krzysiek, Adrian. Na samym ko(cid:241)cu kodu dodajemy element Micha(cid:239) na przodzie kolejki. Sekwencja przyj- muje zatem ostatecznie posta(cid:202): Micha(cid:239), Janek, Franek, Krzysiek, Adrian. Jako (cid:285)e usuwanie z kolejki zaczynamy od ty(cid:239)u, pierwszym elementem, który j(cid:200) opuszcza, jest Adrian; nast(cid:218)pnie usuwamy element z przodu — jest nim Micha(cid:239). Operacja podejrzenia ele- mentu znajduj(cid:200)cego si(cid:218) na pocz(cid:200)tku kolejki spowoduje zwrócenie elementu Janek. Oto dane wyj(cid:258)ciowe wygenerowane przez nasz kod po uruchomieniu: Adrian Micha(cid:239) Janek 104 Poleć książkęKup książkę Rozdzia(cid:225) 4. • Konstruowanie stosów i kolejek Podsumowanie Stosy i kolejki s(cid:200) jednymi z najcz(cid:218)(cid:258)ciej u(cid:285)ywanych struktur danych. Z tych abstrakcyjnych typów danych mo(cid:285)emy w przysz(cid:239)o(cid:258)ci korzysta(cid:202) na wiele ró(cid:285)nych sposobów. W tym rozdziale poznali(cid:258)my rozmaite metody implementowania stosów i kolejek, jak równie(cid:285) ró(cid:285)ne rodzaje kolejek. W nast(cid:218)pnym zamierzamy omówi(cid:202) temat rekurencji b(cid:218)d(cid:200)cej szczególnym sposobem rozwi(cid:200)zywania wi(cid:218)kszych problemów poprzez ich podzia(cid:239) na mniejsze jednostki. 105 Poleć książkęKup książkę PHP 7. Algorytmy i struktury danych 106 Poleć książkęKup książkę Skorowidz quicksort, Patrz: algorytm sortowania szybkiego rekurencyjny, 109, 110, 122, 267 z(cid:239)o(cid:285)ono(cid:258)(cid:202), 122, 123 SHA1, 287 SHA256, 287 sortowania, 157 b(cid:200)belkowego, 158, 159, 161, 165 przez scalanie, 172 przez wstawianie, 168 przez wybieranie, 166 szybkiego, 175 z(cid:239)o(cid:285)ono(cid:258)(cid:202), 190 wydajno(cid:258)(cid:202), 33 wyszukiwania binarnego, 133, 147, 185, 187, 188 powtarzalnego, 187 z nawrotami, 249, 267 zach(cid:239)anny, 228, 231, 249, 255, 256, 260 zastosowania, 258, 259 z(cid:239)o(cid:285)ono(cid:258)(cid:202), 34, 35 aplikacja cz(cid:218)(cid:258)ciowa, 301 atak typ brute force, 288 B B-drzewo, 135, 155 Bellmana-Forda algorytm, Patrz: algorytm Bellmana-Forda BFS, 194, 195, 202, 212 grafu, 197, 212, 213 implementacja, 195, 19
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

PHP 7. Algorytmy i struktury danych
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: