[자료구조] 스택(Stack)

📌기술면접 질문

Q. 스택(Stack)에 대해 설명하고 예제소스를 구현해보아라

Q. 스택과 큐의 차이는 무엇일까요?

Q. 화이트보드에 큐로 스택을 구현해 보라. (넥슨)

Q. 스택과 링크드리스트와 리스트의 차이점을 설명해 보세요. (네이버)

Q. 스택 오버플로우가 왜 일어나는가?

 

Stack

---

• 스택 : 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조
• 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out)방식을 사용
• 스택공간이 가득찼을 때 데이터를 더 넣으려고 할 경우 프로그램에 오류가 발생하는 것을 Overflow 상태라고 하며, 반대로 스택 저장공간에 데이터가 없는데 프로그램에서 스택에서 데이터를 꺼내려고 할 경우 프로그램에 오류가 발생하는 것을 Underflow 상태라고 함
• 삽입(Push)과 제거(Pop)는 모두 Top이라는 스택의 한쪽 끝에서만 일어남

 

스택의 구현 : 연산

---

스택은 아래 연산들로 추상화할 수 있다.

• push - 스택 맨위에 항목을 삽입
• pop - 스택 맨위에 항목 삭제
• peek - 스택의 맨 위(top)를 표시 (읽기 : 원본이 유지됨)
• isEmpty - 스택이 비어있는지 확인
• isFull - 스택이 가득 차 있는지 확인
• getSize - 스택에 있는 요소 수를 반환

 

기본동작

---

Push

데이터를 스택에 넣는 작업을 push 라고 한다. push는 다음 단계를 거친다.

• 1 단계 - 스택이 가득 찼는 지 확인
• 2 단계 - 스택이 가득 차면 오류가 발생하고 종료된다.
• 3 단계 - 스택이 가득 차지 않으면 Top을 증가시킨다.
• 4 단계 - Top이 가리키는 스택 위치에 데이터를 추가한다.

 

Pop

데이터를 스택에 제거하는 작업을 pop이라고 한다. pop은 다음 단계를 거친다.

• 1 단계 - 스택이 비어 있는지 확인한다.
• 2 단계 - 스택이 비어 있으면 오류가 발생하고 종료한다.
• 3 단계 - 스택이 비어 있지 않으면 Top 이 가리키는 데이터를 제거한다.
• 4 단계 - Top 값을 감소시킨다.
• 5 단계 - 성공을 반환한다.

 

시간복잡도 (Time Complexity)

---

 

• push(), pop()의 시간복잡도는 늘 O(1) : 삽입, 삭제가 항상 Top에서만 일어나기 때문
• search()의 시간복잡도 O(n) : 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하기 때문

 

구현

---

구현 방법에는 두 가지가 있다.

배열 사용 (C언어 등)

• 장점 : 구현하기 쉬움
• 단점 : 크기가 동적이 아님. 런타임시 필요에 따라 늘거나 줄지 않음

연결리스트 사용

• 장점 : 크기가 동적임. 런타임시 필요에 따라 크기가 확장 및 축소될 수 있음
• 단점 : 포인터를 위한 추가 메모리 공간이 필요함

 

class Stack:
	def __int__(self):                   # 데이터 저장을 위한 리스트 준비 ([special method](https://www.notion.so/special-method-c7a701bed79c4e1ea37a5231ac996af1))
		self.items = []

	def push(self, val):
		self.items.append(val)

	def pop(self):
		try
			return self.items.pop()  
		except IndexError:                  # pop할 아이템이 없으면
			print("Stack is empty")           # indexError 발생

	def peek(self):
		try:
			return self.items[-1]
		except IndexError:
			print("Stack is empty")
	
	def __len__(self):                     # len()로 호출하면 stack의 item 수 반환
		return len(self.items)

 

 

스택의 활용

---

예제 1. 괄호 검사

stack을 이용해서 푸는 기본적이고 대표적인 문제

❓ 주어진 입력에서 괄호 {}, ()가 제대로 짝을 이뤘는지 검사하는 프로그램을 만드시오. - 예를 들어 {( )}는 제대로 된 짝이지만, {( })는 제대로 된 짝이 아니다. - 입력은 한 줄의 파이썬 코드일수도 있고, 괄호만 주어질 수도 있다. - 정상적으로 짝을 이룬 경우 1, 그렇지 않으면 0을 출력한다. - print(‘{‘) 같은 경우는 입력으로 주어지지 않으므로 고려하지 않아도 된다. - 각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

출력

3
print({} {}'.format(1,2))
N, M = map(int, input(), split())
print('#{} {}'.format(tc, find())

#1 1
#2 1
#3 0

코드

def bracket_check(val):                          # 괄호의 짝 딕셔너리
    matching_dict = {'}': '{', ')': '('}
    stack = []

    for i in val:
        if i in ('{', '('):                      # 열린 괄호를 찾으면 스택에 push
            stack.append(i)

        elif i in ('}', ')'):                    # 닫힌 괄호를 찾으면              
            if not stack or stack[len(stack) - 1] != matching_dict[i]:         # 스택이 비어있거나 괄호의 짝이 맞지 않으면
                return 0
            else:
								stack.pop()  # 짝이 맞으면 pop

    if stack:                                      # 검사 후에도 스택에 괄호가 남아 있으면
        return 0
    else:
        return 1

T = int(input())
for tc in range(T):
    print('#%d %d' % (tc + 1, bracket_check(input())))

---

 

예제 2 : 후위 표기 수식의 계산

중위 표기법과 후위 표기법

• 중위 표기법 (infix notation)
  • 우리가 일상에서 사용하는 수식의 표기법
  • 연산자가 피연산자들의 사이에 위치
• (A + B) * (C + D)
• 후위 표기법 (postfix notation)
  • 컴퓨터가 수식을 계산하는데 유리함
  • 연산자가 피연산자들의 뒤에 위치
• A B + C D + *

 

-> 스택으로 구현할 수 있는 대표적인 예시로는

1. 중위 표기법 수식을 후위 표기법 수식으로 변환하는 알고리즘
2. 후위 표기법 수식을 계산하는 알고리즘

이 있다.

 

⇒ 리스트를 활용하여 2. 후위 표기법 수식을 계산하면 다음과 같다.

❓ 입력: {“2”, “3”, “5”, “+”, “*”, “7”, “-“} 출력: 10

구현

def Calculate(tokens):
    stack = []
    for token in tokens:
        if token == '+':
            stack.append(stack.pop()+stack.pop())
        elif token == '-':
            stack.append(-(stack.pop()-stack.pop()))
        elif token == '*':
            stack.append(stack.pop()*stack.pop())
        elif token == '/':
            rv = stack.pop()
            stack.append(stack.pop()/rv)
        else:
            stack.append(int(token))
    return stack.pop()
 
print(Calculate(["2", "3", "5", "*", "+", "7", "-"]))

 

• 참고자료
  • https://yoongrammer.tistory.com/45
  • https://ehpub.co.kr/후위-표기-수식-계산-스택-계산기-코딩-테스트-python/
  • https://wisdom-and-record.tistory.com/5