Stack과 Queue

1. Stack

 

스택은 밑 부분이 막혀 있는 통 구조로 단방향으로만 데이터를 교환한다.

즉, 마지막에 저장한 데이터를 가장 먼저 빼내는 LIFO(Last In First Out) 방식으로 되어 있다.

 

예를 들어 스택에 0, 1, 2 순서로 데이터를 저장(push)했다면,

꺼낼 때(pop)는 2, 1, 0 순으로 빼오게 되는 것이다.

스택 구조에서는 순서가 바뀌게 되는 것을 주의해야 한다.

 

자바에서는 스택을 클래스로 제공하고 있기 때문에 그 자체로도 구현이 가능하다.

 

class StackTest {

	Stack<Integer> stack = new Stack<Integer>();
	    
	stack.push(0);
	stack.push(1);
	stack.push(2);
        
	while(!stack.empty()) {
    	System.out.println(stack.pop());         // 2, 1, 0
	}
    
    for(Integer integer : stack) {
	    System.out.println(integer);             // 0, 1, 2
	}
}

 

 

2. Queue

 

큐는 스택과 달리 위 아래 모두 뚫려있는 구조로,

가장 처음 저장한 데이터가 가장 먼저 빠져나가는 FIFO(First In First Out)을 보인다.

 

예를 들어 큐에 0, 1, 2 데이터를 저장(offer)한다면,

해당 데이터를 빼왔을 때의 순서도 0, 1, 2 순으로 추출(poll)된다는 것이다.

 

자바에서 큐는 인터페이스로 정의되었기 때문에 큐를 구현한 구상 클래스를 이용해야 한다.

그 중 앞서 정리한 LinkedList 로 구현해보면 다음과 같이 할 수 있다.

class QueueTest {
	
    Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.offer(0);
		queue.offer(1);
		queue.offer(2);
		
		while(!queue.isEmpty()) {
			System.out.println(queue.poll());        // 0, 1, 2
		}
}

 

 

3. Deque(Double-Ended Queue)

 

디큐는 큐의 변형 버전으로 양방향에서 데이터를 저장하고 삭제가 가능하다.

메서드	Deque	Queue	Stack
끝에 저장	offerLast()	offer()	push()
끝에서 삭제	pollLast()	-	pop()
앞에 저장	offerFirst()	-	-
앞에서 삭제	pollFirst()	poll()	-
앞 요소 읽기	peekFirst()	peek()	-
끝 요소 읽기	peekLast()	-	peek()