[Java] 스택(Stack), 큐(Queue)

우리가 어떤 데이터를 저장했다가 사용하는 경우에 배열이나 리스트를 많이 사용한다. 그런데, 어떤 문제들은 배열과 리스트를 사용하는게 어렵고 심지어 정말 많은 시간이 걸리는 경우가 발생한다.

이런 경우, 배열을 좀 더 발전시킨 형태인 스택, 큐이라는 자료구조를 이용해 문제를 해결할 수 있게 된다. 오늘은 이 2가지 자료 구조에 대해 볼 것이다.

1. 스택 (Stack)

---

(1) 스택이란?

• 자료구조 중 하나로, 데이터의 삽입과 삭제가 후입선출(LIFO : Last In First Out)이뤄지는 구조이다.
• 후입선출이기 때문에, 데이터의 삽입과 삭제가 한 쪽에서만 일어난다.
  

(2) 스택의 구현 방식

• 배열 기반 스택 : 고정된 크기의 배열을 사용해 스택을 구현하며, 인덱스를 통해 데이터에 접근한다.
• 연결 리스트 기반 스택 : 각 노드가 데이터와 다음 노드에 대한 포인터를 가지는 구조로, 동적 메모리 할당을 통해 스택을 구현한다.

(3) 스택의 메소드

• push(E item) : 스택에 데이터를 넣어줌 (가장 위에)

• pop() : 가장 마지막에 들어온 값을 삭제하고 리턴

• peek() : 가장 마지막에 들어온 값을 리턴

• empty() : 스택에 데이터가 있다면 false 없다면 true 값을 리턴

• search(Object o) : 해당 위치에 있는 데이터를 리턴한다.

⁉️ add와 push
Stack에는 push와 같은 기능을 하는 add라는 메소드도 존재한다. 그런데 Stack은 Vector을 상속받은 클래스 이기 때문에 Vector의 메소드는 push를 사용하는 것이 올바른 방법이다.

(4) 선언 및 사용

import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Stack<Integer> myStack = new Stack<>();
		
		myStack.push(1); // 1 넣기
		myStack.push(2); // 2 넣기
		myStack.push(3); // 3 넣기
		myStack.pop(); // 3 삭제, 리턴
		myStack.peek(); // 3 리턴
        myStack.empty(); // 현재 1,2라는 값이 있으므로 false 리턴
        myStack.search(1); // 2리턴
	}
}

2. 큐 (Queue)

---

(1) 큐란?

• 자료구조 중 하나로, 데이터의 삽입과 삭제가 선입선출(FIFO : First In First Out)이뤄지는 구조이다.
• 삽입과 삭제가 양방향에서 이뤄진다.
  

(2) 큐의 메소드

• 삽입 (Insert) : 위의 그림에서 new 부분에 값을 삽입
  • add(e) : 큐가 꽉 차면 IllegalStateException 발생
  • offer(e) : 삽입에 실패하면 false를 반환한다.
    
    
• 제거 (Remove) : del 부분의 값을 삭제하고, 그 값을 리턴
  • remove() : 큐가 비면 NoSuchElementException 발생
  • poll() : 큐가 비어있으면 null값을 리턴한다.
    
    
• 확인 (Examine) : del 부분의 값을 리턴
  • peek() : 큐가 비면 NoSuchElementException 발생
  • element() : 큐가 비어있으면 null값을 리턴한다.

각각의 삽입, 제거, 확인 메소드의 차이를 정리한 그림이다.
상황에 맞게 잘 사용하면 된다.

출처 : https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

(3) 선언 및 사용

• Queue 자체로는 인터페이스이다. 그래서 new Queue<>();로는 작성하지 않는다.
• Queue의 구현체로 자주 사용되는 클래스에는 ArrayDeque(배열의 특징)와 LinkedList(List의 특징)가 있다.
• 여기에서는 LinkedList를 통해 만든 Queue 예제이다.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
	public static void main(String[] args) {
		Queue<Integer> q = new LinkedList<>();
		
		q.add(1); // 값을 추가하기
		q.add(2);
		q.add(3);
		
		q.peek(); // head에 있는 값을 확인 가능 : 1 리턴
		
		q.poll(); // head에 있는 값을 확인, 삭제 : 1 리턴,삭제	
	}
}

3. 참고 문헌

• Stack 공식 문서
• Queue 공식 문서
• 김종관, Do it! 알고리즘 코딩 테스트 (자바 편)