Stack / Queue (스택 / 큐)

ch11 - 15 스택과 큐 (Stack & Queue)

 

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

 

LIFO 란 ?

 

Last In First Out 

== 마지막에 넣은것을 제일 먼저 꺼낸다.

 

 

밑은 막히고, 위만 뚫린 상자 라고 생각 하면 된다.

 

0부터 넣었고, 1을 넣었고, 2를 마지막에 넣었다.

 

이것을 추출 하려면 2를 꺼내고, 1을 꺼내고, 0을 꺼내야 하는 구조 이다.

 

1 > 2 > 3 > 4 > 5 의 순서로 넣었다면,

5 > 4 > 3 > 2 > 1 의 순서로 꺼내야 한다는 의미 이다.

 

저장하는것을 push 라고 하고,

추출하는것을 pop 이라고 한다.

 

 

 

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

 

FIFO 이란 ?

 

First In First Out

== 먼저 넣은것을 먼저 꺼내게 된다.

 

 

놀이 공원에서 먼저온 고객부터 놀이 기구를 이용 할 수 있는 상황을 떠올리면 된다.

 

1 > 2 > 3 의 순서로 넣었다면,

1 > 2 > 3 의 순서로 꺼내게 된다.

 

저장하는것을 offer 라고 하고,

추출하는것을 poll 이라고 한다.

 

 

 

스택을 만들려면 ArrayList 와 LinkedList 중에 무엇이 더 효율적일까 ?

 

정답은 ArrayList 가 더 효율적이라고 할 수 있다.

 

왜냐하면 스택은 순차적으로 저장이 되기 때문 이다.

 

뿐만 아니라, 삭제 할 때도 제일 위에 있는 데이터 부터 삭제 하기 때문에, 순차적이라고 할 수 있다.

 

추가도 마찬 가지 이다.

 

암튼 순차적이다 ?

>> 배열리스트에 적합.

 

 

 

큐를 만들려면 ArrayList 와 LinkedList 중에 무엇이 더 효율적일까 ?

 

정답은 LinkedList 가 더 효율적이라고 할 수 있다.

 

큐는 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다고 했었다.

 

그래서 만약에 배열리스트에 저장을 하게 되면,

 

0 | 1 | 2 순서대로 저장 하고, 이때는 문제가 없지만,

 

삭제 하거나, 할때, 0 부터 꺼내야 하는데, 그러면 첫번째 요소의 0을 지우면, 

1 | 2 가 이동 해야 한다는 비효율적인 상황이 발생 하게 된다.

 

그래서, 링크드리스트를 사용 하면, 삭제시, 요소들간의 자리 이동이 없어서 유리 하다고 할 수 있다.

 

 

 

ch11 - 16 스택과 큐 (Stack & Queue) 의 메서드

 

Stack 이라는 클래스가 존재 한다.

 

Stack stack = new Stack(); 해서 생성 하면 된다.

 

 

Object peek() 은 객체를 꺼내는게 아니라, 그냥 맨 위에 저장된 객체가 뭔지만 보는 것이다.

 

2

---

1

---

0

 

인 경우, 객체 2 를 볼 수 있게 된다.

 

Object pop() 은 맨위의 저장된 객체를 정말로 꺼내버린다.

 

 

 

자바에서 Queue 는 클래스가 아니라 인터페이스로 존재 한다.

 

 

즉, Queue queue = new Queue(); 가 불가능 하다.

 

인터페이스를 객체화 할 수 없기 때문 이다.

 

그래서, 사용 방법이 몇가지 있는데 아래와 같다.

 

1)

Queue 를 직접적으로 구현 하기.

(공부 목적이라면 직접 구현 해보기)

 

2)

Queue 를 구현한 클래스를 사용 하기.

(사용 목적이라면 Java API 에서 Queue 인터페이스를 찾고, 그냥 사용 하면 된다)

 

Queue 인터페이스를 구현한 자바의 수많은 클래스를 찾아서 사용 하면 된다.

 

구현한 수많은 클래스들은 Queue 인터페이스의 미완성 메서드를 모두 완성 시킨 메서드로 가지고 있다.

 

 

해당 클래스가 무슨 특징을 가지고 있는지 궁금 하면 검색 해보자.

 

[ 참고 ]

 

Queue queue = new LinkedList();

와

LinkedList linkedList = new LinkedList();

의 

차이점

 

링크드 리스트는 Queue 인터페이스를 구현 했한 클래스 이기 때문에,

인터페이스 Queue 의 참조변수로 LinkedList 객체를 가리키게 되면,

Queue 인터페이스가 가지고 있는 메서드만 사용이 가능 하다.

LinkedList 가 고유하게 가지고 있는 메서드가 있으면 그것은 사용 할 수 없게 된다.

 

LinkedList 타입의 참조변수 linkedList로 LinkedList 객체를 가리키게 되면,

Queue 인터페이스를 구현 받았기 때문에 Queue 인터페이스가 가지고 있는 모든 공통의 메서드를 사용 +

LinkedList가 고유하게 가지고 있는 메서드를 사용 한다는 의미가 된다.

 

그래서,

가능하면 참조변수가 Queue 인터페이스 타입인 참조변수로 해서 만드는게 활용성이 좋다고 할 수 있다.

만약에,

LinkedList 객체를 더이상 가리키지 않고 싶어진다면, 그냥 Queue 인터페이스를 구현한 다른 클래스의

객체를 가리키면 되버리는 것이다.

 

참고 : 인터페이스의 다형성

https://hwanii96.tistory.com/262

인터페이스와 다형성

 

Queue 인터페이스의 대표적인 메서드 6가지 확인 하기.

 

 

메서드 3개는 예외가 발생 할 수 있고, 나머지 3개의 메서드는 예외가 발생 하지는 않는다.

 

이외에도 많은 메서드가 있지만 이정도만 알아도 충분 하다.

 

[ 예시 ]

 

import java.util.*;

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

		q.offer("0");
		q.offer("1");
		q.offer("2");

		System.out.println("= Stack =");
		while(!st.empty()) {
			System.out.println(st.pop()); // 스택에서 요소 하나를 꺼내서 출력
		}
		
		System.out.println();

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

 

//	[ console ]

= Stack =
2
1
0

= Queue =
0
1
2

 

Stack에 pop() 메서드를 사용 하니까, 

넣었던 순서와 반대로 추출 되는 것을 확인 할 수 있다.

 

Queue는 poll() 메서드를 사용 하니까,

넣었던 순서와 동일하게 추출 되는 것을 확인 할 수 있다.