[ch11-15~18] Stack과 Queue

스택: 상자같은 것

밑이 막힌 상자

먼저 넣은게

맨 밑에 깔려있다

스택을

Last In First Out

(LIFO)

이라고도 함

(마지막에 넣은게

첫 번째로 나온다)

 

넣는 것: push

꺼내는 것: pop

큐: 줄서기하고 똑같음

양 끝이 뚤린 상자

꺼내면 젤 첫 번쨰 숫자인

0이 꺼내지는 것

스택과 달리

저장한 순서대로 꺼내짐

 

저장하는 것: offer

꺼내는 것: poll

 

First In First out

(FIFO)

(먼저 온 사람이

먼저 나간다)

스택은 배열이 효율적이고

큐는 링크드리스트가 효율적

<스택의 메서드>

스택을 사용할 때의 클래스가 있다

Stack st = new Stack();

empty: 비어있는 지 알려줌

true - 비어있는 것

false - 비어있지 않은 것

peek: 상자 맨 위에

뭐가 있는 지 보는 것

꺼내지 않고 맨 위만 보는 것

ex) 2

 

push: 추가

pop: 삭제

 

search: 스택이 어떤게

있는 지 찾는 것

지정한 객체가

몇 번 째 있는 지

찾는 것

(index of와 비슷하지만

index of는 0부터 시작

search는 1부터 시작)

<큐의 메서드>

offer: 추가

poll: 삭제

remove: 삭제

(poll 하고의 차이:

remove는 예외 발생 O

poll은 null 반환, 예외 발생 X

 

add:  추가

예외발생O

offer: 예외발생X

 

element: 예외발생O

 

peek: 예외발생X

꺼내지 않고 보기만 하는 것

자바에서 Queue는

인터페이스로 정의 돼 있어서

new Queue로 쓸 수 없다

Queue q = new Queue

 

반면에 Stack은 class가 있어서

Stack st = new Stack

이렇게 쓸 수 있다

 

그럼 어떻게 해야할 까?

 

Queue가 갖고있는

객체를 쓰고 싶을 땐,

1) Queue를 직접 구현

2) Queue를 구현한 클래스를 사용

 

2번방법 사용하려면

Java API에서

Interface Queue를 찾아보자

 

All Known Implementing Classes

: Queue interface를 구현한 클래스의 목록

 

  여기 있는 class들은

Queue interface 들을 구현한 것

Queue interface에 있는

추상 메서드들을 갖고 있다는 뜻

<실습>

Stack와 Queue에다가

0,1,2 넣음

그 다음엔

Stack 하고 Queue가 비어있는 지

반복문을 통해서 확인

비어있지 않으면

계속 꺼내기를 하는 것(pop)

 

Stack은 2, 1, 0 순으로 꺼내진다

반면에 Queue는 0,1,2