데이터 구조: 스택 및 큐

안녕! 오늘 우리는 모든 프로그래머에게 매우 중요한 데이터 구조에 대해 이야기할 것입니다. Wikipedia에서는 " 데이터 구조는 효율적인 액세스 및 수정을 가능하게 하는 데이터 구성, 관리 및 저장 형식입니다. 보다 정확하게는 데이터 구조는 데이터 값, 이들 간의 관계 및 수행할 수 있는 기능 또는 작업의 모음입니다. 데이터에 적용됩니다." 정의는 약간 혼란스럽지만 그 요지는 분명합니다. 데이터 구조는 나중에 사용할 수 있도록 데이터를 저장하는 일종의 저장소입니다. 프로그래밍에는 매우 다양한 데이터 구조가 있습니다. 특정 문제를 해결할 때 가장 중요한 것은 문제에 가장 적합한 데이터 구조를 선택하는 것입니다. 그리고 당신은 이미 그들 중 많은 것에 익숙합니다! 예를 들어 배열에 대해 알고 있습니다. 그리고 당신도 잘 알고 있습니다Map(이 데이터 구조는 "사전" 또는 "연관 배열"이라고도 합니다.) 데이터 구조가 특정 언어에 연결되어 있지 않다는 것을 이해하는 것이 매우 중요합니다. 이들은 단순히 각 프로그래밍 언어가 고유한 클래스 또는 특정 구조의 구현을 만드는 데 사용하는 추상적인 "청사진"입니다. 예를 들어, 가장 유명한 데이터 구조 중 하나는 연결 목록입니다. Wikipedia로 이동하여 작동 방식과 장점 및 단점에 대해 읽을 수 있습니다. 아마도 그것의 정의는 당신에게 친숙해 보일 것입니다 :) "연결된 목록은 데이터 요소의 선형 컬렉션이며 순서는 메모리의 물리적 배치에 의해 주어지지 않습니다. 대신 각 요소는 다음 항목을 가리킵니다." 그것은 우리의 사랑하는 사람을 묘사 LinkedList하지 않습니까? 예, 그게 바로 그것입니다 :) Java에서 "연결된 목록" 데이터 구조는 클래스에 의해 구현됩니다 LinkedList. 그러나 다른 언어도 연결 목록을 구현합니다! Python에서는 이 데이터 구조를 " llist"라고 합니다. LinkedListScala에서는 Java와 마찬가지로 " "라고 합니다 . 연결된 목록은 기본 공통 데이터 구조 중 하나이므로 최신 프로그래밍 언어로 구현된다는 것을 알 수 있습니다. 연관 배열도 마찬가지입니다. Wikipedia의 정의는 다음과 같습니다. 생각나는 게 있나요? :) 네. 우리 Java 개발자에게 연관 배열은Map상호 작용. 그러나이 데이터 구조는 다른 언어로도 구현됩니다! 예를 들어 C# 프로그래머는 "Dictionary"라는 이름으로 알고 있습니다. 그리고 Ruby에서는 "Hash"라는 클래스에서 구현됩니다. 데이터 구조는 프로그래밍의 보편적인 개념이며 각 프로그래밍 언어는 이를 고유한 방식으로 구현합니다. 오늘 우리는 스택과 큐라는 두 가지 구조를 연구하고 이들이 Java에서 어떻게 구현되는지 알아볼 것입니다.

Java의 스택

스택은 잘 알려진 데이터 구조입니다. 매우 간단합니다. 일상 생활에서 꽤 많은 항목이 스택으로 "구현"됩니다. 다음과 같은 간단한 상황을 상상해 보십시오. 당신은 호텔에 머물고 있으며 하루 종일 비즈니스 서신을 받았습니다. 당신은 그 때 당신의 방에 없었기 때문에 호텔 직원은 단순히 들어오는 편지를 당신의 책상 위에 놓았습니다. 먼저 그는 첫 번째 편지를 책상 위에 올려놓았다. 그런 다음 두 번째 편지가 도착했고 그는 그것을 첫 번째 편지 위에 올려 놓았습니다. 그는 세 번째 글자를 두 번째 글자 위에, 네 번째 글자를 세 번째 글자 위에 놓았다. 이제 간단한 질문에 답하세요. 방으로 돌아와 탁자 위의 더미를 볼 때 가장 먼저 읽을 글자는 무엇입니까 ? 맞아, 맨 위 를 읽을거야편지. 즉, 가장 최근에 도착한 것입니다 . 이것이 바로 스택이 작동하는 방식입니다. 이 원칙을 "후입선출"(LIFO) 이라고 합니다 . 스택은 무엇에 좋은가요? 자, 당신이 자바로 어떤 종류의 카드 게임을 만든다고 가정해 봅시다. 카드 한 벌이 탁자 위에 놓여 있습니다. 사용한 카드는 버립니다. 두 개의 스택을 사용하여 드로우 데크와 폐기 더미를 모두 구현할 수 있습니다. 플레이어는 비즈니스 서신과 동일한 원칙에 따라 덱 맨 위에서 카드를 가져옵니다. 플레이어가 카드 더미에 카드를 넣으면 새로 버려진 카드가 이전 카드 위에 놓입니다. 다음은 스택을 기반으로 구현된 게임에서의 첫 번째 시도입니다.

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()— 스택의 맨 위 요소를 반환하지만 스택에서 제거하지는 않습니다.

게임이 어떻게 작동하는지 봅시다:

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

덱에 5장의 카드를 추가했습니다. 첫 번째 플레이어가 3개를 가져갔습니다. 그녀는 어떤 카드를 받았습니까? 콘솔 출력:

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

카드가 콘솔에 표시되는 순서에 주의하십시오. "Edwin VanCleef" 카드는 마지막으로 덱에 들어갔고(다섯 번째 카드) 플레이어가 가장 먼저 뽑은 카드였습니다. "Millhouse"는 데크에서 두 번째로 마지막이었고 플레이어는 두 번째로 뽑았습니다. "실바나스"는 위에서 세 번째 덱으로 들어갔고, 플레이어가 뽑은 세 번째 카드였습니다. 다음으로 플레이어는 카드를 버립니다. 먼저 그녀는 Edwin, Millhouse, Sylvanas를 버립니다. 그런 다음 폐기 더미에 있는 카드를 하나씩 표시합니다. 콘솔 출력:

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

다시 한 번 스택이 어떻게 작동하는지 확인합니다! 우리 게임에서 버린 더미는 스택이기도 합니다(드로우 덱과 같습니다). "Edwin VanCleef"가 먼저 폐기되었습니다. 두 번째 버린 카드는 Millhouse Manastorm이었고, 버린 카드 더미에서 Edwin 위에 놓였습니다. 그런 다음 Sylvanas는 폐기되었고 이 카드는 Millhouse 위에 놓였습니다. 보시다시피 스택에는 복잡한 것이 없습니다. 그래도 이 데이터 구조를 알아야 합니다. 구직 면접에서 자주 묻는 질문이며 더 복잡한 데이터 구조를 구축하기 위한 기초가 되는 경우가 많습니다.

자바의 대기열

대기열은 또 다른 일반적인 데이터 구조입니다. 스택 외에도 Java를 포함한 많은 프로그래밍 언어도 큐 데이터 구조를 구현합니다. 대기열과 스택의 차이점은 무엇입니까? 대기열은 LIFO 원칙이 아니라 FIFO 원칙("선입선출")을 기반으로 합니다. 이 원칙은 예를 들어 실생활에서 일반적인 줄이나 대기열을 고려하면 이해하기 쉽습니다! 예를 들어, 식료품점의 줄. 줄을 서 있는 사람이 5명일 경우 가장 먼저 입장한 사람이 먼저 서비스를 받습니다 . 다른 사람(이미 줄을 선 5명 외에)이 물건을 사고 싶어 줄을 서면 마지막으로 서빙을 받습니다.즉, 여섯 번째입니다. 큐 작업을 할 때 꼬리(뒷면)에 새로운 요소가 추가되고 요소를 얻고자 하면 머리(앞면)에서 가져옵니다. 이것은 대기열이 작동하는 방식과 관련하여 기억해야 할 주요 원칙입니다. 큐의 작업은 실생활에서 종종 큐를 찾기 때문에 매우 직관적입니다. Java에서 큐는 클래스가 아니라 인터페이스인 Queue로 표시된다는 점을 별도로 주목할 가치가 있습니다. 또한 Java에는 이 대기열 인터페이스가 많이 구현되어 있습니다. Oracle 설명서를 보면 4개의 다른 인터페이스와 매우 인상적인 클래스 목록이 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 인터페이스를 구현합니까? 그러나 어떻게 대기열이 될 수 있습니까? 결국, 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를 사용하면 먼저 서비스를 제공할 수 있습니다! 아주 유용한 내용이죠? :) 둘째, Robert Lafore의 저서 "Data Structures and Algorithms in Java"를 다시 한 번 언급해도 나쁘지 않을 것입니다.. 이 책을 읽으면 많은 데이터 구조(스택 및 큐 포함)를 배울 수 있을 뿐만 아니라 많은 데이터 구조를 직접 구현하게 됩니다! 예를 들어 Java에 Stack 클래스가 없다면 어떻게 될까요? 프로그램에 이러한 데이터 구조가 필요하다면 어떻게 하시겠습니까? 물론 직접 작성해야 합니다. 라포레의 책을 읽으면서 종종 그렇게 할 것입니다. 결과적으로 데이터 구조에 대한 이해는 단순한 이론 공부보다 훨씬 더 깊어질 것입니다 :) 오늘 이론은 마무리하지만 실습 없는 이론은 아무것도 아닙니다! 작업은 저절로 해결되지 않으므로 문제를 해결할 시간입니다! :)