자료구조 - Stack, Queue 차이점
자료 구조
Java에서 자료 구조라 함은, 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것.
아래의 자료 구조 중 가장 많이 사용되는 대표적인 Stack, Queue에 대해 알아 보자.
1. Stack // ex)프링글스 통
#1. LIFO (Last In First Out) - 먼저 들어간 데이터가 제일 나중에 나온다.
#2. 데이터는 하나씩 넣고 뺼 수 있다.
#3. 하나의 입출력 방향을 가지고 있다.
#4. 그래프 탐색 중 '깊이우선탐색(DFS)'에 사용된다.
<Stack 생성>
Stack<Integer> stack = new Stack<>(); // int 형 스택
Stack<String> stack = new Stack<>(); // char형 스택<실사용 예제>
브라우저 앞으로 가기, 뒤로 가기
1. 새로운 페이지로 접속할 때, 현재 페이지를 #Prev Stack에 보관
2. 뒤로가기 버튼을 통해 이전 페이지로 돌아갈 때,
현재 페이지를 #Next Stack에 보관, #Prev Stack에 가장 최근에 등록되어 있던 페이지 호출.
3. 앞으로 가기 버튼을 통해 앞서 방문한 페이지로 이동할 때,
#Next Stack에 가장 최근에 등록된 페이지 호출.
4. 마지막으로 현재 페이지를 #Prev Stack에 보관.
<Stack 메서드>
| 메소드 | 기능 | 예시 |
| .push() .add(int) |
데이터 1개씩 추가 / .add()는 int만 가능. |
N.push(); |
| .pop() | 가장 최근에 추가된 데이터 삭제 // | System.out.println( N.pop()); |
| .size() | 스택안의 데이터 개수 | System.out.println( N.size()); |
| .peek() | 맨 마지막에 추가된 값 출력 | System.out.println( N.peek()); |
| .clear() | 스택의 모든 데이터 삭제 | N.clear(); |
| .empty() .isEmpty() |
스택이 비었는지 아닌지 boolean 리턴 |
System.out.println( N.empty()); |
| .contains(값) | 스택이 특정 데이터 포함 유무 boolean 리턴 |
System.out.println( N.contains(값)); |
| .search(값) | (값)이 뒤에서 몇번째 위치인지 나옴 | System.out.println( stack.search(값)); |
2. Queue // ex) 구멍뚫린 프링글스 통
#1. FIFO (First In First Out) - 먼저 들어간 데이터가 먼저 나온다.
#2. 데이터는 하나씩 넣고 뺄 수 있다.
#3. 두 개의 입출력 방향을 가지고 있다.
#4. 그래프의 넓이 우선 탐색(BFS)에 사용된다.
#5. 중간에 값 추가가 불가능하며, 맨 뒤로만 데이터가 들어올 수 있다.
<Queue 생성>
Queue는 인터페이스라, Stack과는 다르게 자체 객체 선언을 할 수 없고, LinkedList 를 통해 사용 가능하다.
Queue<Integer> q = new LinkedList<>();
<실사용 예제>
프린터에서 여러 문서를 순서대로 인쇄할 때.
1. 문서를 작성하고 출력 버튼을 눌리면, 해당 문서는 인쇄 작업 (임시 기억 장치)Queue에 들어간다.
2. 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄한다.
<Queue 메서드>
| 메소드 | 기능 | 예시 |
| .offer() / .add() | 데이터 추가, 순차적으로 | N.offer(); / N.add(); |
| .poll() / .remove() | 앞쪽부터 데이터 삭제 | N.poll(); / N.remove(); |
| * .remove(값/index) | 값/index 지우며 중복의 경우 앞쪽에 있는 값을 지운다. |
*.remove(값/index) |
| .clear() | 모든 데이터를 지운다. | N.clear(); |
| .size() | Queue 안의 데이터 개수 구함. | System.out.println( N.size()); |
| .peek() | 맨 처음 넣은 값 확인. | System.out.println( N.peek()); |
| is.Empty() | Queue가 비었는지 확인 | N.isEmpty(); / !N.isEmpty(); |
< Stack 과 Queue의 차이점 >
#1. 작동 원리
Stack : LIFO 원칙으로 책을 쌓는 원리와 같이 가장 마지막에 삽입된 데이터가 먼저 제거된다는 특성이 있다.
Queue : FIFO 원칙으로 줄을 서는 원리와 같이 가장 먼저 삽입된 데이터가 먼저 제거된다는 특성이 있다.
#2. 구현 방법
Stack : Java에서 Stack은 Vector 클래스를 상속받아 Vector클래스의 모든 메서드 + 고유 메서드를 사용.
Stack은 push()메서드를 사용하여 요소를 추가하고, pop() 메서드를 사용하여 요소를 제거한다.
Queue : Java에서 Queue는 인터페이스이며, LinkedList를 통해 구현할 수 있다.
Queue는 add() or offer() 메서드를 사용하여 요소를 추가, remove() or poll() 메서드로 요소를 제거한다.
#3. 사용 사례
Stack : 재귀 알고리즘, 실행 취소/재실행, 페이지 이동(앞으로 가기, 뒤로 가기), 메모리 관리
Queue : 데이터 스트림 처리, 시뮬레이션, 캐싱, 작업 스케줄링, 프린트 큐