3주차

Stack / Queue

코딩 테스트에서 매우 자주 등장하는 선형 자료구조

• 데이터를 어떤 순서로 넣고 꺼내느냐에 따라 동작 방식이 달라진다.
• 특히 두 자료구조는 순서 처리, 대기열 관리, 괄호 검사, 탐색(BFS/DFS) 등과 깊게 연결되어 있다.
• 삽입과 삭제가 어느쪽에서 일어나는지, 그리고 어떤 상황에서 Stack을 쓰고 Queue를 써야 하는지를 정확하게 이해하는 것이 중요하다. ㅤ

개념

Stack

나중에 들어온 데이터가 먼저 나가는 후입선출 구조로, LIFO(Last In, First Out) 구조라고도 부른다.

특징

• 한쪽 끝에서만 삽입과 삭제가 일어남
• 가장 마지막에 들어온 데이터가 가장 먼저 나옴
• 재귀, 되돌리기(Undo), 괄호 검사 문제에 자주 사용됨
• DFS와도 자주 연결되는 개념

주요 연산

• push(e) : 새로운 요소 e를 스택의 최상단에 추가
• pop() : 스택의 맨 위에 있는 요소를 꺼내서 변환
• peek() : 스택의 최상단 요소를 삭제하지 않고 반환
• isEmpty : 스택이 비어있으면 True 반환 / 아니면 False 반환
• isFull : 스택이 가득 차 있으면 True 반환 / 아니면 False 반환

참고

• push의 경우 상단에 어떤 요소를 쌓을 지 그 정보를 입력해 주어야 한다.
• pop의 경우는 무조건 가장 상단의 요소를 삭제하는 것이므로 별도의 입력이 필요없다.

문제 패턴

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트