Stack과 Queue

스택과 큐 (Stack & Queue)

 

 

- 스택(Stack) : LIFO 구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.

스택은, 밑이 막힌 상자처럼 되어있다.
Last In First Out 구조이다.
먼저들어간게 제일 마지막에 나오고, 제일 마지막에 넣은게 제일 처음 나온다.

스택에서는 저장하는 것을 push, 추출하는 것을 pop라고 한다.

데이터 1, 2, 3, 4, 5가 있을 때, 이것의 순서를 반대로 뒤집고 싶다면,
스택에 넣었다가 빼면, 5, 4, 3, 2, 1로 나온다.

 

 

 

- 큐(Queue) : FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.

큐는 위아래가 뚫려있다.
데이터 흐름이 줄서기와 똑같다.
First In First Out구조이다.
먼저 들어간게 제일 먼저나오고, 마지막에 넣은게 제일 마지막에 나온다.

큐에서는 저장하는 것을 offer, 추출하는 것을 poll이라고 한다.

 

그러면, 스택을 구현하려면 배열과 링크드리스트중에 어떤것을 사용하는게 좋을까?
둘다 가능하긴 할테지만, 어느것이 더 효율적일까?

스택은 배열로 구현하는게 효율적일 것이다.
왜냐하면, 스택 그림을 회전시키면 순차적으로 저장되는 배열과 유사하기 때문이다.

 

큐는 어떤것이 더 적합할까?
배열에 저장했다고 가정해보자. 저장하는데는 문제가 없다.

그러나, 꺼낼때는 삭제방향이 왼쪽에서 오른쪽이다. 그러면, 배열에 있는 데이터의 이동이  일어나게 된다.
따라서 큐는 링크드리스트로 구현하는 것이 더 효율적이다.
왜냐하면, 링크드리스트로 구현하면, 데이터를 삭제할 때, 자료이동이 필요없기 때문이다.

 

---

 

스택과 큐(Stack $ Queue)의 메서드

스택과 큐가 어떤 메서드들을 가지고 있는지 보자.

 

[스택의 메서드]

스택을 사용하고싶으면, Stack클래스가 있어서,
Stack st = new Stack(); 이런식으로 만들어서 사용하면 된다.

empty()는 스택이 비어있는지 알려준다. true면 비어있는 것이고, false면 비어있는 것이 아니다.

push(Object item)은 Stack에 객체(item)을 저장할 때 사용하고,
pop()은 스택의 맨 위에 저장된 객체를 꺼낼 때 사용한다.

peek()는 스택의 맨 위에 저장된 객체를 반환한다. pop()와 달리 스택에서 객체를 꺼내지는 않는다.
만약, 스택이 비었을 때는, EmptyStackException이 발생한다.

search(Object to)는 스택에 어떤게 있는지 찾는 것이다. 인덱스위치가 1부터 시작한다.
indexOf()는 해당 데이터가 있는 인덱스(0부터 시작하는)을 반환하는데,
search()는 스택의 맨위의 데이터를 기준으로 1부터 시작한다.
못찾으면 -1을 반환하는 것은 indexOf와 search가 똑같다.

 

 

 

[큐의 메서드]

offer()은 큐에 객체를 저장하는 것이다. (추가)
poll()은 큐에서 객체를 꺼내서 반환한다.(삭제)

remove()도 큐에서 객체를 꺼내서 삭제하는 메서드이다.

poll()과 remove()의 차이점이 있는데,
remove()는 객체가 비어있으면 NosuchElementException이라는 예외가 발생하는데,
poll()은 객체가 비어있으면 null을 반환한다.
둘중에 편한 것을 사용하면 된다.
만약에 poll()을 쓰면, if문을 이용해서 obj가 null인지 확인해서 그에따른 처리를 하면되고,
remove()를 사용하면 try-catch를 사용해서 처리하면 된다.
전통적으로는 poll()을 사용하기는 한다.

add()도 마찬가지로 큐에 객체를 저장하는데(추가), 저장에 성공하면 true를 반환하고,
저장공간이 부족하면 객체저장에 실패하며 IllegalStateException 예외가 발생한다.
offer()는 add()와 마찬가지로 저장에 성공하면 true반환하지만, 객체 저장에 실패하면 false를 반환한다.

element()와 peek()도 삭제없이 요소를 읽어온다는 것은 같지만,
위의 메서드들과 마찬가지로 예외가 발생하고 안하고의 차이가 있다.
element()는 큐가 비어있으면 NoSuchElementException을 발생시킨다.
peek()는 큐가 비어있으면 null을 반환한다.

 

이 외에도 더 많은 메서드들이 있는데, 이정도 알아두고, 필요할 때 찾아서 사용하면 된다.

 

---

 

인터페이스를 구현한 클래스 찾기

 

앞서말했듯, Stack은 클래스가 있어서
Stack st = new Stack();이렇게 사용할 수 있다.

자바에서 Queue는 인터페이스로 정의가 되어있다.
Queue q = new Queue();이런식으로 사용할 수 없다.
인터페이스 이기 때문에 객체를 생성할 수 없기 때문이다.

그러면 큐는 어떻게 사용할까?

 

 

큐의 기능을 가지고 있는 객체를 사용하고 싶을때 우리가 해볼 수 있는 방법은 대략 아래와 같을 것이다.,

1. Queue를 직접 구현하는 방법을 사용한다.
2. Queue를 구현한 클래스를 사용한다.

이렇게 두가지로 나눠볼수 있는데 두번째 방법에 대해서 알아보자.
(공부목적으로는 직접 구현해 보는 것도 좋다. 그런데, 사용목적이라면 직접만드는 것 보다 구현되있는 것을 사용하는 편이 빠르다)

Queue인터페이스를 구현한 클래스를 사용하려면, Java API에서 Qeueu인터페이스를 찾아보자.

All Know Implementing Classes를 보면, 해당 항목에 있는 클래스들은,
Queue 인터페이스를 구현한 클래스이다.

즉, Queue인터페이스에 있는 추상메서드들을 전부 가지고 있는 클래스들이다.

우리는 이중에 하나를 골라서 사용하면 된다.

보다보니까 LinkedList클래스가 보인다.

우리가 First In First Out 기능을 가진 저장공간이 필요하면,
Queue인터페이스를 구현한 클래스들중 하나를 골라서 사용하면 되고,
보니까 LinkedList클래스가 그중 하나이다.

그래서 우리가 앞으로 큐를 사용하고 싶으면,
Queue q = new LinkedList(); 이렇게 만들어서 사용하면 된다.
q에 무언가를 저장하고싶으면 q.offer("??"); 이렇게 사용하면 된다.

물론 Queue q = new LinkedList(); 를
LinkedList q = new LinkedList(); 이렇게 사용해도 상관없다.
그러나, Queue q = new LinkedList(); 이렇게 사용하면,
LinkedList();를 Queue인터페이스를 구현한 다른 클래스들로 바꿀 수 있게되는 장점이 있다.
리모컨을 Queue인터페이스로 하면, 큐 인터페이스에 있는 기능만 사용하기 때문에,
하위 코드를 검토하지 않아도 된다는 장점이 있다.

어쨋든, 내가 큐를 사용하고싶으면,
큐가 인터페이스이므로, Queue인터페이스를 구현한 클래스중에서 적절한 것을 찾아서
객체를 생성하면 된다.

 

[Ex11_2]