[CS] 스택 (Stack), 큐 (Queue)

1. 스택 (Stack)

스택의 정의

 

스택 이란 말 그대로 쌓아 올린다는 것을 의미한다

따라서 스택 자료구조라는 것은 책을 쌓는 것 처럼 위로 점점 쌓는 형태의 자료구조를 말한다

 

스택의 특징

- 스택은 위의 그림처럼 같은 구조로 정해진 방향으로만 쌓을 수 있다

- top으로 정한 곳을 통해서만 접근할 수 있다

- top은 가장 위에를 뜻하고 그곳은 가장 최근에 들어온 자료가 있다는걸 의미한다

- 스택에서는 삭제할 때도 top을 통해서만 가능하다

- 스택에서 삽입하는 연산을 push, 삭제하는 연산을 pop이라고 한다

 

따라서 스택은 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가진다

이를 후입선출 (LIFO, Last In First Out) 구조 라고한다

 

비어있는 스택에서 원소를 추출하려고 할 때를 stack underflow 라고한다

스택이 넘치는 경우를 stack overflow라고 한다

 

스택의 활용 예시

- 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다

- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다

- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다

- 후위 표기법 계산

- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

 

2. 큐 (Queue)

큐의 정의

 

큐란 사전적 의미로 줄(무엇을 기다리는 사람, 자동차 등의),

혹은 줄을 서서 기다리는 것을 의미한다

즉 은행에서 먼저 온 사람의 업무를 먼저 처리하는 것과 같이

선입선출 (FIFO, First In Frist Out)방식의 자료구조를 말한다

 

큐의 특징

스택처럼 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지지 않고

큐는 한쪽 끝에서 삽입 작업을, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다

이때 삭제 연산만 수행하는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)라 한다

이렇게 정해진 곳에서만 각각의 연산 작업을 수행한다

리어에서 이루어지는 삽입연산을 인큐(enQueue)

프론트에서 이루어지는 삭제연산을 디큐(deQueue)

 

- 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear

- 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성

- 접근방법은 가장 첫 원소와 끝 원소로만 가능

- 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

 

즉 큐에서는 프론트 원소는 가장 먼저 큐에 들어왔던 첫번째 원소가 되는것이고

리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 된다

 

큐의 활용 예시

- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)

- 은행 업무

- 콜센터 고객 대기시간

- 프로세스 관리

- 너비 우선 탐색(BFS, Breadth-First Search) 구현

- 캐시(Cache) 구현

 

3. 스택과 큐의 JAVA 코드 및 실행 결과

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class StackQueue {
	public static void main(String[] args) {
		Stack<String> st = new Stack<>();
		Queue<String> q = new LinkedList<>();

		st.push("0");
		st.push("1");
		st.push("2");

		q.offer("0");
		q.offer("1");
		q.offer("2");

		System.out.println("--- Stack ---");
		while(!st.isEmpty()) {
			System.out.println(st.pop());
		}

		System.out.println("--- Queue ---");
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}