스택(Stack) VS 큐(Queue) 개념 정리

안녕하세요!!

 

오늘은 스택(Stack)과 큐(Queue) 자료구조의 개념에 대해서 공부해 보려고 하는데요!

이어서 자바에서는 이 두 자료구조가 어떻게 사용되는지 사용법과 메서드에 대해서도 함께 정리해보려고 합니다.

바로 시작해 볼까요~?

 

 

Stack(LIFO)

스택은 후입선출(LIFO) 방식입니다. 

한쪽 끝에서만 자료를 삽입하고, 삭제할 수 있는 자료구조여서 제한적으로 데이터를 접근할 수 있다는 특징을 가집니다.

 

이와 비슷하게 그래프 탐색 방법 중 DFS 자료구조 하고 Stack이 서로 유사한 특징을 가집니다.

DFS는 그래프의 깊이 우선 탐색으로, 하나의 루트노드(node : 정점)로부터 시작해 최대한 항 방향으로 갈 수 있을 때까지 쭉 탐색하다가 더 이상 탐색할 노드가 없을 시 다른 방향으로 탐색을 진행하며 차례대로 모든 정점들을 한 번씩 방문하는 것을 말하는데요.

 

스택 또한 TOP을 통해 접근하여 맨 위에서부터 push() 또는 pop()을 하며 데이터 연산을 수행할 수 있습니다.

그래서 바로 직전에 추가했던 최신 데이터를 빠르게 가져올 수 있다는 장점이 있습니다.

 

출처 : 코드 보관함: [자료 구조] 스택 (Stack)

 

자바에서는 총 7개의 메서드로 스택을 활용할 수 있는데요.

 

1. push()

- 데이터 삽입 메서드

 

2. pop()

- 데이터 삭제 메서드

- 가장 최근에 저장된 값(스택 최상단에 저장되어 있는 값)을 제거

 

3. peek()

- 스택 최상단 값 리턴 메서드

- 가장 최근에 저장된 값(스택 최상단에 저장되어 있는 값)을 출력해 줌.

 

4. search()

- 찾는 값의 인덱스 리턴 메서드

- 찾는 값이 저장되어 있는 위치를 검색해 리턴해주는 것으로, 인덱스 값을 출력.

- 스택의 경우 맨 아래서부터 인덱스가 시작 => 0, 1, 2... 순

 

5. empty()

- 스택이 비어있는지 여부 리턴해주는 메서드(=> stack.empty())

- 스택이 비어있다면 True, 스택에 값이 들어있다면 False 출력

 

6. size()

- 스택의 크기 리턴

 

7. contains()

- stack에 해당 값의 포함 여부를 리턴해주는 메서드

- stack이 해당 값을 포함하고 있다면 True, 포함하고 있지 않다면 False 리턴.

 

 

 

큐(FIFO)

큐(Queue)는 선입선출(FIFO) 방식입니다.

가장 먼저 들어간 데이터가 가장 먼저 나가는 자료구조로, 먼저 들어온 값부터 차례대로 처리하는 구조로 되어 있습니다.

 

큐는 그래프 탐색 방법 중 BFS 자료구조 하고 유사한 특징을 지닙니다.

BFS는 그래프의 너비 우선 탐색으로, 루트노드에서 시작해 인접한 노드를 먼저 탐색하는 방법입니다. 현재 정점에서 가까운 점들부터 차례대로 탐색하는 방식이라고 생각하시면 됩니다.

 

BFS를 큐를 통해 가장 먼저 들어간 값부터 그다음 연결된 값을 순서대로 체크하며 삽입(enqueue)과 삭제(dequeue) 연산을 수행함으로써 구현이 가능합니다.

 

 

출처 : [Java] 큐(Queue) 자료구조 정리

 

자바에서 큐를 활용할 수 있는 메서드에는 총 10개가 있습니다.

 

1. 삽입 메서드(enqueue)

- q.add() : 실패 시 예외 발생

- q.offer() : 실패 시 false 리턴

 

 

2. 삭제 메서드(dequeue)

=> 가장 먼저 추가된 데이터부터 차례대로 삭제됨.

 

- q.remove() : 실패 시 예외 발생

- q.poll() : 실패 시 null 리턴

- q.clear() : 큐 안에 저장된 모든 데이터 삭제

 

 

3. 검사 메서드(peek)

=> 가장 먼저 들어간 값 리턴

 

- q.element() : 실패 시 예외 발생

- q.peek() : 실패 시 null 리턴

 

 

4.  q.size()

- 큐의 크기를 리턴해주는 메서드

 

 

5. q.contains()

- 큐 안에 해당 값이 존재하는지 여부 리턴

- 큐 안에 값이 존재한다면 true, 값이 없다면 false 리턴

 

 

6. isEmpty()

- 큐 안에 데이터가 없고 비어있는지 여부 리턴(=> q.isEmpty())

- 공백 큐라면 true, 큐 안에 값이 들어 있다면 false 리턴

 

 

 

오늘 이렇게 스택과 큐 자료구조 개념에 대해서 살펴보았는데요.

자바에서 스택과 큐를 활용하는 데 사용하는 메서드들에 대해서 잘 공부해 두고 익혀두면

앞으로 코드를 구현하는 데 있어 큰 도움이 될 것입니다!

오늘도 고생 많으셨고 다음 포스팅에서 만나요~!