1. 스택 (Stack)

💡 핵심 설명

LIFO 구조. 함수 호출, 괄호 검사에 활용

---

📌 개념

스택(Stack)은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 선형 자료 구조이다.

데이터가 차곡차곡 쌓아 올라가는 형태이며, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조이다.

 

연산

push 연산을 통해 새로운 데이터를 top 위치에 삽입하고,

pop 연산을 통해 top 위치의 데이터를 제거한다.

데이터는 top을 통해서만 접근 가능하며, 중간에 있는 데이터를 직접 수정하거나 삭제할 수 없다.

---

✅ 추가 설명

스택(Stack) vs 큐(Queue) 비교

특성	스택(Stack)	큐(Queue)
구조	후입선출(LIFO)	선입선출(FIFO)
삽입 방식	push (top에서 삽입)	enqueue (rear에서 삽입) offer (java)
삭제 방식	pop (top에서 삭제)	dequeue (front에서 삭제) poll (java)
접근 방식	top을 통해서만 가능	front에서만 삭제, rear에서 삽입
사용 사례	실행 취소(undo), 역순 문자열	은행 업무, 프로세스 관리

---

💯  관련 알고리즘

📍 괄호 유효성 검사 (Valid Parentheses)

• 설명: (), {}, [] 와 같은 괄호의 열림과 닫힘이 올바른지 검사
• 알고리즘:
  1. 여는 괄호는 스택에 push
  2. 닫는 괄호가 나오면, 스택의 top과 짝이 맞는지 확인하고 pop
  3. 모든 괄호를 처리한 후 스택이 비어 있어야 올바른 괄호

 

📍 수식 계산 (후위 표기법 - Postfix Expression Evaluation)

• 설명: 후위 표기법으로 작성된 수식을 계산
• 예시: 3 4 + 2 * → ((3+4) * 2)
• 알고리즘:
  1. 숫자는 스택에 push
  2. 연산자를 만나면 스택에서 숫자 2개 pop → 연산 → 결과 push

 

📍 중복 문자 제거 / 문자열 압축

• 예시: abbaca → ca (같은 문자가 연속으로 나올 때 제거)
• 알고리즘:
  1. 스택에 문자를 하나씩 push
  2. 현재 문자와 top이 같으면 pop (중복 제거)

 

📍 Histogram에서 가장 큰 직사각형 구하기

• 설명: 막대그래프에서 가장 넓은 직사각형 구하기
• 알고리즘 핵심:
  • 각 막대에 대해 왼쪽/오른쪽으로 갈 수 있는 한계를 스택을 이용해 계산

 

📍 Next Greater Element (다음 큰 숫자 찾기)

• 설명: 배열에서 현재 숫자보다 오른쪽에 있는 숫자 중 처음으로 큰 숫자 찾기
• 알고리즘:
  1. 스택에 인덱스 또는 값을 저장
  2. 현재 값이 스택 top보다 크면, 해당 인덱스에 현재 값을 정답으로 기록하고 pop

 

📍 DFS (깊이 우선 탐색) 비재귀 구현

• 설명: 스택을 활용해 재귀 없이 DFS 구현

 

📍 백트래킹 시 스택 사용

• 설명: 경로 저장, 상태 복원 등을 위해 스택을 사용

 

---

🧠 스택 응용 팁

• 문제에 "최근 것" 또는 "되돌리기" 개념이 보이면 스택을 의심
• 문자열 문제에서도 스택을 많이 활용 (특히 중첩 구조 파악, 되돌리기, 중복 제거 등).

 

---

🕐 시간복잡도

삽입/삭제 O(1)