[자료구조] 스택(Stack) & 큐(Queue)

스택(Stack)

선형 자료구조의 일종으로, 
가장 나중에 들어온 것이 가장 먼저 나온다. LIFO (Last In First Out, 후입선출)

 

 

 

※ 스택(stack)이란, 쌓아 올린다는 것을 의미한다.

따라서 스택 자료구조라는 것을 책을 쌓는 것처럼 

차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

 

 

---

 

스택의 특징

같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, 
top으로 정한 곳을 통해서만 접근할 수 있다.
즉, 스택의 경우 자료의 삽입과 삭제는 한 곳(top)에서만 이루어지게 된다.

스택은 시간 순서에 따라 자료가 쌓여서
가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가졌다.

만약 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 
스택 언더플로우(Stack Underflow)가 발상하고, 

반대로 스택이 꽉 차있을 때 자료를 넣으려고 하면 
스택 오버플로우(Stack Overflow)가 발생하게 된다.

 

 

 

스택의 활용 예시

스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

 

- push() : 데이터 삽입
- pop() : 데이터 삭제
- isEmpty() : 비어있는 지 확인
- isFull() : 꽉차있는 지 확인

 

 

 

---

 

큐(Queue)

선형 자료구조의 일종으로, 
가장 먼저 들어온 것이 가장 먼저 나온다. FIFO (First In First Out, 선입선출)

 

※ 참고로 Java Collection에서 Queue는 인터페이스다.

이를 구현하고 있는 PriorityQueue 등을 사용할 수 있다.

 

 

 

※ Queue의 사전적 의미는 

(무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미한다.

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

선입선출(FIFO, First in first out) 방식의 자료구조를 말한다. 

 

 

---

 

큐의 특징

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리
큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

이때 삭제연산만 수행되는 곳을 프론트(front),
삽입연산만 이루어지는 곳을 리어(rear)라고 정하여 각각의 연산 작업만 수행된다.

이때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue), 
프론트에서 이루어지는 삭제연산을 디큐(deQueue)라고 부른다.

 

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성
• 접근방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

 

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

리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

 

 

 

큐의 활용 예시

주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색 (BFS) 구현
• 캐시(Cache) 구현

 

 

---

 

스택과 큐의 Java 코드 및 실행 결과

 

[실행 코드]

import java.util.*;

public class StackQueue {

	public static void main(String[] args) {
		
		Stack<String> stack = new Stack<>();
		Queue<String> queue = new LinkedList<>();
		
		stack.push("0");
		stack.push("1");
		stack.push("2");
		
		queue.offer("0");
		queue.offer("1");
		queue.offer("2");
		
		System.out.println("--- Stack ---");
		while(!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
		
		System.out.println("--- Queue ---");
		while(!queue.isEmpty()) {
			System.out.println(queue.poll());
		}

	}

}

 

 

[실행 결과]

 

 

 

---

출처

• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#stack-and-queue
• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Stack%20%26%20Queue.md
• https://devuna.tistory.com/22
• https://cocoon1787.tistory.com/691