rldnd
rldnd
스택, 큐, 덱 - algorithm[2]

스택, 큐, 덱 - algorithm[2]

Tag
Algorithm

스택

FILO(First In Last Out)
notion image
  1. 원소의 추가가 O(1)
  1. 원소의 제거가 O(1)
  1. 제일 상단의 원소 확인이 O(1)
  1. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
 

큐

notion image
한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조.
 
  1. 원소의 추가가 O(1)
  1. 원소의 제거가 O(1)
  1. 제일 앞/뒤의 원소 확인이 O(1)
  1. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
 

Circular Queue

notion image
 

덱

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

스택의 활용

수식의 괄호 쌍이란?

주어진 괄호 문자열이 올바른지 판단하는 문제
32-{6-(2+4)*7} => {()} 정상
5+{6-(12+4}*7} => {(}) 비정상
 
⇒ 푸는 방법은 연결 리스트로 구현하면 해볼만 하지만, 스택이 제일 쉽다.
 
📌
문자열을 앞에서 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다.
 

문제 해결 방법

  1. 여는 괄호가 나오면 스택에 추가
  1. 닫는 괄호가 나왔을 경우,
    1. 스택이 비어있으면 올바르지 않은 괄호 쌍
    2. 스택의 top이 짝이 맞지 않는 괄호일경우 올바르지 않은 괄호 쌍
    3. 스택의 top이 짝이 맞는 괄호일 경우 pop
  1. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍
Copyright 2023 rldnd