스택과 큐(자료구조)

이번 시간에는 스택과 큐에 대해 정리해보았습니다.

  1. 스택(STACK)

여러 의미로 사용되는 스택은 자료구조에서는 무언가를 쌓는다라는 의미를 갖는 자료구조입니다.

후입선출(後入先出, Last In First Out; LIFO)의 자료구조라고도 불리우며 QUEUE와 달리 먼저 들어온 것이 먼저 나가는 용도로 쓰입니다.

 

스택은 입력은 push, 제거는 pop을 이용합니다.

 

peek는 Top의 위치에 있는 데이터를 확인하는 것이므로 스택으로 데이터를 쌓아 올렸을 때 peek를 사용하면 가장 마지막에 삽입한 데이터가 출력되게 됩니다.

 

즉 쉽게 말해 스택은 일종의 바닥이 막힌 상자라고 볼 수 있습니다. 나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수밖에 없다고 생각하시면 되겠습니다.

 

스택은 힙 영역 메모리에서 일반적인 데이터를 저장하는 스택과 스택 영역 메모리에서 프로그램의 각 분기점에 변수와 같은 정보를 저장하기 위한 스택이라는 두 가지 의미로 사용될 수 있므로 유의해야 합니다.

 

그리고 이것도 종류를 나눌 수 있는데,

 

Ascending stack VS Descending stack
Empty stack VS Full stack

 

로 나뉩니다.

 

예제를 통해 살펴보겠습니다.

 

Stack<String> stack = new Stack<String>();
	stack.push("hEO");
	stack.push("JEEN");
	stack.push("sung");
	System.out.println(stack.toString());
	System.out.println(stack.size());
	System.out.println(stack.pop());
	System.out.println(stack.toString());
	System.out.println(stack.size());
}
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
[hEO, JEEN, sung]
3
lee
[hEO, JEEN]
2

 

처음에 데이터를 입력할 때 3개의 데이터를 입력했으므로 이 스택의 크기는 3입니다. 그리고 pop을 이용하여 데이터 제거를 한 것은 가장 마지막에 넣은 데이터가 삭제되는 것이므로 sung을 제외한 hEO와 JEEN만 출력되는 것을 확인할 수 있습니다.

 

 

  2. 큐(QUEUE)

선입선출(先入先出, First In First Out; FIFO)의 자료구조로서 대기열이라고도 합니다.

 

Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미합니다.

 

데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back이라고 한다)에 있고, 데이터가 나가는 위치는 가장 앞(Front라고 한다)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 됩니다.

 

큐에는 우선순위 큐, 원형 큐 등의 베리에이션이 존재합니다. 입력 동작은 Enqueue, 출력 동작은 Dequeue라고도 합니다

보통의 배열을 사용해서 큐를 구현하면 Enqueue와 Dequeue을 할 때마다 계속 데이터가 앞으로 밀려나는 문제가 생기는데(앞쪽은 채워지고 뒤쪽은 빠져나가므로), 이를 해결하기 위해 원형 버퍼를 사용합니다. 시작 부분과 끝 부분을 포인터로 지정한 뒤 Enqueue와 Dequeue를 하는 형태 대신 가득찰 때와 비어있을 때 포인터가 같은 위치를 지정하기 때문에 이를 해결하기 위해 한 공간을 비워놓아야 합니다.

 

연결 리스트를 사용하면 배열에 비해 매우 쉽게 구현이 가능합니다.

STL에는 선형 큐가 이미 알고리즘으로 구현되어 있지만, STL의 알고리즘을 이용해 원형 큐를 구현하는 것은 사실 힘듭니다.

 

원형 큐

큐를 위해 배열을 지정해 놓고 큐를 쓰다보면 배열의 앞부분이 비게된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐입니다.

 

데크

 

 

일반적인 큐는 뒤에서만 삽입이 이루어지고 앞에서만 인출이 가능한 데 비해, 데크는 양쪽에서 모두 삽입/인출이 가능합니다.

 

어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용됩니다.

서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로도 많이 사용되고 있습니다.

 

 

코드 구현

package Stack;

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

public class QueueExample {

public static void main(String[] args) {
	Queue<Message> mq = new LinkedList<Message>();
	
	//객체 저장
	mq.offer(new Message("sendMail", "heo"));
	mq.offer(new Message("sendSMS", "jeen"));
	mq.offer(new Message("sendKakaotalk", "sung"));
	
	while(!mq.isEmpty()) {
		//mq에서 한 개의 메세지 꺼내기
		Message m = mq.poll();
		switch(m.command) {
		case "sendMail":
			System.out.println(m.to + "님에게 메일을 보냅니다.");
			break;
		case "sendSMS":
			System.out.println(m.to + "님에게 sms 보냅니다.");
			break;
		case "sendKakaotalk":
			System.out.println(m.to + "님에게 카카오톡을 보냅니다.");
			break;
		}
	}
}

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
heo님에게 메일을 보냅니다.
jeen님에게 sms 보냅니다.
sung님에게 카카오톡을 보냅니다.