Data Structures in Java - Stack and Queue

Hello! Today we’ll talk about such important things for any programmer as data structures . Wikipedia says: Data structure ( eng. data structure ) is a software unit that allows you to store and process a lot of the same type and/or logically related data in computing. The definition is a little confusing, but its essence is clear. A data structure is a kind of storage where we store data for further use. There are a huge variety of data structures in programming. Very often, when solving a specific problem, the most important thing is choosing the most suitable data structure for this purpose. And you are already familiar with many of them! For example, with arrays . And also with Map(which is usually translated as “dictionary”, “map”, or “associative array”). It is very important to understand: data structures are not tied to any specific language . These are simply abstract “blueprints” according to which each programming language creates its own classes - implementations of this structure. For example, one of the most famous data structures is the linked list . You can go to Wikipedia, read about how it works, what advantages and disadvantages it has. You may find its definition familiar :) “A linked list is a basic dynamic data structure in computer science, consisting of nodes, each of which contains both the data itself and one or two links (“links”) to the next and/or previous node list” So this is ours LinkedList! Exactly, that's how it is :) The linked list data structure is implemented in the Java language in the class LinkedList. But other languages ​​also implement linked lists! In Python it is called “ llist”, in Scala it is called the same as in Java - “ LinkedList“. A linked list is one of the basic common data structures, so you can find its implementation in any modern programming language. Same thing with an associative array. Here is its definition from Wikipedia: An associative array is an abstract data type (an interface to a data store) that allows storing pairs of the form “(key, value)” and supports the operations of adding a pair, as well as searching and deleting a pair by key. Doesn't remind you of anything? :) Exactly, for us Javaists, an associative array is an interfaceMap. But this data structure is implemented in other languages ​​too! For example, C# programmers know it under the name “Dictionary”. And in the Ruby language it is implemented in a class called “Hash”. In general, you roughly understand what the meaning is: a data structure is a thing common to all programming, which is implemented differently in each specific language. Today we will study two such structures and see how they are implemented in Java - stack and queue.

Stack in Java

A stack is a known data structure. It is very simple and quite a lot of objects from our daily life are “implemented” as a stack. Imagine a simple situation: you live in a hotel, and during the day you receive business letters. Since you were not in the room at that time, the hotel employee simply put the incoming letters on your table. First he put the first letter on the table. Then the second one came and he put it on top of the first. He placed the third letter that arrived on top of the second, and the fourth on top of the third. Now, answer a simple question: what letter will you read first when you come to your room and see a stack on the table? That's right, you will read the top letter. That is, the one that came last in time . This is exactly how a stack works. This operating principle is called LIFO - “last in - first out” (“last in, first out”). What can a stack be useful for? For example, you are creating some kind of card game in Java. A deck of cards lies on the table. Played cards are discarded. You can implement both the deck and the discard using two stacks. Players draw cards from the top of the deck - the same principle as with letters. When players discard cards, new cards are placed on top of old ones. Here's what the first draft of our game would look like, implemented using a stack:

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 {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

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

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

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

As we said earlier, we have two stacks: the deck and the discard. The stack data structure is implemented in Java in the java.util.Stack. In our card game there are 3 methods that describe the actions of the players:

• take a card from the deck (method getCardFromDeck());
• discard card (method discard());
• look at the top card (method lookTopCard()). Let's say this will be the bonus mechanic “Intelligence”, which will allow the player to find out which card will come into play next.

Inside our methods, class methods are called Stack:

• push()— adds an element to the top of the stack. When we discard a card, it goes on top of the previously discarded cards;
• pop()— removes the top element from the stack and returns it. This method is ideal for implementing the “player draws a card” mechanic.
• peek()- returns the top element of the stack, but does not remove it from the stack

Let's see how our game will work:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

So we've added five cards to our deck. The first player took 3 of them. What cards did he get? Console output:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

Pay attention to the order in which the cards were output to the console. The “Edwin Van Cleiff” card was the last one to hit the deck (fifth in a row), and it was the card that the player took first. “Michhlaus” was the second to last one on the deck, and its player took it second. “Sylvanas” hit the deck third from the end, and went to the third player. Next, the player discards his cards. First he drops Edwin, then Millhouse, then Sylvanas. After which we one by one output to the console the cards that are in our discard: Output to the console:

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

And again we see how the stack works! The discard in our game is also a stack (just like the deck). "Edwin Van Clyffe" was the first to be dropped. The second to be dropped was “Millhouse Manastorm” - and lay on top of Edwin in the discard. Next, Sylvanas was discarded - and this card lay on top of Millhouse. As you can see, there is nothing complicated about how the stack works. However, it is necessary to know this data structure - it is often asked about in interviews, and more complex data structures are often built on its basis.

Queue

A queue (or, in English, “Queue”) is another common data structure. Just like a stack, it is implemented in many programming languages, including Java. What is the difference between a queue and a stack? Its queue is not based on LIFO, but on another principle - FIFO (“first in - first out”, “first in - first out”) . It’s easy to understand, taking as an example... or at least an ordinary, real queue from real life! For example, a queue to the store. If there are five people in line, the first person in line will get into the store . If one more person (besides the five in line) wants to buy something and gets in line, then he gets into the store last , that is, sixth. When working with a queue, new elements are added to the end, and if you want to get an element, it will be taken from the beginning. This is the basic principle of its operation, which you need to remember. The principle of the queue is very easy to understand intuitively, since it is often encountered in real life. It is worth noting separately that in Java a queue is represented not by a class, but by an interface - Queue. But at the same time, a queue in Java is an interface that has many implementations. If we look at the Oracle documentation, we will see that 4 different interfaces and an extremely impressive list of classes are inherited from the 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

What a big list! But, of course, you don’t need to memorize all these classes and interfaces now - your head might explode :) We will look at only a couple of the most important and interesting points. First, let's pay attention to one of the four “sub-interfaces” of the queue - Deque. What's so special about it? Deque- This is a two-way queue. It extends the functionality of a regular queue by allowing you to add elements to both ends (the beginning and end of the queue) and take elements from both ends of the queue. The deque is widely used in development. Pay attention to the list of queue classes that we provided above. The list is quite long, but is there anything familiar to us there?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, so our old friend is here LinkedList! That is, it implements the interface Queue? But how can he be a queue? After all LinkedList, this is a connected list! True, but that doesn't stop it from being a queue :) Here's a list of all the interfaces it implements:

All Implemented Interfaces:

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

As you can see, LinkedListit implements an interface Deque- a two-way queue. Why is this necessary? Thanks to this, we can get elements from both the beginning and the end LinkedList. And also - add elements to both the beginning and the end. Here are the methods inherited LinkedListfrom the interface Deque:

• peekFirst()— returns (but does not remove from the queue) the first element.
• peekLast()— returns (but does not remove from the queue) the last element.
• pollFirst()- returns the first element from the queue and removes it.
• pollLast()- returns the last element from the queue and removes it.
• addFirst()— adds a new element to the beginning of the queue.
• addLast()— adds an element to the end of the queue.

As you can see, LinkedListit fully implements the functionality of a two-way queue! And if such functionality is needed in the program, you will know that it can be used :) And our lecture today is coming to an end. Finally, I'll give you a couple of links for further reading. First, pay attention to the article dedicated to PriorityQueue - “priority queue”. This is one of the most interesting and useful implementations of Queue. For example, if there are 50 people in line at your store, and 7 of them are VIP clients, PriorityQueueit will allow you to serve them first! A very useful thing, don’t you agree? :) Secondly, it would not be superfluous to once again mention Robert Laforet’s book “Data Structures and Algorithms in Java” . While reading the book, you will not only learn many data structures (including stack and queue), but you will also implement many of them yourself! For example, imagine if Java didn't have a Stack class. What would you do if you needed such a data structure for your program? Of course, I would have to write it myself. When reading Laforet's book, this is often what you will do. Thanks to this, your understanding of data structures will be much broader than when simply studying theory :) We are done with theory for today, but theory without practice is nothing! The problems won't solve themselves, so now is the time to tackle them! :)