[자료구조] 스택(Stack)

 

스택(Stack)은 후입선출(LIFO), 원칙을 따르는 자료구조입니다. 즉, 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조입니다.

특징

• LIFO 구조
  • 후입선출 구조로, 가장 나중에 들어온 데이터가 가장 먼저 나갑니다.
  • 예) 상자를 쌓아 올리고, 맨 위에서부터 차례로 꺼냄, 프링글스 과자
• 한쪽 끝에서만 접근가능
  • 데이터를 삽입 & 제거할 때 항상 맨 위(Top)에서만 가능합니다.
• 순서가 중요함
  • 데이터의 순서에 민감한 문제를 해결할 때 유용합니다.
  • 예) 짝 맞추기, 경로 탐색

---

💡 핵심 포인트

스택의 동작 원리에 대해 알아봅시다. 스택은 상자를 쌓는 것처럼 데이터를 위에서부터 차례로 쌓아 올리고(push), 나중에 쌓은 데이터를 맨 위에서부터 차례로 꺼내는(pop) 방식으로 동작합니다.

 

스택의 기본 연산

• Stack 생성
  • 예시)

   import java.util.Stack;
   
   Stack<Integer> stack = new Stack<>();
  

• Push
  • 데이터를 스택 맨 위에 추가합니다.
  • 예시)

  스택: [A, B]
  -> stack.push(C)
  -> [A, B, C]
  

• Pop
  • 맨 위의 데이터를 삭제합니다.
  • 예시)

  스택: [A, B, C]
  -> stack.pop()  //가장 위의 데이터만 삭제할 수 있습니다.
  -> [A, B]
  

• Peek
  • 맨 위의 데이터를 제거하지 않고 확인합니다.
  • 예시)

  스택: [A, B, C]
  -> stack.peek()
  -> C
  

• isEmpty()
  • 스택이 비어있는지 확인합니다.
  • 예시)

  스택: [A, B, C]
  -> stack.isEmpty()
  -> false
  
  스택: []
  -> stack.isEmpty()
  -> true
  

• search()
  
  • 인자 값을 스택에서 검색하여 우선순위를 출력합니다.
  • 인자 값으로 2를 주면 3번째로 출력되기때문에 3을 출력합니다.
  • 스택에 인자 값이 여러개라면 가장 높은 우선순위를 출력합니다.
  • 스택에 없는 값을 검색하면 -1을 출력합니다.

[스택]: 1, 2, 3, 1
-> stack.search(2)
-> 출력: 3
-> stack.search(1)
-> 출력: 4
-> stack.search(5)
-> 출력: -1

📜 코드 예시

java
# 코드 예시
public class Main {
	public static void main(String[] args){
		Stack<Integer> stack = new Stack<>();
		stack.push(1)
		stack.push(2)
		stack.push(0)
		
		System.out.println(stack.pop())  //0
		System.out.println(stack.pekk()) //2
		
		/* 이후 스택의 값 [1, 2] */
		
	}

}

---

📝 적용 문제

알고리즘/자료구조를 사용한 문제 예시와 간단한 설명

• 문제: [12909] 올바른 괄호
• 해결 방법: 괄호의 짝이 맞을 경우 true, 안 맞을 경우 false를 return하는 방식으로, 괄호가 담겨져있는 문자열 String을 for문을 통해 한 문자씩 Charactor로 변환하여 ‘(’일 경우 Stack에 추가(push) 해주었고, ‘)’일 경우 Stack에서 지워주었다(pop). 만약 ‘)’가 더 존재하는데 스택이 비어있다면 (stack.isEmpty()) false를 바로 반환해주었고, 반복문을 다 돌았을 때 스택이 비어있다면 짝이 맞는 것이고, 스택이 안비어있다면 짝이 맞지않는 것 이니 answer에 stack.isEmpty()를 담아 결과를 리턴해주었다.

---

✅ 학습 회고

스택에 대해 알아보는 시간을 가졌다. 자료구조의 지식이 많지 않아 항상 수 맞추기 등의 문제는 긴 코드로 하나하나 중첩 for문과 중첩 if문을 반복하여서 사용하여 코드가 더러워지고 알아보기 힘들었었는데 스택을 통해 관리하면 쉽게 문제를 풀 수 있다는 것을 깨달았다! 앞으로 사용 할 일이 많을 것 같으니 꾸준히 복습하자.

 

 

---

 

노션에서 작성 된 글이므로 내용에 누락이 있을 수 있습니다. 🙂

자세한 내용은 노션에서 확인해주세요.

http://hail-buttercup-c86.notion.site

Stack | Notion