스택과 큐에 대해..

SionBackEnd·2022년 7월 25일

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. 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의 실사용 예

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

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