[개념] stack 과 queue

1. Stack

- 삽입과 삭제 연산이 후입선출(Last-in first-out)로 이루어지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징을 가지고 있다.

- 새 값이 스택에 들어가면 top이 새 값을 가리킨다. 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 된다. (단방향 입출력 구조: 데이터의 들어오는 방향과 나가는 방향이 같다. > 데이터를 하나씩만 넣고 뺄 수 있다)

- 깊이 우선 탐색(DFS: Depth First Search), 백트래킹 종류의 로직에 효과적이다.

- 재귀 함수의 동작 흐름과 같은 구조이다

 

[용어 설명]

1) push() : top 위치에 새로운 데이터를 삽입하는 연산

2) pop() : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산

3) peek() : top 위치에 현재 있는 데이터를 단순 확인하는 연산

4) clear() : 스택의 모든 내용을 제거하는 메서드

5) empty() : 스택이 비어있는지 여부 반환하는 메서드로 비어있을 경우 true, 비어있지 않을 경우 false를 반환한다

6) search() : 메서드의 인자를 스택에서 검색하여 해당 위치를 반환하다. 인자가 여러개일 경우 마지막 위치를 반환하고, 여기서 위치는 인덱스가 아닌 바져나오는 순서를 뜻한다. 찾는 값이 스택에 없을 경우 -1을 반환한다

 

- 스택의 선언은 Stack<T> 스택 이름 = new Stack<>(); 형태로 선언할 수 있는데, 이때 데이터 타입은 클래스나 래퍼 클래스로 선언할 수 있다. 

// Integer형 스택 선언
Stack<Integer> stackInt = new Stack<>();

// String형 스택 선언
Stack<String> stackStr = new Stack<>();

// Boolean형 스택 선언
Stack<Boolean> stackBool = new Stack<>();

 

[예제]

import java.util.Stack;

public class Main{
	Stack<Integer> st = new Stack<>();
    
    //push() > 값 추가
    st.push(1);
    st.push(2);
    st.push(3);
    
    //pop() > 값 제거 (후입선출이기 때문에 마지막 push()했던 값인 3부터 차례대로 제거)
    st.pop();
    //peek() > 값 확인 (제일 마지막에 들어간 값 확인됨)
    System.out.println(st.peek()); //2
    
    st.pop();
    st.pop();
}

 

2. Queue

- 삽입과 삭제 연산이 선입선출(First-in First-out) 로 이루어지는 자료구조이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나가기 때문에 삽입과 삭제가 양방향에서 이루어진다.

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

[용어 설명]

1) rear : 큐에서 가장 끝 데이터를 가리키는 영역

2) front : 큐에서 가장 앞의 데이터를 가리키는 영역

3) add( ) : rear부분에 새로운 데이터를 삽입하는 연산으로 삽입 성공 시 true, 실패 시 Exception발생

4) offer() : 새로운 데이터를 삽입하는 연산으로 삽입 성공 시 true, 실패 시 false 반환

5) poll() : front부분에 있는 데이터를 삭제하고 확인하는 연산으로 공백일 시 null을 반환

6) peek() : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산으로 공백일 시 null을 반환

7) remove() : 큐에 해당 값이 존재하면 해당 값 삭제 후 true 반환, 존재하지 않으면 false 반환

8) element() : 데이터를 확인할 때 사용하는 연산으로 공백일 시 Exception(NoSuchElementException) 발생

9) clear() : 큐에 있는 데이터 초기화

10) size() : 큐의 사이즈 반환(int)

11) contains() : 큐에 해당 원소가 존재하는지의 여부 확인하는 메서드로 값이 존재할 떄 true, 존재하지 않을 대 false 반환

 

 

- 너비 우선 탐색(BFS: Breadth First Search)에서 자주 사용된다.

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

 

- 자바에서 스택은 Stack 클래스로 구현하여 제공하고 있지만 큐는 Queue 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하지 않는다. 그래서 큐를 인스턴스화 하려면 Queue 인터페이스를 구현하는 클래스 중 하나를 사용해야 한다.

//LinkedList<> 가장 많이 사용되는 구현체 중 하나
Queue<Integer> queue = new LinkedList<>();

//PriorityQueue<> 우선순위큐
Queue<Integer> queue = new PriorityQueue<>();

 

[예제]

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

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);  // 요소 추가
        queue.add(2);
        queue.add(3);

        System.out.println(queue.poll());  // 출력 후 제거
        System.out.println(queue.peek());  // 출력 (제거하지 않음)
    }
}