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

 

1. Stack(스택)

- 스택의 사전적인 정의는 '쌓아올림', '무더기'라는 뜻이며, 의미 그대로 자료를 계속 쌓아올라가는 방식으로 데이터를 임시 저장하는 자료구조를 의미한다.

- 스택은 데이터의 입출입이 단 하나의 방향에서만 이루어진다.

- 따라서, 가장 먼저 들어온 데이터가 가장 늦게 사용되고, 가장 나중에 들어온 데이터가 가장 먼저 사용되는 후입선출(Last In First Out) 방식의 자료구조이다.

- 스택에 자료를 쌓아올리는 작업을 푸시(push), 스택에서 자료를 꺼내는 작업을 팝(pop)이라고 한다.

- 스택의 상단을 탑(top), 하단을 (bottom)이라고 한다.

 

※ 대표적인 구현 방식 & 상황 예시

- 웹 브라우저 등에서 뒤로 가기 버튼을 누르면, 현재 페이지 이전으로 돌아간다(history back).

- MS Office의 엑셀, 파워포인트에는 이전 작업으로 돌아가는 '실행 취소' 기능을 통해, 이전 작업으로 백업을 할 수 있다.

 

※ 자바에서 Stack 구현해 보기

import java.util.Stack;

public class StackQueue {
	
	public static void main(String[] args) {		
		Stack<String> st = new Stack<String>();
		st.push("첫번째");
		st.push("두번째");
		st.push("세번째");
		System.out.println("----- Stack -----");
		while(!st.isEmpty()){
			System.out.println(st.pop());
		}
	}
}

// 실행결과
----- Stack -----
세번째
두번째
첫번째

 

 

2. 큐(Queue)

- Queue의 사전적 의미는 '대기 줄'인데, 자료가 일정 순서로 처리되는 자료구조 방식이다.

- 임시 데이터를 저장하는 자료 구조라는 점에서 스택과 동일하나, 가장 먼저 들어온 데이터가 먼저 꺼내지는 선입선출(FIFO) 방식의 자료구조이다.

- 자료가 들어오는 부분을 rear, 자료가 삭제되어 나가는 부분을 front라고 한다.

- 먼저 들어온 원소를 front 원소, 마지막에 들어온 원소를 rear 원소라고 한다.

- 큐에 데이터를 추가하는 것을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다.

 

※ 대표적인 구현 방식 & 상황 예시

- 은행 대기 동선은 먼저 도착한 순서(대기표를 뽑은 순서)대로 업무 처리를 진행한다.

- OS에서 프로세스를 스케줄링 할 때, 먼저 들어온 요청부터 처리하는 방식으로 자원을 할당한다(FIFO).

 

※ 자바에서 Queue 구현해 보기

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

public class StackQueue {
	public static void main(String[] args) {	
		Queue<String> qu = new LinkedList<>();
		qu.offer("첫번째");
		qu.offer("두번째");
		qu.offer("세번째");
		System.out.println("----- Queue -----");
		while(!qu.isEmpty()){
			System.out.println(qu.poll());
		}
	}
}

// 실행결과
----- Queue -----
첫번째
두번째
세번째

지금까지 스택과 큐에 대해 알아보았다.

 

감사합니다 : )