스택과 큐 Stack & Queue

스택은 가장 마지막에 들어간 데이터가 가장 첫 번째로 나오는 성질 (LIFO, 후입선출)을 가진 자료구조입니다. 반면에, 큐는 처음에 저장한 데이터를 가장 먼저 꺼내는 성질 (FIFO, 선입선출)을 가진 자료구조입니다. 

 

스택은 바닥이 있고, 큐는 바닥이 없는 통이라고 생각하면 편합니다. 그렇다면 스택과 큐를 구현하기 위해서는 어떤 Collection을 사용하는 게 좋을까요?

 

순차적인 스택은 ArrayList와 같은 배열기반이 적합합니다. 반면에, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적입니다. 그렇기 때문에 데이터의 삽입/삭제가 효율적인 연결 리스트(LinkedList)를 사용해 구현합니다.

 

<스택 메서드>

스택 메서드	설명
boolean empty()	스택이 비었는지 알려줌
Object peek()	스택의 맨 위 객체를 알려줌 (꺼내는 건 아님)
Object pop()	스택의 맨 위 객체를 꺼냄 (꺼낼 값이 없으면 EmptyStack Exception이 발생하므로 처음에 push(0)을 사용해 미연에 방지할 수 있음)
Object push(Object item)	스택에 객체(item)을 저장
int Search(Object o)	스택에서 주어진 객체(o)를 찾아서 그 위치를 반환. 찾지 못하면 -1 반환. (배열과 달리 위치는 1부터 시작)

 

<큐 메서드>

큐 메서드	설명
boolean add(Object o)	지정된 객체를 큐에 추가. 성공하면 true 반환. 저장공간이 부족하면 IllegalStateException 발생
Object remove()	큐에서 객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어옴. peek과 달리 큐가 비어있으면 NoSuchElementException 발생
boolean offer(Object o)	큐에 객체 저장.
Object poll()	객체를 꺼냄. 비어있으면 null 반환
Object peek()	데이터 값을 읽기만 함. 비어있으면 null 반환

 

스택과 큐 활용도

스택 : 수식계산, 수식괄호검사, undo/redo, 웹 브라우저 방문 기록, 재귀함수

큐 : 최근사용문서, 인쇄작업 대기목록, 버퍼, CPU 작업을 기다리는 프로세스, 스레드 행렬, bfs, 캐시, 네트워크 접속을 기다리는 행렬