Java의 데이터 구조 - 스택 및 큐

안녕하세요! 오늘 우리는 모든 프로그래머에게 데이터 구조 와 같은 중요한 것들에 대해 이야기하겠습니다 . Wikipedia에서는 다음과 같이 말합니다. 데이터 구조 ( eng. 데이터 구조 )는 컴퓨팅에서 동일한 유형 및/또는 논리적으로 관련된 많은 데이터를 저장하고 처리할 수 있는 소프트웨어 단위입니다. 정의는 약간 혼란스럽지만 그 본질은 분명합니다. 데이터 구조는 추가 사용을 위해 데이터를 저장하는 일종의 저장소입니다. 프로그래밍에는 매우 다양한 데이터 구조가 있습니다. 특정 문제를 해결할 때 가장 중요한 것은 해당 목적에 가장 적합한 데이터 구조를 선택하는 것입니다. 그리고 당신은 이미 그들 중 많은 것을 잘 알고 있습니다! 예를 들어 배열 의 경우 . 또한 with Map(일반적으로 "사전", "맵" 또는 "연관 배열"로 번역됨)도 있습니다. 이해하는 것이 매우 중요합니다. 데이터 구조는 특정 언어에 묶여 있지 않습니다 . 이는 각 프로그래밍 언어가 자체 클래스, 즉 이 구조의 구현을 생성하는 추상적인 "청사진"일 뿐입니다. 예를 들어, 가장 유명한 데이터 구조 중 하나는 연결 목록 입니다 . Wikipedia로 이동하여 작동 방식, 장점과 단점에 대해 읽어보세요. 그 정의가 익숙할 것입니다. :) "연결된 목록은 컴퓨터 과학의 기본 동적 데이터 구조로, 노드로 구성됩니다. 각 노드에는 데이터 자체와 다음 및/또는 데이터에 대한 하나 또는 두 개의 링크("링크")가 모두 포함되어 있습니다. 이전 노드 목록” 그래서 이것이 우리 것입니다 LinkedList! 바로 그거예요 :) 연결리스트 데이터 구조는 자바 언어의 클래스에서 구현됩니다 LinkedList. 하지만 다른 언어도 연결 목록을 구현합니다! Python에서는 " "라고 하며 llistScala에서는 Java에서와 동일하게 " LinkedList"라고 합니다. 연결된 목록은 기본 공통 데이터 구조 중 하나이므로 모든 최신 프로그래밍 언어에서 구현을 찾을 수 있습니다. 연관 배열도 마찬가지입니다. Wikipedia의 정의는 다음과 같습니다. 연관 배열은 "(키, 값)" 형식의 쌍을 저장할 수 있고 쌍을 추가하는 작업과 검색을 지원하는 추상 데이터 유형(데이터 저장소에 대한 인터페이스)입니다. 키로 쌍을 삭제합니다. 아무것도 생각나지 않나요? :) 정확하게는 우리 Javaists에게 연관 배열은 인터페이스입니다.Map. 하지만 이 데이터 구조는 다른 언어에서도 구현됩니다! 예를 들어 C# 프로그래머는 이를 "사전"이라는 이름으로 알고 있습니다. 그리고 Ruby 언어에서는 "Hash"라는 클래스로 구현됩니다. 일반적으로 의미가 무엇인지 대략적으로 이해합니다. 데이터 구조는 모든 프로그래밍에 공통적이며 각 특정 언어에서 다르게 구현됩니다. 오늘 우리는 이러한 두 가지 구조(스택과 큐)를 연구하고 Java에서 어떻게 구현되는지 살펴보겠습니다.

자바의 스택

스택은 알려진 데이터 구조입니다. 매우 간단하며 일상 생활에서 사용되는 많은 개체가 스택으로 "구현"됩니다. 간단한 상황을 상상해보십시오. 당신은 호텔에 살고 있으며 낮에는 비즈니스 편지를 받았습니다. 그 시간에 당신이 방에 없었기 때문에 호텔 직원은 단순히 들어오는 편지를 당신의 테이블 위에 올려 놓았습니다. 먼저 그는 테이블 위에 첫 글자를 올려놓았다. 그런 다음 두 번째 사람이 와서 그것을 첫 번째 사람 위에 올려 놓았습니다. 그는 도착한 세 번째 편지를 두 번째 편지 위에, 네 번째 편지를 세 번째 편지 위에 놓았습니다. 이제 간단한 질문에 대답해 보세요. 방에 와서 테이블 위에 쌓인 더미를 보면 어떤 편지를 가장 먼저 읽을 것입니까? 맞습니다, 당신은 맨 위의 편지를 읽을 것입니다. 즉, 시간상 마지막에 온 것입니다 . 이것이 바로 스택이 작동하는 방식입니다. 이 작동 원리를 LIFO(후입선출) 라고 합니다 . 스택은 어디에 유용할까요? 예를 들어, Java로 일종의 카드 게임을 만들고 있습니다. 테이블 위에는 카드 한 벌이 놓여 있습니다. 사용된 카드는 폐기됩니다. 두 개의 스택을 사용하여 데크와 폐기를 모두 구현할 수 있습니다. 플레이어는 덱 상단에서 카드를 뽑습니다. 이는 글자와 동일한 원리입니다. 플레이어가 카드를 버리면 새 카드가 기존 카드 위에 놓입니다. 스택을 사용하여 구현된 게임의 첫 번째 초안은 다음과 같습니다.

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

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

앞서 말했듯이 우리는 덱과 폐기라는 두 개의 스택을 가지고 있습니다. 스택 데이터 구조는 Java에서 java.util.Stack. 우리 카드 게임에는 플레이어의 행동을 설명하는 3가지 방법이 있습니다.

• 덱에서 카드를 가져옵니다(방법 getCardFromDeck()).
• 카드를 버리고(방법 discard());
• 맨 위 카드를 봅니다(방법 lookTopCard()). 이것이 플레이어가 다음에 어떤 카드가 나올지 알아낼 수 있게 해주는 보너스 메커니즘인 "지능"이 될 것이라고 가정해 보겠습니다.

메소드 내에서 클래스 메소드가 호출됩니다 Stack.

• push()— 스택의 맨 위에 요소를 추가합니다. 카드를 버리면 이전에 버려진 카드 위에 놓입니다.
• pop()— 스택에서 최상위 요소를 제거하고 반환합니다. 이 방법은 "플레이어가 카드를 뽑는다" 메커니즘을 구현하는 데 이상적입니다.
• peek()- 스택의 최상위 요소를 반환하지만 스택에서 제거하지는 않습니다.

게임이 어떻게 작동하는지 살펴보겠습니다.

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

그래서 우리는 덱에 카드 5장을 추가했습니다. 첫 번째 플레이어가 그 중 3개를 가져갔습니다. 그는 어떤 카드를 받았나요? 콘솔 출력:

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

카드가 콘솔에 출력된 순서에 주의하세요. "Edwin Van Cleiff" 카드는 덱에 마지막으로 떨어진 카드(5번째 연속)였으며 플레이어가 먼저 가져간 카드였습니다. "Michhlaus"는 덱의 마지막에서 두 번째였으며, 그 플레이어가 두 번째를 차지했습니다. "Sylvanas"는 덱 끝에서 세 번째에 맞고 세 번째 플레이어에게 넘어갔습니다. 다음으로, 플레이어는 자신의 카드를 버립니다. 먼저 그는 Edwin을 떨어뜨렸고, 그 다음에는 Millhouse, 그 다음에는 Sylvanas를 떨어뜨렸습니다. 그런 다음 폐기된 카드를 하나씩 콘솔에 출력합니다. 콘솔에 출력:

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

그리고 다시 스택이 어떻게 작동하는지 살펴보겠습니다! 우리 게임에서 버리는 것도 (덱과 마찬가지로) 스택입니다. "Edwin Van Clyffe"가 가장 먼저 삭제되었습니다. 두 번째로 떨어뜨린 것은 "Millhouse Manastorm"이었고 폐기 시 Edwin 위에 놓였습니다. 다음으로 Sylvanas는 버려졌고 이 카드는 Millhouse 위에 놓였습니다. 보시다시피 스택 작동 방식에는 복잡한 것이 없습니다. 그러나 이 데이터 구조를 아는 것이 필요합니다. 인터뷰에서 자주 질문을 받고 이를 기반으로 보다 복잡한 데이터 구조가 구축되는 경우가 많습니다.

대기줄

큐(또는 영어로 “Queue”)는 또 다른 일반적인 데이터 구조입니다. 스택과 마찬가지로 Java를 포함한 많은 프로그래밍 언어로 구현됩니다. 큐와 스택의 차이점은 무엇입니까? 해당 대기열은 LIFO가 아니라 또 다른 원칙인 FIFO(선입선출, 선입선출)를 기반으로 합니다 . 예를 들어보면 이해하기 쉽습니다... 또는 적어도 실제 생활의 평범하고 실제적인 대기열을 예로 들면요! 예를 들어 상점 대기열입니다. 5명이 줄을 섰을 경우, 먼저 줄을 선 사람이 매장 에 입장하게 됩니다 . (5명 줄 외에) 한 사람이 더 사고 싶어 줄을 서면 그 사람은 마지막 , 즉 6번째 가게에 들어갑니다. 큐로 작업할 때 새 요소는 끝에 추가되며, 요소를 얻으려면 처음부터 가져옵니다. 이것이 여러분이 기억해야 할 동작의 기본 원리인데, 큐의 원리는 실생활에서 자주 접하게 되므로 직관적으로 이해하기가 매우 쉽습니다. Java에서 대기열은 클래스가 아니라 인터페이스로 표시된다는 점을 별도로 주목할 가치가 있습니다 Queue. 그러나 동시에 Java의 대기열은 많은 구현을 포함하는 인터페이스입니다. Oracle 문서를 보면 4개의 서로 다른 인터페이스와 매우 인상적인 클래스 목록이 대기열에서 상속되는 것을 볼 수 있습니다.

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

정말 큰 목록입니다! 하지만 물론 지금은 이러한 클래스와 인터페이스를 모두 외울 필요는 없습니다. 머리가 터질 것 같습니다 :) 가장 중요하고 흥미로운 점 몇 가지만 살펴보겠습니다. 먼저 대기열의 4개 "하위 인터페이스" 중 하나인 에 주목해 보겠습니다 Deque. 무엇이 그렇게 특별한가요? Deque- 양방향 대기열입니다. 이는 양쪽 끝(큐의 시작과 끝)에 요소를 추가하고 큐의 양쪽 끝에서 요소를 가져올 수 있도록 하여 일반 큐의 기능을 확장합니다. deque는 개발에 널리 사용됩니다. 위에서 제공한 대기열 클래스 목록에 주의하세요. 목록은 꽤 길지만 거기에 우리에게 친숙한 것이 있습니까?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

하, 우리 오랜 친구가 여기 있군요 LinkedList! 즉, 인터페이스를 구현합니까 Queue? 그런데 어떻게 대기열이 될 수 있습니까? 결국 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먼저 서비스를 제공할 수 있습니다! 매우 유용한 것입니다. 동의하지 않나요? :) 둘째, Robert Laforet의 저서 "Data Structures and Algorithms in Java"를 다시 한 번 언급하는 것은 불필요한 일이 아닙니다 . 책을 읽는 동안 많은 데이터 구조(스택 및 큐 포함)를 배울 뿐만 아니라 그 중 많은 부분을 직접 구현하게 됩니다! 예를 들어 Java에 Stack 클래스가 없다고 가정해 보세요. 프로그램에 그러한 데이터 구조가 필요하다면 어떻게 하시겠습니까? 물론 제가 직접 작성해야겠죠. 라포레의 책을 읽을 때 여러분은 종종 이런 일을 하게 될 것입니다. 덕분에 단순히 이론을 공부하는 것보다 데이터 구조에 대한 이해가 훨씬 넓어질 것입니다 :) 오늘은 이론은 끝났지만 실천이 없는 이론은 아무것도 아닙니다! 문제는 저절로 해결되지 않습니다. 이제 문제를 해결해야 할 때입니다! :)