#11. Stack과 Queue의 차이

스택(Stack)

스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료구조이다. 다시 말해 후입선출(LIFO, Last-In-First-Out) 구조로, 왼쪽 그림과 같이 가장 마지막에 들어간 데이터가 가장 먼저 나오는 자료구조이다. 쌓아올려진 팬케이크를 생각하면 쉽다. 가장 위에 있는 팬케이크 먼저 없어질 것이다. 이 외에도 웹 페이지에서 뒤로가기 버튼을 눌렀을 때, 문서를 작성하다가 Ctrl+Z를 눌렀을 때 등 스택이 활용되는 상황이 많다. 스택에서 데이터가 추가/제거되는 곳을 top이라고 한다.

스택 메서드

• Object pop() : 맨 위에 저장된 객체를 꺼내서 반환한다.
• Object push(Object item) : 새로운 객체를 맨 위에 저장한다.
• Object peek() : 맨 위에 있는 데이터를 본다. (데이터를 꺼내지는 않는다.)
• boolean isEmpty() : 스택이 비어있는지 확인한다.

스택의 성질

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 상단의 원소 확인이 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

스택의 장단점

• 장점 : 데이터의 삽입, 삭제, 접근이 빠르다.
• 단점 : top 위치 외 데이터의 접근이 원칙적으로 불가능하다.

스택의 활용

• DFS 알고리즘
• 재귀 알고리즘
• 수식 괄호 검사
• 역순 문자열 만들기

큐(Queue)

큐는 한쪽 끝에서 데이터를 넣고 반대쪽 끝에서 데이터를 뺄 수 있는 자료구조이다. 다시 말해 선입선출(FIFO, First-In-First-Out) 구조로, 오른쪽 그림과 같이 가장 먼저 들어간 데이터가 가장 먼저 나오는 자료구조이다. 비행기를 탈 때 탑승수속 줄을 생각하면 쉽다. 먼저 줄을 선 사람이 먼저 나올 것이다. 큐에서 데이터가 추가되는 곳을 rear, 제거되는 곳을 front라고 한다.

큐 메서드

• boolean add(Object o) : 새로운 객체를 맨 뒤에 추가한다.
• Object poll() : 맨 앞에 있는 객체를 꺼내서 반환한다.
• Object peek() : 삭제없이 요소를 읽어온다.

큐의 성질

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 앞/뒤의 원소 확인이 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

큐의 장단점

• 장점 : 데이터의 삽입, 삭제, 접근이 빠르다.
• 단점 : rear과 front 위치 외 데이터의 접근이 원칙적으로 불가능하다.

큐의 활용

• BFS 알고리즘
• 캐시 구현
• 프로세스 관리
• 우선순위가 같은 작업 예약

스택과 큐의 차이

스택은 입력과 출력이 한 곳에서 이루어지는 자료구조로, LIFO 구조라고도 불린다. 마지막에 들어간 데이터가 먼저 나오는 자료구조이다. 큐는 입력과 출력이 양 쪽 끝에서 이루어지는 자료구조로, FIFO 구조라고도 불린다. 먼저 들어간 데이터가 먼저 나오는 자료구조이다. 

 

https://youtu.be/Nk_dGScimz8?si=u8PnhvT3adzQd2jW

https://youtu.be/0DsyCXIN7Wg?si=LFivCCiVWOM7fx4T

https://youtu.be/D_fwSy5tRAY?si=XPGGyiw9rTzxgD1P

[Data Structure] 스택(Stack)과 큐(Queue) 개념, 특징, 활용 예시 :: 코딩 공부 일지 (tistory.com)

🧱 Java Collections Framework 종류 💯 총정리 (tistory.com)