스택(Stack)과 큐(Queue)

스택(Stack)

스택은 "쌓다"는 의미입니다. 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다.
스택은 후입선출(Last In First Out, LIFO) 구조입니다.
 
"데이터를 위로만 담을 수 있는 바구니"라고 생각하면 조금 감이 오시지 않을까 합니다.
 

스택은 같은 크기의 자료를 정해진 한 방향으로만 입력, 저장, 삭제가 가능합니다.
이때 스택 구조의 제일 윗부분을 가르키는 것을 top이라고 하며, 가장 최근의 들어온 데이터를 의미합니다.
 
스택의 자료를 빼낼때도 탑의 가장 위층에서부터 하나씩 제거합니다. 즉 입력이 들어왔던 방향으로 데이터가 리턴됩니다.
 
 

스택의 자바 주요 메서드

Boolean empty(): 스택이 비어있는지 확인
peek(): 스택의 최상단 데이터를 삭제하지 않고 해당 데이터를 반환
pop():  스택의 최상단 데이터를 삭제하고 해당 데이터를 반환
push(E item): 스택의 최상단 부분에 데이터를 입력
int search(object o): 스택의 최상단에서부터 찾고자 하는 데이터가 몇번째에 존재하는지 반환
 
 

스택의 활용 예시

- 웹 브라우저 뒤로가기
- 실행 취소(undo)
- 역순 문자열 만들기
- 후위 표기법 계산
 
 

큐(Queue)

큐는 "줄을 서서 기다리는 것"을 의미합니다.
 
먼저 들어온 것이 먼저 나가는 선입선출 구조(First In First Out, FIFO)를 가지고 있습니다.

큐는 파이프와 같이 양방향 입구로, 한 쪽에선 데이터의 입력만 이루어지고 다른 쪽에서는 데이터의 출력만 이루어지는 구조입니다.
이때 가장 먼저 입력된 데이터를 가르키는 것을 프론트(Front)라고 하며, 프론트에서 이루어지는 삭제연산을 디큐(Dequeue)라고 합니다.
가장 최근에 입력된 데이터를 리어(rear)라고 하며, 리어에서는 삽입 연산만 진행합니다. 이것을 인큐(Enqueue)라고 부릅니다.
 

큐의 자바 주요 메서드

Boolean add(): 큐의 최끝단에 데이터 삽입하고 true 반환, under/overflow발생 시 예외 발생
element(): 큐의 제일 앞쪽 데이터를 삭제하지 않고 해당 데이터를 반환
Boolean offer(E e):  큐의 최끝단에 데이터 삽입하고 true 반환, under/overflow발생 시 예외 발생
peek(): stQueue의 제일 앞쪽 데이터를 삭제하지 않고 해당 데이터를 반환, 비어있으면 null 반환
poll(): stQueue의 제일 앞쪽 데이터를 삭제하고 해당 데이터를 반환, 비어있으면 null 반환
remove(): stQueue의 제일 앞쪽 데이터를 삭제하고 해당 데이터를 반환, under/overflow발생 시 예외 발생

 

큐의 활용 예시

- 캐시
- 대기열 순서와 같은 우선순위의 작업 예약 등
- 서비스 센터의 대기시간
- 프로세스 관리
 
 
참고
https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

 
https://ontheway.tistory.com/23

[자료구조] 추상 자료형(Abstract  Data Type, ADT)이란? (feat. 스택 & 큐)