Структури на данни: стек и опашка

здрасти Днес ще говорим за нещо, което е супер важно за всеки програмист: структури от данни. Wikipedia казва: „ Структурата от данни е организация на данни, управление и формат за съхранение, който позволява ефективен достъп и модифициране. По-точно, структурата от данни е колекция от стойности на данни, връзките между тях и функциите or операциите, които могат да бъдат приложено към данните." Определението е малко объркващо, но същността му е ясна. Структурата на данните е вид хранorще, където съхраняваме данни за бъдеща употреба. В програмирането има огромно разнообразие от структури от данни. При решаването на конкретни проблеми много често най-важното е да изберете най-подходящата структура от данни за проблема. И вече сте запознати с много от тях! Например, знаете за масивите. И вие също сте запознати сMap(тази структура от данни може също да се нарича "речник" or "асоциативен масив"). Много е важно да се разбере, че структурите от данни не са обвързани с конкретен език. Те са просто абстрактни „чертежи“, които всеки език за програмиране използва, за да създаде свои собствени класове or реализации на определена структура. Например, една от най-известните структури от данни е свързан списък. Можете да отидете в Wikipedia и да прочетете How работи и Howви предимства и недостатъци има. Може би дефиницията му ще ви се стори позната :) "Свързаният списък е линейна колекция от елементи от данни, чийто ред не е даден от физическото им разположение в паметта. Вместо това всеки елемент сочи към следващия." Това описва нашия любим LinkedList, нали? Да, и точно това е :) В Java структурата от данни на "свързания списък" се реализира от LinkedListкласа. Но други езици също прилагат свързани списъци! В Python тази структура от данни се нарича " llist". В Scala се нарича " LinkedList", точно Howто в Java. Свързаният списък е една от основните общи структури от данни, така че ще откриете, че той се прилага във всеки модерен език за програмиране. Същото важи и за асоциативните масиви. Ето дефиницията от Wikipedia: „Асоциативен масив, карта, table със символи or речник е абстрактен тип данни, съставен от колекция от двойки (ключ, стойност), така че всеки възможен ключ се появява най-много веднъж в колекцията.“ Това напомня ли ви за нещо? :) Да. За нас, разработчиците на Java, асоциативният масив еMapинтерфейс. Но тази структура от данни се прилага и на други езици! Например C# програмистите го познават под името "Dictionary". И в Ruby, той е имплементиран в клас, наречен "Hash". Е, разбрахте мисълта: структурите от данни са универсални концепции в програмирането и всеки език за програмиране ги прилага по свой начин. Днес ще проучим две такива структури — стека и опашката — и ще видим How са имплементирани в Java.

Стекове в Java

Стекът е добре позната структура от данни. Много е просто. Доста елементи в нашето ежедневие са "имплементирани" като стек. Представете си тази проста ситуация: отседнали сте в хотел и през деня сте получor няколко бизнес писма. Вие не сте бor в стаята си по това време, така че служителят на хотела просто е поставил входящите писма на бюрото ви. Първо постави първата буква на бюрото. След това пристигна второ писмо и той го постави върху първото. Той постави третата буква върху втората, а четвъртата върху третата. А сега отговорете на един прост въпрос: коя буква ще прочетете първо , когато се върнете в стаята си и видите купчината на масата? Добре, ще прочетете най-горнияписмо. Тоест този, който пристигна най-скоро . Точно така работи един стек. Този принцип се нарича "последен влязъл, първи излязъл" (LIFO) . За Howво са полезни стековете? Е, да предположим, че създавате няHowва игра на карти в Java. Тесте карти лежи на масата. Изиграните карти се изхвърлят. Можете да използвате два стека, за да реализирате Howто тестето за теглене, така и купчината за изхвърляне. Играчите вземат картите си от горната част на тестето, като следват същия принцип като при вашите бизнес писма. Когато играчите поставят карти в купчината за изхвърляне, новите изхвърлени карти се поставят върху старите. Ето първия ни опит за играта, реализиран на базата на стек:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       discardPile.push(card);
   }

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

Както казахме по-рано, имаме два стека: тесте за теглене и купчина за изхвърляне. В Java структурата на данните на стека е имплементирана в java.util.Stackкласа. Нашата игра с карти има 3 метода, които описват действията на играчите:

• вземете карта от тестето ( getCardFromDeck()метод)
• изхвърляне на карта ( discard()метод)
• погледнете горната карта ( lookAtTopCard()метод). Да кажем, че това е бонус „Интелигентност“, който позволява на играча да разбере коя карта ще дойде следващата в играта.

В нашите методи ние извикваме следните методи на класа Stack:

• push()— добавя елемент в горната част на стека. Когато изпратим карта в купчината за изхвърляне, тя отива в горната част на купчината
• pop()— премахва горния елемент от стека и го връща. Този метод е идеален за изпълнение на действия, при които играчът тегли карта.
• peek()— връща горния елемент на стека, но не го премахва от стека

Да видим How ще работи нашата игра:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

Добавихме пет карти към нашето тесте. Първият играч взе 3 от тях. Кои карти е получила? Конзолен изход:

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

Обърнете внимание на реда, в който картите се показват на конзолата. Картата „Edwin VanCleef“ влезе в тестето последна (това беше петата карта) и това беше картата, която играчът изтегли пръв. „Millhouse“ беше предпоследен в тестето и играчът го изтегли втори. "Sylvanas" влезе в тестето трети отгоре и това беше третата карта, която играчът изтегли. След това играчът изхвърля карти. Първо тя изхвърля Едуин, след това Милхаус, след това Силвана. След това показваме картите в нашата купчина за изхвърляне една по една: Изход от конзолата:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

Още веднъж виждаме How работи един стек! В нашата игра купчината за изхвърляне също е стек (точно като тестето за теглене). "Edwin VanCleef" беше изхвърлен първи. Втората изхвърлена карта беше Millhouse Manastorm и беше поставена върху Edwin в купчината за изхвърляне. След това Силвана беше изхвърлена и тази карта беше поставена върху Millhouse. Както можете да видите, няма нищо сложно в стека. Все пак трябва да познавате тази структура от данни - често се пита за нея по време на интервюта за работа и често е основата за изграждане на по-сложни структури от данни.

Опашка в Java

Опашката е друга често срещана структура от данни. В допълнение към стековете, много езици за програмиране, включително Java, също реализират структурата на данните на опашката. Каква е разликата между опашка и стек? Опашката се основава не на принципа LIFO, а по-скоро на принципа FIFO („първи влязъл, пръв излязъл“). Този принцип е лесен за разбиране, като разгледаме например обикновена линия or опашка в реалния живот! Например опашка в магазина за хранителни стоки. Ако има петима души на опашка, първият , който ще бъде обслужен, ще бъде този, който е влязъл пръв на опашката . Ако друг човек (в допълнение към петимата вече на опашката) иска да купи нещо и се нареди на опашката, тогава той се обслужва последен, тоест шесто. Когато работите с опашка, нови елементи се добавят към опашката (отзад), а ако искате да получите елемент, той ще бъде взет от главата (отпред). Това е основният принцип, който трябва да запомните за това How работи опашката. Работата с опашката е много интуитивна, тъй като често срещаме опашки в реалния живот. Струва си да се отбележи отделно, че в Java опашката е представена не от клас, а от интерфейс: Queue. Нещо повече, има много реализации на този интерфейс на опашка в Java. Ако погледнем documentацията на Oracle, ще видим, че 4 различни интерфейса, Howто и изключително впечатляващ списък от класове, наследяват интерфейса Queue:

All known subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All known implementing classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Какъв голям списък! Но, разбира се, не е нужно да запомняте всички тези класове и интерфейси точно сега - главата ви може да избухне :) Ще разгледаме само няколко от най-важните и интересни точки. Първо, нека обърнем внимание на един от четирите „подинтерфейса“ на Queue: Deque . Какво го прави толкова специален? A Dequeе опашка с двоен край. Той разширява функционалността на обикновена опашка, като ви позволява да добавяте елементи към двата края (в началото и опашката) и да вземате елементи от двата края на опашката. Двустранните опашки се използват широко в разработката на софтуер. Обърнете внимание на списъка с класове на опашка, който предоставихме по-горе. Списъкът е доста дълъг, но има ли нещо познато?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

ха! Ето го старият ни приятел LinkedList! И така, той имплементира интерфейса Queue? Но How може да е опашка? В крайна сметка a LinkedListе свързан списък! Вярно, но това не пречи да е опашка :) Ето списък на всички интерфейси, които прилага:

All implemented interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Както можете да видите, LinkedListимплементира Dequeинтерфейса (отново това означава опашка с двоен край). Защо е необходимо това? Това ни позволява да получаваме елементи от началото и края на LinkedList. Също така ни позволява да добавяме елементи към началото и края. Ето методите, които LinkedListсе получават от Dequeинтерфейса:

• peekFirst()— връща първия елемент (но не го премахва от опашката).
• peekLast()— връща последния елемент (но не го премахва от опашката).
• pollFirst()— връща първия елемент от опашката и го премахва.
• pollLast()— връща последния елемент от опашката и го премахва.
• addFirst()— добавя нов елемент в началото на опашката.
• addLast()— добавя елемент в края на опашката.

Както можете да видите, LinkedListнапълно прилага функционалността на опашка с двоен край! И имате нужда от такава функционалност в програмата си, ще знаете къде да я намерите :) Днешният урок е към своя край. В заключение ще ви дам няколко връзки за допълнително четене. Първо, обърнете внимание на тази статия за PriorityQueue . Това е една от най-интересните и полезни Queueреализации. Да предположим например, че във вашия магазин чакат 50 души на опашка и 7 от тях са VIP клиенти. PriorityQueue ще ви позволи да ги обслужите първи! Много полезни неща, нали? :) Второ, няма да навреди още веднъж да споменем книгата на Робърт Лафоре "Структури на данни и алгоритми в Java". Четейки тази книга, вие не само ще научите много структури от данни (включително стек и опашка), но и сами ще имплементирате много от тях! Например, Howво ще стане, ако Java няма клас Stack? Какво бихте направor, ако имате нужда от такава структура от данни за вашата програма? Ще трябва да го напишете сами, разбира се. Докато четете книгата на Lafore , често ще правите точно това. В резултат вашето разбиране на структурите от данни ще бъде много по-задълбочено от това, което бихте получor от обикновено изучаване на теорията :) Завършваме теорията за днес, но теорията без практика е нищо! Задачите няма да се решат сами, така че е време да се захванете с тях! :)