먼저 살펴보도록하자.

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out) 구조로 되어 있고, 큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO( Fist in First Out) 구조로 되어있다.

쉽게 애기하자면 스택은 동전통과 같은 구조로 양 옆과 바닥이 막혀 있어서 한방향으로만 뺼 수 있는 구조이고, 큐는 양옆만 막혀 있고 위아래로

뚫려 있어서 한 방향으로는 넣고 한방향으로는 뺴는 파이프와 같은 구조로 되어 있다.

예를 들어 스택에 0,1,2 의 순서로 데이터를 넣었다면 꺼낼 떄는 2,1,0 의 순서로 꺼내게 된다 즉 넣은 순서와 꺼낸 순서가 뒤집어지게 되는 것이다.

이와 반대로 큐에 0,1,2, 의 순서로 데이터를 넣었다면 꺼낼 떄 역시 0,1,2, 의 순서로 꺼내게 된다. 순서의 변경없이 먼저 넣은 것으 ㄹ먼저 꺼내게 되는 것이다.

그렇다면 스택과 큐를 구현하기 위해서는 어떤 컬렉션 클래스를 사용하는 것이 좋을까?

순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렛션클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫 번쨰 저장된 데이터를 삭제하므로 ArrayList와 같은 배열기반의 컬렛션 클래스를 사용한다면 데이터를 꺼낼 떄 마다 빈공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다,

그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는것이 더 적합하다

Stack 메서드 

boolean empty() -> Stack이 비어있는지 알려준다

Object peek() _> Stack의 맨 위에 저장된 객체를 반환한다. Stack에서 꺼내지는 않는다 , 비어있을떄 null을 반환한다.

Object pop() -> Stack의 맨 위에 저장된 객체를 꺼낸다.

Object push(Object item) Stack에 객체(item)를 저장한다.

int search(Object o) 0> Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환한다. (배열과달리 1부터 시작한다.)

Queue 메서드 (jdk 1.5부터 추가)

Object element() ->삭제없이 저장된 요소를 읽어온다. peek와 다른점은 queue가 비었을떄 Exception을 발생시킨다는 것이다.(pekk()은 null을 반환한다)

boolean offer(Object o) Queue 에 객체를 저장한다. 성공하면 true 실패하면 false를 반환한다.

Object peek() -> 삭제없이 읽어 온다. queue 가 비었을떄 null을 반환한다.

Object poll()-> queue 에서 꺼내온다

Object remove() -> Queue 에서 꺼내온다 . 비어있으면 예외를 발생시킨다.

스택과 큐에 각각 0 1 2 를 같은 순서로 넣고 꺼내었을 떄의 결과가 다른 것을 알 수 있따. 큐는 먼저 넣은것이 먼저 꺼내지는구조 (FIFO)이기 떄문에 넣을 떄와 같은 순서이고 스택은 먼저 넣은 것이 나중에 꺼내지는 구조(LIFO)이기 떄문에 넣을 떄의 순서와 반대로 꺼내진 것을 알 수 있다.

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

Stack은 컬렉션 프레임웍 이전부터 존재하던 것이기 떄문에 ArrayList가 아닌 Vector로 부터 상속받아 구현하였다. Stack의 실제코드를 이해하기 쉽게 약간 수정해서 MyStack을 만들어 보았따. 스택을 자바코드로 어떻게 구현하엿는지 이해하는데 많은 도움이 될 것이다.

Vector에 구현되어 있는 메서드를 이용하기 떄문에 코드도 간단하고 어렵지 않다. 추가적인 설명이 없어도 이해하는데 어려움이 없으리라 생각한다.

지금까지 스택과 큐의 개념과 구현에 대해서 알아보았는데 이제는 스택과 큐를 어떻게 활용할 것인가에 대해서 살펴보자.

우리가 쉽게 찾아볼 수 있는 스택과 큐의 활용 예는 다음과 같다.

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

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

스택과 큐는 실제 프로그래밍에서 번번하게 사용되는 자려구조라고는 하지만 어디에서 사영되었고 막상 어떻게 활용해야할지를 생각해보면 막상 잘 떠오르지 않을것이다.

이제 스택과 큐를 어떻게 활용하는지 감을 잡을 수 있는 예제를 몇가지 학습해보고 나면 스택과 큐를 이해하고 활용하는데 더 많은 도움이 될것이다.

요약 ->

Stack 마지막에 넣은놈이 제일먼저 빠진다 1.2.3. -> 3,2,1

Queue -> 처음에넣은놈이 제일먼저 빠진다 1.2.3 -> 1.2.3

Stack은 오래전부터 사용햇기떄문에 ArrayList대신 Vector(ArrayList 전버전) 을 사용한다

Stack으로 구현가능한 기능 -> 웹페이지 앞으로가기 뒤로가기, 워드프로세서의 undo/redo;

Queue로 구현 가능한 기능 -> 최근사용문서 , 인쇄대기목록