자바 자료구조 : Stack과 Queue

스택과 큐

배열에서 발전된 형태의 자료구조

스택과 큐의 구조는 비슷하지만 처리 방식은 다르다.

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

public class StackQueueAlgorithm {

	public static void main(String[] args) {
		Stack st = new Stack();
		// Queue 인터페이스의 구현체인 LinkedList를 사용
		Queue q = new LinkedList(); // 
		
        // Stack에 객체를 하나씩 추가
		st.push("0");
		st.push("1");
		st.push("2");

        // Queue에 객체를 하나씩 추가
		q.offer("0");
		q.offer("1");
		q.offer("2");
		
		System.out.println("= Stack =");
		while(!st.empty()) {
			System.out.println(st.pop()); // 스택에서 요소 하나를 꺼내서 출력
		}

		System.out.println("\n"+"= Queue =");
		while(!q.isEmpty()) {
			System.out.println(q.poll()); // 큐에서 요소 하나를 꺼내서 출력
		}		
	}
}

스택과 큐에 각각 "0", "1", "2"를 같은 순서로 넣고 꺼내었을 때 결과가 다르다.

= Stack =

2

1

0

 

= Queue =

0

1

2

큐는 먼저 넣은 것이 먼저 꺼내지는 구조이기 때문에 넣을때와 같은 순서로 출력되고,

스택은 먼저 넣은 것이 나중에 꺼내지는 구조로 넣을 때의 순서와 반대로 꺼내지며 출력되는 자료구조이다.

 

자바에서는 스택을 Stack 클래스로 구현하여 제공하고 있지만 큐는 Queue 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 하지만 Queue 인터페이스를 구현한 클래스들이 있어서 이들 중 하나를 선택해 사용하면 된다.

 

스택 활용 예 : 수식 계산, 수식괄호 검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

큐의 활용 예 : 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)

 

---

스택(Stack)

삽입과 삭제 연산이 후입선출(LIFO : Last in First out)로 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 자료구조이다.

후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다. 양 옆과 바닥이 막혀 있어서 한 방향으로만 뺄 수 있는 구조로 이해할 수 있다.

 

스택은 깊이 우선 탐색(DFS : Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적이다. 후입선출 은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.

 

위치 

• top : 삽입과 삭제가 일어나는 위치를 뜻한다.

연산

• push : top 위치에 새로운 데이터를 삽입하는 연산이다.
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다. 

Stack st = new Stack();
boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환, pop()과 달리 Stack에서 객체를 꺼내지는 않음 (비었을 때는 EmptyStackException 발생)
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다.(비었을 때는 EmptyStackException 발생)
Oobject push(Object item)	Stack 객체(item)를 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환, 못찾으면 -1을 반환(배열과 달리 위치는 0이 아닌 1부터 시작, 맨위의 요소가 1이다.)

 

 

배열과 스택의 차이

배열에서 값을 삽입/삭제하는데 O(N)의 시간 복잡도가 소요된다.

그렇다면 이런 이동을 최소화하기 위해 배열의 크기가 무한하다는 가정하에 값 맨 뒤에 새로운 값을 삽입하면 된다.

이런 경우엔 다른 값들의 이동이 전혀 존재하지 않기 때문에 O(1)의 시간복잡도를 보인다.

 

즉, 맨 뒤에서 값을 넣고, 빼는 작업은 시간 복잡도가 O(1)이 나온다.

자세히 바라보면 삽입과 삭제 연산이 동일한 곳에서 진행되므로, 결국 스택과 비슷한 구조가 된다.

 

즉 배열에서 삽입과 삭제 연산이 발생하는 장소를 맨 뒤로만 제한한다면 배열을 스택처럼 사용할 수 있다.

삽입에 해당하는 함수 push()와 삭제에 해당하는 함수 pop()은 배열로 다음과 같이 표현할 수 있다.

불가능한 상황에서는 throw exception()을 수행하고, 배열에서 사용 가능한 index 범위는 0에서 maxsize 로 설정한다.

 

재귀와 콜 스택

재귀적으로 호출한 함수는 실행이 되고, 종료가 되면 그 함수를 수행한 지점으로 되돌아간다.

컴퓨터는 함수가 실행되면 함수가 실행되는 지점을 기록해둔다. 그래야 함수가 종료되고 난 후 원래 지점으로 돌아갈 수 있기 때문이다. 재귀함수가 된다면 저장해야 할 지점이 한 두개가 아니기 때문에 기록하기가 어려울 수 있다.

 

그래서 함수 중간 지점을 저장하는 자료구조는 스택이 되어야 할 것이다. 그러면 맨 마지막에 저장했던 복귀 지점을 맨 먼저 실행할 수 있다. 이렇게 함수 실행 과정을 저장하기 위해 사용하는 스택이 콜 스택이다. 

 

 

---

큐(Queue)

삽입과 삭제 연산이 선입선출(FIFO: First in First out)  자료구조

먼저 들어온 데이터가 먼저 나간다 그래서 삽입과 삭제가 양방향에서 이뤄진다.

양 옆만 막혀 있고 위아래로 뚫려 있어서 한 방향으로는 넣고 한 방향으로는 빼는 파이프와 같은 구조이다.

 

큐는 너비 우선 탐색(BFS : Breadth First Search)에서 자주 사용한다.

 

큐 용어

• rear : 큐에서 가장 끝 데이터를 가리키는 영역, 값 추가는 rear에서 이뤄짐
• front: 큐에서 가장 앞의 데이터를 가리키는 영역, 삭제는 큐의 front에서 이뤄짐
• add: rear 부분에 새로운 데이터를 삽입하는 연산
• poll : front  부분에 있는 데이터를 삭제하고 확인하는 연산
• peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산

 

스택과 큐를 구현하기 위해 순차적으로 데이터를 추가하고 삭제하는 스택에서는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하고, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로 추가와 삭제가 쉬운 LinkedList로 구현하는 것이 적합하다.

 

Queue q = new LinkedList(); * Queue
boolean add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true를 반환. 저장공간이 부족하면 IllegalStateException발생
Object remove()	Stack의 맨 위에 저장된 객체를 반환, pop()과 달리 Stack에서 객체를 꺼내지는 않음 (비었을 때는 EmptyStackException 발생)
Object element()	삭제없이 요소를 읽어온다. peek와 달리 Queue가 비었을 때 NodSuchElementException발생
boolean offer(Object o)	Queue에 객체를 저장. 성공하면 true, 실패하면 false를 반환
Object poll()	Queue에서 객체를 꺼내서 반환. 비어있으면 null을 반환
Object peek()	삭제없이 요소를 읽어 온다. Queue가 비어있으면 null을 반환

 

배열과 스택, 그리고 큐와 연결리스트

스택의 경우엔 맨 뒤에서 데이터를 삽입하고 삭제한다면 충분히 O(1)을 만들 수 있다.

큐의 경우, 배열 맨 앞에서 삽입을 하고 맨 뒤에서 삭제를 하거나, 맨 뒤에서 삽입을 하고 맨 앞에서 삭제를 해야한다.

그러나 배열의 맨 앞에서 삭제나 삽입을 진행한다면 무조건 O(N)의 시간 복잡도를 보일 것이다. 따라서 배열을 스택처럼 활용할 수는 있지만, 큐처럼 활용하기에는 무리가 있다. 

 

다만 맨 앞이나 뒤에서 삽입 삭제가 일어날 때 시간복잡도가 항상 O(1)인 연결리스트를 사용하면 된다. 배열 대신 연결리스트를 이용하여 큐를 구현한다면 모든 연산에 대해 시간복잡도를 O(1)만 갖게 만들 수 있다. 스택 역시 연결 리스트를 이용하여 모든 연산에 대해 시간복잡도를 O(1)만 갖게 할 수 있다.

 

큐 활용 방식

큐는 일자로 줄을 서는 경우에 사용될 수 있다. 큐에 들어간 데이터가 상황에 따라 다시 큐에 들어가야 한다면, 이 구조는 다음과 같이 원형으로 그릴 수 있다.