[묘공단] 2. 스택

1-1. 스택

 - 스택의 어원은 "쌓는다"

 - 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조 (선입선출)

 - 스택에 삽입하는 것은 push / 꺼내는 연산은 pop이라한다.

 - 정해진 방향으로 쌓을 수 있으며 top으로 정한 곳을 통해서만 접근 할수 있다. 자료 삭제도 top을 통해서 삭제가 가능하다.

 

 

1-2. 스택의 사용 사례

 

- 웹 브러우저 방문기록

-  실행 취소

- 역순 문자열 만들기

- 후위 표기법 계산

04-03. 후위 표기법(Postfix notation) #1 - 좌충우돌, 파이썬으로 자료구조 구현하기 (wikidocs.net)

04-03. 후위 표기법(Postfix notation) #1

 

2. 스택의 ADT

 - ADT : 추상 자료형 - 인터페이스만 있고 실제로 구현은 되지 않은 자료형

 

2-1. 정의

- boolean isFull()

• 스택에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean값을 반환
• 가득 차있다면 True / 아니면 False

- boolean isEmpty()

• 스택에 들어 있는 데이터가 하난도 없는지 확인해 boolean값을 반환
• 데이터가 하나라도 있으면 False / 아니면 True

- void push(Item Tpye item)

• 스택에 데이터를 푸시

- ItemType pop()

• 스택에서 최근에 푸시한 데이터를 pop하고 그 데이터를 반환

- Int pop

• 스택에서 최근에 푸시한 데이터의 위치를 기록

- ItemType data[maxsize]

• 스택의 데이터를 관리하는 배열.
• 최대의 maxsize를 관리

stack =  [] #스택 리스트 초기화
maxsize = 10 #스택의 최대 크기

def isFull(stack):
  #스택이 가득 찼는지 확인하는 함수
  return len(stack) == maxsize

def isEmpty(stack):
  #스택이 비어있는지 확인
  return  len(stack) == 0

def push(stack, item):
  #스택에 데이터를 추가하는 함수
  if isFull(stack):
    print("스택이 가득 찼습니다.")
  else:
    stack.append(item):
    print("데이터가 추가되었습니다")

 

3. 몸풀기 문제

 

3-1. 괄호 짝 맞추기

 

• 제약 조건
  • 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄됩니다.
  • 상쇄 조건은 열린 괄호가 먼저 와야하고, 열린 괄호와 닫힌 괄호 사이에 아무것도 없어야 합니다
  • 더 상쇄할 괄호가 없을 때까지 상쇄를 반복합니다.

def solution(s):
  stack = []
  for c in s:
    if c =="(":
      stack.append(c)
    elif c ==")":
      if not stack:
        return False
      else:
        stack.pop()
  if stack:
    return False
  else:
    return True

 

 

3-2. 10진수를 2진수로 변환하기

 

def solution(s):
  stack = []
  while s > 0:
    r  = s % 2 
    stack.append(str(r))
    s // = 2
    binary = ""
    while stack:
      binary += stack.pop()
  return binary