스택과 큐는 프로그래밍이란 개념이 시작될 때부터 사용된 고전적인 자료구조이다.
스택은 선입후출(LIFO), 큐는 선입선출(FIFO)의 구조를 가지고 있다.
스택
스택(Stack) : Last in First Out. 스택에 마지막에 들어온 데이터가 가장 먼저 처리되는 형태의 자료구조
스택은 실생활에서 예를 들면 무거운 상자를 쌓는 것과 같다.
상자를 쌓기 위해 가장 아래에서부터 하나씩 두면서 위로 쌓아나간다. 가장 아래 상자가 필요한 경우 맨 위의 상자부터 순서대로 치워야 맨 아래 상자에 도달할 수 있다.
이와 같이 스택 자료구조에는 데이터를 순서대로 쌓고 가장 마지막에 쌓인 데이터부터 처리하게 되는 자료구조이다.
물론 실제 물리 메모리상에는 위아래로 쌓이진 않고 무작위로 배치되어있지만 가장 처음 들어온 데이터부터 마지막 데이터까지 순서대로 포인터로 가르키고 있다.
스택의 사용처
JVM의 Runtime Data Area(Stack 영역), 재귀함수
스택에 담을 노드
class MyNode {
int item;
Mynode next;
public MyNode(int item, Node next) {
this.item = tiem;
this.next = next;
}
}Java에서 스택(Stack) 사용
선언
import java.util.Stack;
Stack<T> stack(변수명) = new Stack<>();
>> 선언한 자료형만 삽입, 삭제 가능
Stack stack(변수명) = new Stack();
>> 어떤 자료형이든 삽입, 삭제 가능함수(Method)
삽입
stack.push(value);
// Stack에서 제공하는 메서드
// 반환 >> 삽입된 값
stack.add(value);
//Vector에서 제공하는 메서드
// 반환 >> boolean삭제
stack.pop();
// 반환 >> 스택에 가장 마지막에 삽입된 값을 반환하고 스택에서 제거
stack.clear();
// 스택에 저장된 모든 값 제거가장 상단의 값
stack.peek();
// 가장 마지막에 추가된 값을 반환, pop()과 달리 스택에서 제거하지 않는다.empty()
stack.empty();
// 스택이 비어있는지 여부를 boolean 값으로 알려준다.앞으로 Stack 자료형은 사용하지 않는다.
스택은 cpu가 단일 코어였던 시절에 나온 자료형으로, 모든 작업에 잠금(Lock)이 수행되는 Vector라는 자료형을 기반으로 한다.
Vector 클래스는 java version 1.2 가 등장하기 이전부터 있던 오래된 클래스이다. 요즘처럼 멀티 코어 시대에는 심각한 성능 문제가 있으므로 사용하지 않는다.
Vector 클래스의 add 메서드를 사용하였다가 의도치 않는 동작이 실행되면서 오류를 범할 수 있다.
Queue 큐
큐 : First in First Out. 큐에 가장 먼저 삽입된 데이터가 먼저 처리되는 형태의 자료구조
큐는 실생활에서 놀이공원 줄서기라고 생각하면 된다.
가장 먼저 줄을 선 사람부터 놀이기구를 탈 수 있는 개념의 자료구조를 큐라고 한다.
Java에서 큐(Queue) 사용
선언
(1)
import java.util.Queue;
import java.util.LinkedList;
Queue<Integer> queue = new LinkedList<>();
(2)
import java.util.Queue;
import java.util.ArrayDeque;
Queue<Integer> queue = new ArrayDeque<>();큐를 구현하는 자료형으로는 LinkedList 또는 ArrayDeque가 있다.
삽입의 경우에 객체 생성이라는 작업이 수반되는 이유로 ArrayDeque가 LinkedList보다 빠르다.
반면 추출(Poll())의 경우 ArrayDeque보다 Linked가 미세하기 더 빠르거나 비슷하다.
책 186page같은 경우에는 ArrayDeque 사용한다 하고 책 297page에서는 큐에 한에서인지는 모르겠는데 LinkedList를 사용하겠다고 한다. 바본듯
코테용으로는 어떤 걸 사용해도 큰 차이는 없을 것이라고 생각.
자바 알고리즘 인터뷰 책 186page 참조
삽입
queue.offer(value);
>> 문제 상황에서 false return
>> 반환 삽인된 값
queue.add(value);
>> 문제 상황에서 예외 발생
>> 반환 boolean 값삭제
queue.remove();
>> 가장 앞에 있는 값 반환 및 삭제
>> 공백 큐이면 에외 발생
queue.poll();
>> 가장 앞에 있는 값 반환 및 삭제
>> 공백 큐이면 null 반환
queue.clear();
>> 큐의 모든 값을 삭제한다.Queue의 front 값 조회
queue.peek();
>> 큐의 front에 있는 값 반환. 삭제는 하지 않는다.
>> 공백 큐이면 null 반환
queue.element();
>> 큐의 front에 있는 값 반환. 삭제는 하지 않는다.
>> 공백 큐이면 예외 발생