스택 / 큐

스택(Stack)

개념

• LIFO (Last In, First Out) - 마지막에 들어간 것이 먼저 나옴
• 책 쌓기와 같은 구조 - 위에서 넣고, 위에서 빼기

주요 연산

• push(): 맨 위에 요소 추가
• pop(): 맨 위 요소 제거하고 반환
• peek() / top(): 맨 위 요소 확인 (제거하지 않음)
• isEmpty(): 스택이 비어있는지 확인

사용 예시

• 되돌리기(Undo) 기능
• 괄호 검사 (올바른 괄호 쌍 확인)
• 함수 호출 관리
• 계산기 (후위 표기법)

자바 코드

Stack<Integer> stack = new Stack<>();
stack.push(1);        // [1]
stack.push(2);        // [1, 2]
int top = stack.pop(); // 2 반환, [1]
int peek = stack.peek(); // 1 확인, [1]

---

큐(Queue) 

개념

• FIFO (First In, First Out) - 먼저 들어간 것이 먼저 나옴
• 줄 서기와 같은 구조 - 뒤에서 넣고, 앞에서 빼기

주요 연산

• offer() / enqueue(): 뒤쪽에 요소 추가
• poll() / dequeue(): 앞쪽 요소 제거하고 반환
• peek() / front(): 맨 앞 요소 확인 (제거하지 않음)
• isEmpty(): 큐가 비어있는지 확인

사용 예시

• 프로세스 스케줄링
• BFS(너비 우선 탐색)
• 프린터 대기열
• 버퍼 관리

자바 코드

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);       // [1]
queue.offer(2);       // [1, 2]
int front = queue.poll(); // 1 반환, [2]
int peek = queue.peek();  // 2 확인, [2]

---

스택 vs 큐 비교

구분	스택(Stack)	큐(Queue)
구조	LIFO	FIFO
삽입 위치	맨 위(top)	맨 뒤(rear)
삭제 위치	맨 위(top)	맨 앞(front)
대표 예시	책 쌓기	줄 서기
주요 용도	되돌리기, 괄호검사	스케줄링, BFS

---

자료구조의 관계

스택과 큐는 리스트의 특별한 사용법

• 리스트: 인덱스로 자유롭게 접근 가능
• 스택: 리스트를 "맨 위에서만" 사용
• 큐: 리스트를 "한쪽 끝에서만" 사용

핵심 포인트

• 스택과 큐는 제약이 있는 리스트
• 접근 패턴에 따라 선택 (최근 것 vs 오래된 것)
• 문제 상황을 보고 LIFO인지 FIFO인지 판단하기

 

---