기술면접 질문

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

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

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

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

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

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)

| Operation | Average | Worst | | — | — | — | | Access | Θ(n) | O(n) | | Search | Θ(n) | O(n) | | Insert (=push) | Θ(1) | O(1) | | Delete (=pop) | Θ(1) | O(1) |

• 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을 이용해서 푸는 기본적이고 대표적인 문제

예시

출력

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)후위 표기법 수식을 계산하면 다음과 같다.

구현

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", "-"]))

• +) 중위표기법 ⇒ 후위표기법

    # step 1 : 리스트를 활용해 스택 준비
      
    class Stack:
    	def __int__(self):
    		self.items = []
      
    	def push(self, item):
    		self.items.append(item)
      
    	def pop(self):
    		return self.items.pop()
      	
    	def peek(self):
    			return self.items[-1]
      
    # step 2 : 수가 문자열로 주어져 있을 때 (몇자리수인지 모르는상태) 
    # 각각을 피연산자(수)와 연산자(기호)로 분리해서 리스트로 만드는 작업
      
    # exprStr -> 중위 표현식으로된 수식
      
    def splitTokens(exprStr):
        tokens = []
        val = 0                 # 각 자리 숫자를 담는 변수
        valProcessing = False   
          
        for c in exprStr:
            # 빈칸이 들어있으면 그냥 넘어감
            if c == ' ':
                continue
              
            # 숫자를 만나면 10진수로 변환하는 과정
            if c in '0123456789' :
                val = val * 10 + int(c)
                valProcessing = True # 수를 만났으므로 true
              
            # 숫자가 아니라면 (괄호 또는 연산자를 만났다고 간주) 10진수 표현이 끝난것
            else:
                if valProcessing:
                    tokens.append(val)
                    val = 0
                  
                valProcessing = False # 지금 10진수를 처리하고있지 않다
                tokens.append(c)
              
        # 마지막 수 처리
        if valProcessing:
            tokens.append(val)
              
        return tokens
      
    # 중위 표기법 -> 후위 표기법으로 바꾸는 함수
    def infixToPostfix(tokenList):
        prec = {
            '*' : 3,
            '/' : 3,
            '+' : 2,
            '-' : 2,
            '(' : 1
        }
          
        opStack = ArrayStack()
        postfixList = []
          
        for token in tokenList:
            # 피연산자이면 리스트에 추가
            if type(token) is int:
                postfixList.append(token)
                  
            # '('이면 스택에 push
            elif token == '(':
                opStack.push(token)
                  
            # ')' 이면 '('가 나올때까지 pop
            elif token == ')':
                while opStack.peek() != '(':
                    postfixList.append(opStack.pop())
                opStack.pop()
              
            # 연산자이면 +-*/
            else:
                # 스택이 비어있을 경우 스택에 push
                if opStack.isEmpty():
                    opStack.push(token)
                      
                # 스택이 비어있지 않다면 비교
                else:
                      
                    # 스택에 값이 존재할 동안에 반복
                    while opStack.size() > 0:
                        # 우선 순위가 스택안에 있는게 높으면 꺼낸다
                        if prec[opStack.peek()] >= prec[token]:
                            postfixList.append(opStack.pop())
                        else:
                            break
                      
                    opStack.push(token)
          
        # 반복문을 다 돌고 스택이 빌때까지 pop
        while not opStack.isEmpty():
            postfixList.append(opStack.pop())
          
        # 리스트로 리턴한다
        return postfixList
      
    # 후위 표기법을 계산하는 함수
    def postfixEval(tokenList):
        valStack = ArrayStack()
          
        for token in tokenList:
            # 피연산자를 만나면 스택에 push
            if type(token) is int:
                valStack.push(token)
                  
            # 연산자를 만나면
            elif token == '+':
                n1 = valStack.pop()
                n2 = valStack.pop()
                valStack.push(n2+n1)
              
            elif token == '-':
                n1 = valStack.pop()
                n2 = valStack.pop()
                valStack.push(n2-n1)
                  
            elif token == '*':
                n1 = valStack.pop()
                n2 = valStack.pop()
                valStack.push(n2*n1)
                  
            elif token == '/':
                n1 = valStack.pop()
                n2 = valStack.pop()
                valStack.push(int(n2/n1))
              
        return valStack.pop()
  

• 참고자료

  https://wisdom-and-record.tistory.com/5

  https://yoongrammer.tistory.com/45

  https://ehpub.co.kr/후위-표기-수식-계산-스택-계산기-코딩-테스트-python/