Stack
특징
1. LIFO(Last In First Out)
= FILO(First In Last Out)
= 선입후출
-> 입력과 출력이 한 방향
2. 데이터는 하나씩 넣거나 뺄 수 있다.
push: 데이터 넣기pop: 데이터 꺼내기
활용
- 실행 취소
- 페이지 뒤로가기, 앞으로 가기
- 수식 괄호 검사
- 역순 문자열 만들기
- DFS(깊이 우선 탐색)
Stack의 특성 상, 마지막 데이터를 쉽게 빼낼 수 있어 마지막 기록, 최근 기록 등을 저장할 때도 사용된다.
조회에 강점을 갖는 자료 구조들이 많기 때문에, 데이터 순회, 조회 시에는 stack을 사용하지 않는다.
브라우저의 뒤로 가기, 앞으로 가기 기능
- prev stack
- current stack
- next stack
1. 새로운 페이지로 접속
- 현재 페이지를 prev stack으로
- next stack을 비우기(clear)
2. 뒤로 가기
- current 페이지를 next stack으로
- prev stack에서 pop한 값을 current stack으로
3. 앞으로 가기
- current 페이지를 prev stack으로
- next stack에서 pop한 값을 current stack으로
구현
자바에서는 Stack을 Class로 제공한다.
따라서 다음과 같이 선언해서 사용하면 된다.
Stack<String> stack = new Stack<>();자료구조는 데이터를 다루는 구조 자체를 뜻하므로, 구현하는 방식에는 제약이 없다.
따라서 직접 사용자 정의 데이터 타입을 구현하여 Stack을 사용해도 된다.
Stack은 배열, ArrayList, LinkedList로 모두 구현이 가능하다.
하지만 각각의 장단점이 있다.
- 배열: 스택은 크기가 한정되어 있지 않은데, 배열은 크기가 정해져 있다는 단점이 있다. 즉 유동적으로 할당이 불가하다.(스택에 삽입/삭제 시에 크기를 늘린 새 배열을 만들어줘야 한다.)
즉, 배열으로 구현하는 것은 쉽지만 좋은 방법은 아니다. - LinkedList: 크기가 한정되지 않으며, 삽입/삭제가 용이하다. 배열보다 데이터 조회가 오래 걸리지만, stack에서는 조회를 주로 사용하진 않기 때문에 큰 문제는 없다!
따라서 Stack은 LinkedList로 구현하는 것이 더 좋다.
Queue
특징
1. FIFO(First In First Out)
= 선입선출
= LILO(Last In Last Out)
=> 입력과 출력의 방향은 다르고, 고정된 2개의 입출력 방향을 가지고 있다.
2. 데이터는 하나씩 넣거나 뺄 수 있다.
enqueue: 데이터 넣기dequeue: 데이터 꺼내기
활용
Queue는 주로 데이터가 입력된 순서대로 처리할 때 사용된다.
ex) BFS(너비 우선 탐색)
프린터
- 우리가 어떤 문서를 출력하고자 할 때,
출력하기버튼을 누른다. - 해당 문서는 임시 기억 장치의 Queue에 들어간다.
- 프린터는 Queue에 들어온 문서를 순서대로 인쇄한다.
프린터처럼, I/O와 데이터를 주고 받을 때, cpu에 비해 I/O는 현저히 느리다.
즉 장치들 사이에 속도의 차이가 존재하게 되고, 이를 극복하기 위해서 임시 기억 장치의 자료구조로 Queue를 사용하고 이를 버퍼라고 부른다.
cpu는 중요한 리소스로, cpu를 효율적으로 사용하는 것이 컴퓨터에서 매우 중요하다.
따라서 cpu는 빠른 속도로 buffer에 인쇄할 문서를 넣어두고, 프린터를 기다리지 않고 해야할 다른 작업을 수행한다.
프린터는 작업이 오래 걸리는데, buffer에서 데이터를 받아와 cpu와 독립적으로 작업을 수행한다.
버퍼링
유튜브와 같은 동영상 스트리밍 앱을 사용하다보면, 버퍼링이 자주 걸린다.
이는 동영상을 재생하는데 충분한 데이터가 모이지 않았기 때문이다.
버퍼링이 걸리는 동안, 버퍼에 동영상 data를 모으고 동영상을 재생하기에 충분한 양이 데이터가 모였을 때, 동영상이 재생된다.
구현
Queue는 stack과 다르게, interface이다.
클래스가 아니기 때문에 stack처럼 이런 식으로 사용할 수 없다.
Queue<String> queue = new Queue<>();Queue Interface를 구현하는 라이브러리는 크게 ArrayDeque, LinkedList, PriorityQueue가 있다.
보통 자바에서 Queue라고 한다면, LinkedList를 사용한다.
Queue<Integer> q = new LinkedList<>();- 배열: 배열은 크기가 정해져 있기 때문에 Queue에 데이터가 들어오거나 나갈 때, 계속 배열의 크기를 키우거나 줄여야 한다는 단점이 있다. 또한, 선형적인 큐로 구현하면 요소들이 뒤에만 쏠려 있기 때문에 원형 큐로 구현해야 한다.(더 고려해야할 사항이 많고 복잡하다.)
- LinkedList: 크기가 한정적이지 않고, 요소들을 추가, 삭제해줄 때도 링크만 끊으면 되기 때문에 구현하기엔 LinkedList가 적합하다.
Deque
출처: https://www.tutorialandexample.com/deque-in-java
-
Double-Ended Queue의 줄임말
-
Stack과 Queue 모두로 사용할 수 있는 자료구조
-> 양쪽으로 삽입과 삭제를 할 수 있기 때문에 -
자바에서 Deque는 인터페이스로 구현되어 있다.
-> 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스를 사용한다.
Deque<String> deque = new LinkedList<>();[참고]
Queue 구현
