※ 배경지식
Stack<> stack = new Stack();에서 나오는 <>는 추후에 배울 제네릭이라는 개념으로, <Integer>라고 하면 정수형(integer)를 저장할 수 있도록 하는 기능이라고만 알아두자(사실 이게 거의 전부임).
ex) Stack<Float>라고 하면 stack에 float자료형을 저장할 수 있다.
1. Stack
1.1 Stack이란?
Stack이란마지막에 저장한 데이터를 가정 먼저 꺼내는 자료구조로, LIFO(Last In First Out)구조로 이루어져 있는 자료구조이다.
Stack은 아래 그림과 같이 데이터가 입력된 순서대로 쌓이고, 데이터를 꺼낼때는 가장 나중에 입력된 값(가장 최근에 입력한 값)을 꺼내는 구조이다.
stack자료구조는 물건쌓기와 같은 자료구조이다.
이때, stack에 데이터를 넣는 행위를 push라 하고, 데이터를 빼는 행위를 pop이라 한다.
또한, 데이터를 꺼내지 않고 stack에 가장 위에 있는 데이터(top이라고 부른다.)를 보는 것을 peek라고 한다.
1.2 Stack 메소드
java에서는 stack과 관련된 다양한 메소드들이 있다.
isEmpty(): stack이 비어있는지 확인한다. 비어있으면true, 비어있지 않으면false를 반환한다.push(Object item): 객체를 stack에 저장한다.peek(): stack의 맨 위에 있는 데이터를 반환한다.pop(): stack의 맨 위에 있는 데이터를 삭제하고 삭제한 데이터를 반환한다.size(): stack에 들어있는 데이터의 갯수를 반환한다.
1.3 stack 문제
이번에는 직접 stack을 이용한 문제들을 풀어보면서 stack의 사용법을 익혀보자.
https://www.acmicpc.net/problem/10828
정답
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
Stack<Integer> stack = new Stack<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in) );
int N;
String command;
int data;
StringTokenizer st;
N=Integer.parseInt(br.readLine());
int i;
for(i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
command=st.nextToken();// 명령어 입력
switch (command){
case "push":
data=Integer.parseInt(st.nextToken());// 데이터 입력
stack.push(data);// stack에 저장(push)
break;
case "pop":
if(stack.isEmpty()){// stack이 비었을 경우
data = -1;
} else{
data = stack.pop();// stack에서 pop
}
System.out.println(data);
break;
case "size":
System.out.println(stack.size() );// stack 크기 반환
break;
case "empty":
if(stack.isEmpty()){// stack이 비어있는 경우
System.out.println("1");
} else{// stack이 비어있지 않은 경우
System.out.println("0");
}
break;
case "top":
if(stack.isEmpty()){
System.out.println(-1);
} else{
System.out.println(stack.peek());
}
}
}
}
}2. Queue
2.1 Queue란?
Queue란처음 저장한 데이터를 가정 처음 꺼내는 자료구조로, FIFO(First In First Out)구조로 이루어져 있는 자료구조이다.
Queue는 아래 그림과 같이 데이터가 입력된 순서대로 저장이 되며, 데이터를 꺼낼때는 가장 처음 입력된 값을 꺼내는 구조이다.
queue자료구조는 줄서기 같은 자료구조이다.
이때, queue에 데이터를 넣는 행위를 enqueue라 하고, 데이터를 빼는 행위를 dequeue이라 한다.
또한, 데이터를 꺼내지 않고 queue의 가장 앞에 있는 데이터(front라고 부른다.)를 보는 것을 peek라고 한다.
또한, java에서 queue는 LinkedList로 구현되 있기에 LinkedList로 생성을 해야 한다.
Queue<Integer> queue = new LinkedList<>();// 이렇게 연결리스트로 생성해야함!!2.2 queue 메소드
java에서는 queue와 관련된 다양한 메소드들이 있다.
isEmpty(): queue가 비어있는지 확인한다. 비어있으면true, 비어있지 않으면false를 반환한다.offer(Object item): 객체를 queue에enqueue한다.peek(): queue의 맨 앞에 있는 데이터를 반환한다. 만약 queue가 비어있으면null반환poll(): queue의 맨 앞의 데이터를dequeue한다.size(): queue에 들어있는 데이터의 갯수를 반환한다.
2.3 queue 문제
이번에는 직접 queue를 이용한 문제들을 풀어보면서 queue의 사용법을 익혀보자.
https://www.acmicpc.net/problem/2164
정답
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N;
Queue<Integer> que = new LinkedList<>();
N=Integer.parseInt(br.readLine() );
int i;
for(i=1; i<=N; i++){
que.offer(i);// 카드 queue에 쌓기
}
while(que.size()>1){
que.poll();// 카드 버리기
que.offer(que.poll());// 또 카드 한장 뽑고(버리고) 맨 뒤에 넣기
}
System.out.println(que.poll());// 마지막 카드
}
}위 문제는 queue를 이용하는 문제로, 다음과 같은 과정을 거친다.
- 가장 위에 있는 카드를 한 장 버린다.
- 가장 위에 있는 카드를 밑으로 넣는다.
카드를 쌓는다라는 말에 stack을 사용해야 하는것 같지만, stack은 카드를 꺼낸 위치에 쌓아야 하기 때문에 stack을 사용할 수 없다. 즉, 카드를 꺼내는 위치와 다시 쌓는 위치가 다르므로, stack이 아닌 다른 자료구조를 사용해야 한다.
이것을 queue를 이용하면 다음과 같이 풀 수 있다.
먼저, 아래와 같이 카드를 순서대로 queue에 저장한다.
그 다음으로 맨 위에 있는 카드 한장을 버린다.
그러면 다음과 같이 카드가 남는다.
다음으로 아래와 같이 맨 위에 있는 카드를 밑으로 보낸다.
이 과정을 계속 반복한다.
카드를 눕혀서 다시 과정을 보면 다음과 같다.
카드가 쌓인 상태:
카드 한장이 빠지는 상태:
맨 앞의 카드가 뒤로 이동한 상태:
위 과정을 보면 단지 카드를 눕혔을 뿐인데 queue의 enqueue, dequeue 연산을 함을 알 수 있다.
3. Deque
3.1 Deque란?
Deque란양 방향으로 삽입/삭제가 가능한 자료구조로,Stack과Queue를 합친 자료구조다.
Deque는 아래 그림과 같이 데이터가 양 끝 방향으로 입출력이 가능한 자료구조다.
deque는 덱이라고 읽는다.
참고로 이 덱이 아니다.
이때, deque에 데이터를 넣는 행위를 enqueue라 하고, 데이터를 빼는 행위를 dequeue이라 한다.
또한, 데이터를 꺼내지 않고 데이터를 확인하는 것을 peek라고 한다.
또한, java에서 일반적으로 deque는 LinkedList 혹은 ArrayDeque로 생성을 한다.
Deque<Integer> queue = new LinkedList<>();// LinkedList로 선언
Deque<Integer> queue = new ArrayDeque<>();// ArrayDeque로 선언3.2 Deque 메소드
java에서는 deque와 관련된 다양한 메소드들이 있다.
isEmpty(): deque가 비어있는지 확인한다. 비어있으면true, 비어있지 않으면false를 반환한다.
offerFirst(Object item): 객체를 맨 앞에enqueue한다.offerLast(Object item): 객체를 맨 뒤에enqueue한다.
peekFirst(): deque의 맨 앞에 있는 데이터를 반환한다. 만약 deque가 비어있으면null반환peekLast(): deque의 맨 뒤에 있는 데이터를 반환한다. 만약 deque가 비어있으면null반환
pollFirst(): deque의 맨 앞의 데이터를dequeue한다.pollLast(): deque의 맨 뒤의 데이터를dequeue한다.
size(): deque에 들어있는 데이터의 갯수를 반환한다.
3.3 deque 문제
이번에는 직접 deque를 이용한 문제들을 풀어보면서 deque의 사용법을 익혀보자.
https://www.acmicpc.net/problem/10866
정답
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Deque<Integer> deq = new LinkedList<>();
StringTokenizer st;
String command;
int data;
int N;
/*명령어 횟수 입력*/
N=Integer.parseInt(br.readLine() );
int i;
for(i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
command=st.nextToken();
switch (command){
case "push_front":
data = Integer.parseInt(st.nextToken());
deq.offerFirst(data);
break;
case "push_back":
data = Integer.parseInt(st.nextToken());
deq.offerLast(data);
break;
case "pop_front":
if(deq.isEmpty()){
data = -1;
} else{
data = deq.pollFirst();
}
System.out.println(data);
break;
case "pop_back":
if(deq.isEmpty()){
data = -1;
} else{
data = deq.pollLast();
}
System.out.println(data);
break;
case "size":
System.out.println(deq.size());
break;
case "empty":
if(deq.isEmpty()){
System.out.println("1");
}else{
System.out.println("0");
}
break;
case "front":
if(deq.isEmpty()){
data = -1;
}else{
data = deq.peekFirst();
}
System.out.println(data);
break;
case "back":
if(deq.isEmpty()){
data = -1;
}else{
data = deq.peekLast();
}
System.out.println(data);
break;
}
}
}
}
3.4 stack vs deque
뜬금없이 상관없어 보이는 Stack과 Deque와 비교를 왜 하는지 싶을 것이다.
자바에서 Stack은 자바 초창기때 만들어진 자료구조이다. 또한, 자바에서는 이전 버전과 호환성을 위해 기존의 자료구조를 크게 변경하고 있지 않다.
자바에서 Stack은 Vector라는 오래된 자료구조를 상속받았는데, 이 Vector는 멀티스레드에서 동기화가 진행되는 thread safe한 특징을 갖고 있다.
thread safe란, 멀티스레드(스레드가 여러개 있는 경우)에서 안정적으로 데이터가 동기화가 된다는 뜻이다. 즉, 여러 코드가 스레드로 각각 돌아가는 멀티스레드 환경에서 데이터가 변경이 제대로 이루어질 수 있다는 것이다.
그렇다면, 멀티스레드 환경을 고려해서 vector를 사용하는게 더 좋은게 아닌가 싶지만, 단일 스레드에서도 동일하게 스레드 동기화 과정을 거치기 때문에 필요하지 않는 동작이 생기면서 오버헤드가 발생해 성능이 저하될 수 있다.
뿐만 아니라 Iterator를 사용해 탐색작업을 할때도 get()메소드를 사용시 락이 발생한다.
반멘에 deque는 thread safe하지 않기 때문에 멀티스레드에서는 안전하지 않다. 그러나, stack에 비해 속도가 빠르며, 동기화 데코레이터를 사용할 수 있어 필요에 따라서는 멀티스레드에서도 thread safe하게 동작할 수 있다.
또한 Iterator를 사용시 락이 걸리지도 않기 때문에 자바 공식 문서에서도 되도록이면 stack이 아닌 deque의 사용을 권장하고 있다.
reference:
https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/
https://vanslog.io/posts/language/java/why-use-deque-instead-of-stack/
https://www.baeldung.com/java-deque-vs-stack
