(Java) 스택(Stack) & 큐(Queue)

❓공부하게 된 계기

프로그래머스 스택 & 큐 파트를 풀기 전 개념을 확인

❗️공부한 내용

1️⃣ Stack

① 선언

➡️ Class 이므로 생성자를 통해 바로 객체 생성이 가능하다.

// Stack 선언
Stack<(자료형)> stack = new Stack<>();

② 구조

➡️ 바닥이 막혀있는 상자를 생각하면 간단하다. 먼저 넣은 물건이 맨 아래에 있고 최근에 넣은 물건일 수록 위에 있다. 따라서 꺼낼 때는 마지막에 넣은 물건을 먼저 꺼내게 된다. 이러한 구조를 LIFO (Last In First Out) 구조라고 한다.

Stack 구조

③ 구현

➡️ 구현 방법으로는 배열과 링크드리스트 (LinkedList) 를 고려할 수 있는데, 앞에서 언급한 Stack 의 LIFO 구조 특성상 뒤에서 부터 하나씩 지워나가면 되는 배열이 적합하다.

배열을 통한 Stack 구현 원리

④ 메서드 (Method)

출처 : 자바의 정석

➡️ return 타입이 Object 이면서 Exception 이 발생하는 경우에는 try-catch 문을 활용하여 예외처리가 가능하다.

➡️ search 메서드의 경우 return 타입이 int 로 Stack 에서의 위치를 의미하는데 배열에서의 index 가 0 에서 시작하는 것과 달리 Stack 은 1부터 시작함을 유의해야한다.

2️⃣ Queue

① 선언

➡️ 인터페이스로 생성자를 통해 바로 객체 생성이 불가능하다. 인터페이스를 구현한 클래스를 통해 생성해주어야 한다.

// Queue 의 선언
Queue<(자료형)> queue = new LinkedList<>();

Queue 인터페이스를 구현한 클래스들은 아래 링크의 레퍼런스 내용 중 Alll Known Implementing Classes 를 확인하면 할 수 있다.

Stack (Java SE 11 & JDK 11 )

레퍼런스를 통해 확인 가능한 내용

② 구조

➡️ 상자의 구조를 생각했던 Stack 과 달리 막혀있던 아래가 뚫려있다고 생각하면 된다. 위에서 넣고 아래서 빼는 구조로 먼저 들어갔다면 먼저 나오게 되고, 이러한 구조를 FIFO (First In First Out) 구조라고 한다.

Queue 구조

③ 구현

➡️ 앞에서 언급한 것과 같이 배열과 링크리스트를 고려해볼 수 있는데 여기서는 배열을 사용할 경우 앞에서 삭제하면 비워진 자리를 뒤에서 하나씩 채워줘야함으로 비효율적이다. 따라서 단순히 앞에서 연결을 끊는 링크드리스트가 적합하다.

배열을 통한 Queue 구현 원리

링크드리스트를 통한 Queue 구현 원리

④ 메서드 (Method)

출처 : 자바의 정석

➡️ return 타입이 Object 이면서 Exception 이 발생하는 경우에는 try-catch 문을 활용하여 예외처리가 가능하다.

➡️ return 타입이 Object 이면서 null 을 반환하는 경우는 if (Obj == null) 조건문을 활용하여 처리가 가능하다.

✏️ 적용 시켜본 예제

(알고리즘 스터디) 3주차 월 _ 스택&큐📦 _ (Programmers) 프린터

 

(알고리즘 스터디) 3주차 수 _ 스택&큐📦 _ (Programmers) 다리를 지나는 트럭

 

(알고리즘 스터디) 3주차 수 _ 스택&큐📦 _ (Programmers) 올바른 괄호

🧐 추가로 궁금한 점

1️⃣ Queue 객체 생성 방식

// Queue 의 선언
// 방법 (1)
Queue<(자료형)> queue = new LinkedList<>();
// 방법 (2)
LinkedList<(자료형)> queue = new LinkedList<>();

방법(2) 의 선언 방식도 가능한데 방법(1)을 기본적으로 사용하는 이유.

 

➡️ 객체 생성 후 다양한  메서드를 사용할 것인데 Queue 객체로 생성 시 Queue 인터페이스 내의 메서드로만 사용가능할 것이다. 하지만 LinkedList 객체로 생성 시 Queue 인터페이스 내의 메서드 외에도 다양한 메서드들을 활용가능하다.

예를 들어 LinkedList 클래스 안에는 removeFirst() 라는 메서드가 있는데,

// 방법 (1) 로 선언한 경우
Queue<Integer> q = new LinkedList<>();
q.removeFisrt(); // 사용불가(오류발생)

// 방법 (2) 로 선언한 경우
LinkedList<Integer> ll = new LinkedList<>();
ll.removeFirst(); // 사용가능

위 예시와 같이 Queue 객체라면 해당 메서드를 사용할 수 없고, LinkedList 객체라면 당연히 사용 가능할 것이다.

 

➡️ 만약 LinkedList 클래스의 다양한 함수를 활용하고자 사용하는 것이면 LinkedList 객체로 생성하여 사용하는 것이 맞지만 Queue 사용이 목적이라면 조상 인터페이스로 좁혀주는 것이 오류를 예방하는 차원에서 좋을 것 이다. 또, LinkedList 말고도 Queue 를 구현한 다양한 클래스가 있으므로 쉽게 바꿀 수도 있다.

// Queue 객체로 생성한경우
Queue<Integer> q = new LinkedList<>(); // 가능
Queue<Integer> q = new ArrayDeque<>(); // 가능

q.revmove();
q.element();

🔗 참고

① 자바의 정석 기초편 Ch11-15 요약 영상 : https://www.youtube.com/watch?v=ktvhRSRohR4