Data structures: stack and queue

Hi! Today we'll talk about something that is super important for any programmer: data structures. Wikipedia says: "A data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data." The definition is a bit confusing, but its gist is clear. A data structure is a kind of repository where we store data for future use. In programming, there are a huge variety of data structures. When solving specific problems, very often the most important thing is to choose the most suitable data structure for the problem. And you are already familiar with many of them! For example, you know about arrays. And you are also familiar with Map (this data structure may also be referred to as a "dictionary" or "associative array"). It is very important to understand that data structures are not tied to any particular language. They are simply abstract "blueprints" that each programming language uses to create its own classes or implementations of a particular structure. For example, one of the most famous data structures is a linked list. You can go to Wikipedia and read about how it works and what advantages and disadvantages it has. Perhaps its definition will seem familiar to you :) "A linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next." That describes our beloved LinkedList, doesn't it? Yes, and that's just what it is :) In Java, the "linked list" data structure is implemented by the LinkedList class. But other languages also implement linked lists! In Python, this data structure is called "llist". In Scala it is called "LinkedList", just like in Java. A linked list is one of the basic common data structures, so you will find that it is implemented in any modern programming language. The same thing is true of associative arrays. Here is the definition from Wikipedia: "An associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection." Does that remind you of anything? :) Yep. For us Java developers, an associative array is the Map interface. But this data structure is also implemented in other languages! For example, C# programmers know it under the name "Dictionary". And in Ruby, it is implemented in a class called "Hash". Well, you get the point: data structures are universal concepts in programming, and each programming language implements them in its own way. Today we will study two such structures — the stack and the queue — and see how they are implemented in Java.

Stacks in Java

A stack is a well-known data structure. It is very simple. Quite a few items in our daily lives are "implemented" as a stack. Imagine this simple situation: you're staying at a hotel, and over the course of the day you received some business letters. You were not in your room at the time, so the hotel clerk simply placed the incoming letters on your desk. First, he placed the first letter on the desk. Then a second letter arrived, and he placed it on top of the first. He put the third letter on top of the second, and the fourth on top of the third. And now, answer a simple question: what letter will you read first when you come back to your room and see the stack on the table? Right, you will read the topmost letter. That is, the one that arrived most recently. This is exactly how a stack works. This principle is called "last in first out" (LIFO). What are stacks good for? Well, suppose you are creating some kind of card game in Java. A deck of cards lies on the table. The played cards are discarded. You can use two stacks to implement both the draw deck and the discard pile. Players take their cards from the top of the deck, following the same principle as with your business letters. When players put cards into the discard pile, the newly discarded cards are placed on top of the old. Here's our first attempt at the game, implemented on the basis of 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 {

   // 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.
}

As we said earlier, we have two stacks: a draw deck and a discard pile. In Java, the stack data structure is implemented in the java.util.Stack class. Our card game has 3 methods that describe the actions of the players:

• take a card from the deck (getCardFromDeck() method)
• discard a card (discard() method)
• look at the top card (lookAtTopCard() method). Let's say this is an "Intelligence" bonus that allows the player to find out which card will come next in the game.

Inside our methods, we call the following methods of the Stack class:

• push() — adds an item to the top of the stack. When we send a card to the discard pile, it goes to the top of the pile
• pop() — removes the top element from the stack and returns it. This method is perfect for implementing actions in which the player draws a card.
• 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) {

       // 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());
   }
}

We added five cards to our deck. The first player took 3 of them. Which cards did she get? Console output:

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

Pay attention to the order in which the cards are displayed on the console. The "Edwin VanCleef" card went into the deck last (it was the fifth card), and it was the card that the player drew first. "Millhouse" was second to last into the deck, and the player drew it second. "Sylvanas" went into the deck third from the top, and it was the third card that the player drew. Next, the player discards cards. First, she discards Edwin, then Millhouse, then Sylvanas. Then we display the cards in our discard pile one by one: Console output:

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

Once again, we see how a stack works! In our game, the discard pile is also a stack (just like the draw deck). "Edwin VanCleef" was discarded first. The second card discard was Millhouse Manastorm, and it was placed on top of Edwin in the discard pile. Then Sylvanas was discarded, and this card was placed on top of Millhouse. As you can see, there is nothing complicated about a stack. Still, you need to know this data structure — it is often asked about during job interviews, and it is often the basis for building more complex data structures.

Queue in Java

A queue is another common data structure. In addition to stacks, many programming languages, including Java, also implement the queue data structure. What's the difference between a queue and a stack? A queue is based not on the LIFO principle, but rather on the FIFO principle ("first in, first out"). This principle is easy to understand by considering, for example, an ordinary line, or queue, in real life! For example, a line at the grocery store. If there are five people in line, the first one to be served will be the one who entered the line first. If another person (in addition to five already in line) wants to buy something and gets in line, then he gets served last, that is, sixth. When working with a queue, new elements are added to the tail (back), and if you want to get an element, it will be taken from the head (front). This is the main principle you need to remember regarding how a queue works. A queue's operation is very intuitive, since we find queues often in real life. It is worth noting separately that in Java a queue is represented not by a class, but by an interface: Queue. What's more, there are a lot of implementations of this queue interface in Java. If we look at the Oracle documentation, we will see that 4 different interfaces, as well as an extremely impressive list of classes, inherit the Queue interface:

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 right now — your head might explode :) We'll only consider a couple of the most important and interesting points. First, let's pay attention to one of Queue's four "subinterfaces": Deque. What makes it so special? A Deque is a double-ended queue. It extends the functionality of a regular queue, allowing you to add elements to both ends (at the head and the tail) and take elements from both ends of the queue. Double-ended queues are widely used in software development. Pay attention to the list of queue classes that we provided above. The list is quite long, but does it contain anything familiar?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

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

All implemented interfaces:

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

As you can see, LinkedList implements the Deque interface (again, this means double-ended queue). Why is this needed? This allows us to get elements from the beginning and the end of a LinkedList. It also allows us to add elements to the beginning and end. Here are the methods that LinkedList gets from the Deque interface:

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

As you can see, LinkedList fully implements the functionality of a double-ended queue! And you need such functionality in your program, you'll know where to find it :) Today's lesson is coming to an end. In conclusion, I'll give you a couple of links for additional reading. First, pay attention to this article about PriorityQueue. This is one of the most interesting and useful Queue implementations. For example, suppose there are 50 people waiting in line at your store, and 7 of them are VIP customers. A PriorityQueue will let you serve them first! Very useful stuff, right? :) Second, it wouldn't hurt to once again mention Robert Lafore's book "Data Structures and Algorithms in Java". Reading this book, you'll not only learn many data structures (including stack and queue), but you'll also implement many of them yourself! For example, what if Java didn't have a Stack class? What would you do if you needed such a data structure for your program? You would have to write it yourself, of course. As you read Lafore's book, you will often do just that. As a result, your understanding of data structures will be much deeper than what you would get from a simple study of the theory :) We are wrapping up the theory for today, but theory without practice is nothing! The tasks won't solve themselves, so it's time to tackle them! :)