Stack

스택은 자료(데이터)를 순서대로 쌓아올리는 자료구조이다.
만약 배열 {1,2,3,4,5} 이 있다고 친다면, 이데이터들은 순서대로 1부터 5까지 순서대로 들어왔을 것이다. 그리고 우리가 상식적으로 빠져나간다고 생각하면 당연히 1부터 빠져나가는게 맞지만, Stack자료구조에서는 마지막으로 들어온 데이터가 먼저 밖으로 나가게 된다.

다시 돌아와서 1,2,3,4,5가 순서대로 들어왔다면 나갈때는 5,4,3,2,1 이렇게 반대로 나가게 된다.

Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한다.

Stack의 실사용 예

스택은 대표적으로 웹사이트의 뒤로가기 앞으로가기에 사용된다. 위에서 언급한것처럼 우리가 뒤로가기를 누르면, 우리가 현재 페이지에 있기전의 페이지로 돌아가고 그상태에서 앞으로 가기를 누르면 현재 페이지로 돌아온다.

앞으로가기 스택과 뒤로가기 스택이 있다고 한다면 현재페이지에서 뒤로가기 스택에 있는 페이지로 가면, 앞으로가기 스택에는 방금전에 있던 페이지가 등록이 될것이다. 하지만, 현상태에서 다른페이지로 들어가게된다면, 앞으로가기 스택에 남아있던, 페이지들은 초기화가 되어버린다. 궁금하면, 직접 웹사이트에서 시도해보자.

주의할점

1. 스택 자료구조는 데이터를 한번에 한개씩 넣고,뺀다. 한번에 여러개의 데이터를 처리할 수 없다.
2. 스택 자료구조는 하나의 입출력 방향을 가지고있다. 데이터가 들어온곳 말고 다른 출구는 없다.

자바에서 구현한 스택

스택은 자바에서 클래스로 만들어준 자료구조이다. 따라서 이미 구현된 메서드를 사용하면된다.

Stack 클래스 공식문서 확인하기 링크!

Stack 클래스 메서드

위 공식문서 내용처럼 이미 구현된 메서드는 아래와 같다.
1. empty() : Stack이 비어있는지에 대한 유무를 리턴.
2. peek() : 맨 마지막으로 들어온 데이터를 리턴.
3. pop() : 맨 마지막으로 들어온 데이터를 삭제하며 그값을 리턴.
4. push(E item) : 인자값에 있는 데이터를 Stack 자료구조에 추가한다.
5. search(Object o) : Stack 자료구조 내부에 매개변수의 데이터가 몇번째 인덱스에 있는지 출력한다. 만약 없다면, -1을 출력함.

Queue

Queue 자료구조는 그래프알고리즘의 넓이 우선 탐색(BFS)에서 사용되니 잘 알아둘것

큐(Queue)는 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다. 따라서 우리가 익히 알고있는 방식, 먼저 들어온사람이 먼저 나간다.

1,2,3,4,5 의 데이터가 들어왔을때 먼저 들어온 순서대로 1,2,3,4,5 이렇게 출력된다.

자료구조 Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있다.

Queue의 실사용 예

큐는 대표적으로 프린터기에서 사용된다. 프린터를 사용할때 복사할 내용을 프린터기에 옮긴다. 그리고 프린터기는 먼저 들어온 데이터를 출력한다.

프린터기는 외부로 부터 복사 할 내용을 입력받고 먼저 들어온 순서대로 프린터하여 출력한다. 만약 프린터기가 스택자료구조를 사용한다면, 우리는 복사 할 내용을 모두 프린터기에 입력한뒤 순서가 뒤집힌 상태로 출력받게 될것이다. ( 생각보다 편할수도 있을것 같다. ??????)

주의할점

1. Queue 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺀다. 한꺼번에 여러 개를 넣거나 뺄 수 없다.
2. Queue 자료구조는 데이터의 입력, 출력 방향이 다르다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없다

자바에서 큐를 사용하는 법

아쉽게도 큐는 클래스가 아니다. 자바에서 큐를 인터페이스로 만들어준 자료구조이기 때문에 생성자를 이용해서 직접 객체를 생성할 수 없다. 먼저 공식문서를 보자.

Queue 인터페티스 공식문서에서 확인하는 링크!

위 사진을 자세히 보면 다행히도 이미 구현되어있는 클래스가 있다. 그중 눈에 띄는게 LinkedList이다. 이전에 배운 LinkedList를 이용하면 Queue를 구현할수있는것이다.

Queue 인터페이스 메서드

아까 말했듯이 LinkedList를 사용하거나 그외 이미 Queue를 구현해준 클래스를 이용하면, Queue의 메서드를 이용할 수 있다.

메서드 이용의 주의할점

위의 공식문서에서는 적혀있지않지만, 자세히 보면 추가, 삭제, 검색 기능들이 2개씩 존재하고 있는걸 확인할수있을것이다.
그이유는 *예외를 발생시키느냐 안시키느냐 차이이다.

예외를 발생시키는 메서드

아래의 3개 메서드를 사용할 때는 try catch로 감싸주어야 한다.

• add (E e)
• remove()
• element()

예외를 발생시키지 않는 메서드

• offer(E e)
• peek()
• poll()