스택과 큐(Java)

스택

• 스택은 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조이다.
• 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.

• 새 값이 스택에 들어가면 top이 새 값을 가리킨다.
• 스택에서 값을 뺄 때 top이 가리키는 값을 스택에서 빼게 되어 있으므로 가장 마지막에 넣었던 값이 나오게 된다.

스택 용어

• 위치
  - top: 삽입과 삭제가 일어나는 위치를 뜻한다.
• 연산
  - push: top 위치에 새로운 데이터를 삽입하는 연산이다.
  - pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
  - peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

• 스택은 깊이 우선 탐색, 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아 두어야 한다.
• 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.

큐

• 큐는 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조이다.
• 스택과 다르게 먼저 들어온 데이터가 먼저 나간다.
• 삽입과 삭제가 양방향에서 이뤄진다.

• 새 값 추가는 큐의 rear에서 이뤄지고, 삭제는 큐의 front에서 이뤄진다.

---

큐 용어

• rear: 큐에서 가장 끝 데이터를 가리키는 영역이다.
• front: 큐에서 가장 앞의 데이터를 가리키는 영역이다.
• add: rear 부분에 새로운 데이터를 삽입하는 연산이다.
• poll: front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
• peek: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.

---

• 큐는 너비 우선 탐색에서 자주 사용되므로 이 역시도 스택과 함께 잘 알아두어야 하는 개념이다.

💡 우선순위 큐도 있다!

우선순위 큐는 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다. 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현하는데 힙은 트리 종류 중 하나이다.

자바에서 스택 사용법

1. 자바에서 스택을 사용하기 위해 java.util 패키지의 Stack 클래스를 import한다.

import java.util.Stack;

1. Stack 객체를 생성한다.

Stack<String> stack = new Stack<>();

1. 스택에 데이터를 추가하기 위해 push 메소드를 사용한다.

stack.push("데이터1");
stack.push("데이터2");
stack.push("데이터3");

1. 스택에서 데이터를 꺼내기 위해 pop 메소드를 사용한다.

String data = stack.pop();
System.out.println(data); // "데이터3"

• pop 메소드는 스택에서 가장 위에 있는 데이터를 꺼내고, 해당 데이터를 반환한다. 스택에서 꺼낸 데이터는 스택에서 제거된다.

1. 스택에서 데이터를 확인하기 위해 peek 메소드를 사용할 수 있다. peek 메소드는 스택의 가장 위에 있는 데이터를 반환하지만, 스택에서 제거하지는 않.ㄷ다.

String topData = stack.peek();
System.out.println(topData); // "데이터2"

• peek 메소드를 사용하면 스택의 가장 위에 있는 데이터를 확인할 수 있다.

1. 스택이 비어있는지 확인하기 위해 isEmpty 메소드를 사용할 수 있다.

boolean isEmpty = stack.isEmpty();
System.out.println(isEmpty); // false

• isEmpty 메소드는 스택이 비어있으면 true를, 데이터가 있는 경우 false를 반환한다.
• 위와 같은 방법으로 자바에서 스택을 활용할 수 있습니다. 스택은 데이터의 추가와 제거가 상수 시간(O(1))에 이루어지기 때문에, 데이터를 임시로 저장하거나 역순으로 처리해야 할 때 유용하게 사용된다.

자바에서 큐 사용법

1. 자바에서 큐를 사용하기 위해 java.util 패키지의 Queue 인터페이스를 import 해야 한다.

import java.util.Queue;

1. 큐를 구현한 클래스 중 하나인 LinkedList를 사용하여 Queue 객체를 생성한다.

Queue<String> queue = new LinkedList<>();

1. 큐에 데이터를 추가하기 위해 offer 메소드를 사용한다.

queue.offer("데이터1");
queue.offer("데이터2");
queue.offer("데이터3");

1. 큐에서 데이터를 꺼내기 위해 poll 메소드를 사용한다.

String data = queue.poll();
System.out.println(data); // "데이터1"

• poll 메소드는 큐에서 가장 앞에 있는 데이터를 꺼내고, 해당 데이터를 반환합니다. 큐에서 꺼낸 데이터는 큐에서 제거된다.

1. 큐에서 데이터를 확인하기 위해 peek 메소드를 사용할 수 있다. peek 메소드는 큐의 가장 앞에 있는 데이터를 반환하지만, 큐에서 제거하지는 않는다.

String frontData = queue.peek();
System.out.println(frontData); // "데이터2"

1. 큐가 비어있는지 확인하기 위해 isEmpty 메소드를 사용할 수 있다.

boolean isEmpty = queue.isEmpty();
System.out.println(isEmpty); // false

• isEmpty 메소드는 큐가 비어있으면 true를, 데이터가 있는 경우 false를 반환한다.
• 위와 같은 방법으로 자바에서 큐를 활용할 수 있다. 큐는 데이터를 순서대로 처리해야 할 때 유용하게 사용되며, 주로 작업 대기열, 이벤트 처리, 너비 우선 탐색(BFS) 등에 활용된다.