자바의 도구인 Stack과 Queue에 대해 배우는 시간입니다. 구조와 원리에 대해서는 “Java로 배우는 자료구조” 코스에서 좀 더 깊게 이해를 하실 수 있습니다. 이 강의에서는 Stack과 Queue는 어떤 특징이 있는지, 어떻게 사용하는지에 대해서만 알아봅니다.

ㅤ

목차

1. Stack

2. Queue

ㅤ

Stack

“자바 메모리 구조”라는 강의에서 잠깐 Stack 자료구조가 무엇인지 설명했었습니다. Collection 도구에는 Stack 자료 구조를 사용할 수 있도록 만들어진 Stack 클래스가 존재합니다.

Stack은 자료구조 강의에서 배우게 되는 재귀와 관련된 것과 굉장히 연관됩니다. 또한 우리가 작성한 코드 명령어도 결국엔 Stack 구조를 이용하여 실행합니다. 추가로 연산자 우선순위가 있는 사칙연산 계산기를 만들 때 사용됩니다.

Stack은 나중에 들어간 것이 가장 먼저 나온다는 LIFO(Last-In-First-Out)의 성질을 가지고 있습니다. Stack은 상자로 비유되며 상자에 데이터를 밀어 넣는다(push) 와 꺼낸다(pop) 이라는 용어를 사용합니다.

우리가 상자에 물건을 넣고 꺼낼 때도 가장 먼저 들어간 것을 꺼내기 위해서는 맨 위에 있는 물건부터 꺼내야 아래에 있는 물건을 꺼낼 수 있습니다.

ㅤ

예시

우리 도전자님이 표의 순서대로 강의를 들었다고 가정합니다. 만약에 최근에 들었던 강의 순서대로 세 개만 보여줘야 한다면 어떻게 하면 될까요?

가장 간단한 방법은 Stack을 이용하는 것입니다. 강의를 시청할 때마다 강의의 이름을 Stack에 넣으면 됩니다.

강의를 시청한 순서에 대한 기준(날짜, 시간)이 없다면 최근에 들었던 강의를 출력하기 가장 편한 방법입니다.

ㅤ

Stack<E>

Stack은 Vector 클래스를 상속하여 만들어졌습니다. Vector 클래스는 ArrayList와 유사하나 Thread 동기화를 위해 synchronized 키워드가 선언되어 있습니다.

NOTE! Thread와 동기화, synchronized는 스레드 파트에서 배웁니다.

아주 간단하게 생각하면 ArrayList와 유사한 것으로 Stack 클래스를 만들었다고 보면 됩니다.

ㅤ

특징

1. LIFO 성질을 갖는다

2. Thread-Safe 하다

ㅤ

사용용도

1. 재귀적인 코드를 비재귀적으로 바꿀 때 사용된다.

2. 계산기를 만들 때 사용된다.

3. 최근에 저장된 데이터를 나열할 때 사용된다.

ㅤ

Stack의 생성

import java.util.Stack;

Stack<E> stack = new Stack<>();

ㅤ

Stack의 데이터 삽입

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("강의A");
stack.push("강의E");
stack.push("강의B");
stack.push("강의D");
stack.push("강의C");

stack에서 데이터를 밀어 넣는 방법은 push(data) 메서드를 이용합니다.

ㅤ

Stack 데이터 꺼내기

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("강의A");
stack.push("강의E");
stack.push("강의B");
stack.push("강의D");
stack.push("강의C");

String lessonName1 = stack.pop();
// 강의C
String lessonName2 = stack.pop();
// 강의D
String lessonName3 = stack.pop();
// 강의B

stack.pop() 메서드 사용 시 최근에 저장된 데이터를 가장 먼저 반환받습니다. stack.pop()의 특징은 데이터를 꺼낼 때 Stack에 저장된 기존 데이터는 삭제된다는 점입니다. 상자에서 물건을 꺼내면 상자에 물건이 들어있지 않는 것과 동일합니다. 만약 Stack에 데이터가 존재하지 않을 경우 EmptyStackException이 발생합니다.

ㅤ

Stack의 최상단 데이터 확인

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("강의A");
stack.push("강의E");
stack.push("강의B");
stack.push("강의D");
stack.push("강의C");

String lessonName1 = stack.peek();
// 강의 C
String lessonName2 = stack.peek();
// 강의 C

stack.pop() 메서드를 사용하면 기존 데이터가 삭제된다는 점이 있었습니다. 단순히 Stack의 최상단 데이터를 확인하려면 stack.peek() 메서드를 이용하여 확인할 수 있습니다.

ㅤ

Stack에 저장된 데이터의 확인 및 순서 확인

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("강의A");
stack.push("강의E");
stack.push("강의B");
stack.push("강의D");
stack.push("강의C");

int sequence1 = stack.search("강의A");
// 5
int sequence2 = stack.search("강의E");
// 4
int sequence3 = stack.search("강의B");
// 3
int sequence4 = stack.search("강의D");
// 2
int sequence5 = stack.search("강의C");
// 1

int search = stack.search("강의Z");
// -1

Stack에 데이터가 존재하는지 확인하기 위해 stack.search(data) 메서드를 사용할 수 있습니다. 반환 값은 검색한 데이터가 존재하지 않는다면 -1을 반환하며 존재한다면 stack.pop() 메서드를 호출했을 때 몇 번째순서로 나오는지 확인할 수 있습니다.

ㅤ

Stack이 비어있는지 확인

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("강의A");
stack.push("강의E");
stack.push("강의B");
stack.push("강의D");
stack.push("강의C");

while (!stack.isEmpty()) {
    System.out.println(stack.pop());
}

만약에 Stack에 데이터가 존재하지 않는 상황에서 stack.pop() 메서드를 호출하면 EmptyStackException이 발생합니다. 그러므로 stack.pop() 호출 시 Stack에 데이터가 존재하는지 확인해야 합니다. 데이터 존재 여부를 확인하는 방법은 stack.isEmpty() 메서드를 사용하면 됩니다.

데이터가 존재하지 않을 경우 true, 데이터가 존재할 경우는 false를 반환합니다.

ㅤ

Stack에 저장된 데이터의 크기

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("강의A");
stack.push("강의E");
stack.push("강의B");
stack.push("강의D");
stack.push("강의C");

int size = stack.size();
// 5

Stack 클래스는 Vector 클래스를 상속했으며, Vector 클래스는 List 인터페이스를 구현하므로 stack.size() 메서드를 사용할 수 있습니다.

ㅤ

2. Queue

Queue라는 자료구조는 먼저 들어간 것이 가장 먼저 나온다는 FIFO(First-In-First-Out)의 성질을 가지고 있습니다. Queue는 보통 대기열로 비유됩니다. 버스 정류장에서 버스를 타기 위해서는 순서대로 줄 서서 기다려야 합니다. 그리고 가장 먼저 기다린 사람이 가장 먼저 버스에 탑니다.

ㅤ

예시

국가 기관이나 기업에 전화를 걸었을 때 “상담자가 바쁘니 잠시만 기다려주시기 바랍니다” 라는 음성 메세지를 들어본 적이 있을 겁니다. 그리고 “약 23명의 대기자가 있으며 약 20분 정도 걸릴 것으로 예상됩니다” 라는 메세지도 들어본 적이 있을 겁니다. 전화 상담은 전화가 걸려온 순서대로 처리되어야 합니다. 만약에 마지막에 걸었던 사람이 가장 먼저 상담원이 배정된다면 이전부터 전화를 기다리고 있는 사람들은 굉장히 화가 날 것입니다.

Queue는 대기열로 주로 사용되는 자료구조입니다.

ㅤ

Queue<E> - interface

Queue의 자료구조를 이용할 수 있도록 만들어진 클래스는 Queue Interface를 구현해야 합니다.

Queue 인터페이스를 구현한 클래스는 LinkedList, ArrayDeque 클래스가 있습니다.

ㅤ

특징

1. 일반적으로 FIFO 성질을 갖는다

ㅤ

사용용도

1. 작업의 순차적인 처리가 필요할 떄 사용된다

2. 저장된 데이터를 저장된 순서대로 꺼내야 할때 사용된다.

ㅤ

Queue의 생성

import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayDeque;

// LinkedList를 이용한 Queue
Queue<E> queue = new LinkedList<>();

// ArrayDeque를 이용한 Queue
Queue<E> queue = new ArrayDeque<>();

Queue를 생성하는 방법은 다음과 같습니다. LinkedList, ArrayDeque, 클래스를 이용하면 됩니다.

다만 LinkedList를 이용하는 것이 좋습니다. 그 이유는 이전 강의에서 설명드렸지만 LinkedList는 가장 앞이나 뒤의 데이터를 삭제하는데 쉬우며, Queue에서 데이터를 꺼낼 때도 가장 앞의 데이터를 꺼내기 때문입니다. 또한 배열처럼 중간 데이터에 접근할 이유가 없기 때문입니다. ArrayDeque는 배열을 이용하여 Queue를 만듭니다.

ㅤ

Queue의 데이터 삽입

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();
queue.add("전화A");
queue.add("전화E");
queue.add("전화B");
queue.add("전화D");
queue.add("전화C");

Queue에서 데이터를 저장하는 방법은 queue.add(data) 메서드를 이용합니다.

ㅤ

Queue 데이터 꺼내기

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();
queue.add("전화A");
queue.add("전화E");
queue.add("전화B");
queue.add("전화D");
queue.add("전화C");

String data1 = queue.poll();
// 전화A
String data2 = queue.poll();
// 전화E
String data3 = queue.poll();
// 전화B

queue.poll() 메서드 사용 시 가장 먼저 저장된 데이터를 반환합니다. queue.poll()의 특징은 데이터를 꺼낼 때 Queue에 저장된 기존 데이터는 삭제됩니다.(Stack의 pop과 동일합니다) 만약에 데이터가 존재하지 않는다면 null을 반환합니다.

ㅤ

Queue의 맨 앞 데이터 확인

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();
queue.add("전화A");
queue.add("전화E");
queue.add("전화B");
queue.add("전화D");
queue.add("전화C");

String data1 = queue.peek();
// 전화A
String data2 = queue.peek();
// 전화A
String data3 = queue.peek();
// 전화A

queue.poll() 메서드를 사용하면 기존 데이터가 삭제된다는 점이 있었습니다. 단순히 Queue의 맨 앞 데이터를 확인하려면 queue.peek() 메서드를 이용하여 확인할 수 있습니다.

ㅤ

Queue이 비어있는지 확인

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();
queue.add("전화A");
queue.add("전화E");
queue.add("전화B");
queue.add("전화D");
queue.add("전화C");

boolean isEmpty = queue.isEmpty();

데이터 존재 여부를 확인하는 방법은 queue.isEmpty() 메서드를 사용하면 됩니다.

데이터가 존재하지 않을 경우 true, 데이터가 존재할 경우는 false를 반환합니다.

ㅤ

Queue에 저장된 데이터의 크기

import java.util.Queue;
import java.util.LinkedList;

Queue<String> queue = new LinkedList<>();
queue.add("전화A");
queue.add("전화E");
queue.add("전화B");
queue.add("전화D");
queue.add("전화C");

int size = queue.size();
// 5