4. 스택 📚

---

📚 4.1 스택이란?

📚 스택은 후입선출(Last In Fist Out)의 자료구조!

면접에서 종종 나오는 문제이다. "스택과 큐의 차이는 무엇인가?" 와 같은 형태로 스택은 후입선출의 형태로 자료의 입출력이 일어난다. A,B,C,D 순서로 입력했다면 꺼낼 때는 D, C, B, A로만 꺼낼 수 있다. 이는 위의 뚜껑(후단)만을 열어둔 구조와 같다. 열린 곳을 보통 스택 상단(top)이라 부른다. 그래서 삽입과 삭제는 상단으로만 가능하며 중간으로의 삽입과 삭제는 불가하다.

📚 스택은 어디에 사용할까?

첨 들어온 애가 어떻게 먼저 나가!라고 생각할 수 있지만 역순으로 이뤄져야 할 출력에서 요긴하게 사용된다.

• 문서 그림 ctrl+Z처럼 되돌리기 기능을 구현할 때 스택이 사용된다. 가장 최근에 입력되었던 데이터로 이동해야 하며 지금까지 본 정보를 스택에 저장해야 한다.
• 아래에도 나오겠지만 소스코드에서 괄호 닫기가 정상적으로 수행됐는지 확인할 때도 스택을 사용한다. 또한 계산기 프로그램이 입력된 수식을 계산할 때도 스택이 사용된다.

---

📚 4.2 스택의 구현

배열구조를 이용한 함수의 구현

스택항목들을 저장하는 가장 간단한 방법은 배열 구조를 사용. 파이썬에서는 리스트를 사용한다. 이름을 top이라 하자. 이 리스트는 공백이 되어야 한다.

isEmpty() : 공백 상태 검사

def isEmpty():
	return len(top) == 0 #len(top) == 0 이 T/F

push(item): 삽입연산
삽입은 스택의 상단에 항목을 추가하는 것이다. 시간 복잡도를 생각하면 맨 뒤을 스택의 상단으로 사용하는 것이 좋다.

def push(item):
	top.append(item)

pop(): 삭제연산
삭제 연산은 스택 상단에 항목을 하나 꺼내고 이를 반환. 파이썬은 항목을 꺼내는 pop(위치) 연산을 제공. 매개변수로 꺼낼 항목의 위치를 전달해야 한다. -1은 맨 뒤의 항목을 꺼낸다.

def pop(): 
    if not isEmpty(): #🔥🔥🔥삭제는 공백 검사 꼭 해줘!🔥🔥🔥
    	return top.pop(-1)

삭제 연산도 항상 O(1)에 처리된다. 막 이동하고 그럴 필요 없기 때문에 그렇다. 익숙함에 속아 소중한 공백 검사를 잊지 말자! (과제나 셤에서 감점도 그렇지만 코드도,, 문제가 생긴다)

📚 기타 연산들

나머지 연산들도 간단히 구현된다. peek는 리스트의 마지막 항목을 반환하면된다. 스택 내용에는 변화가 없다. 물론 이 경우에도 공백이 아니어야 한다.

def peek():	#맨 위의 항목을 삭제하지 않고 반환
    if not isEmpty():
    return top[-1]

📚 배열 구조를 이용한 스택의 클래스 구현

여러 개의 스택이 필요해질 수 있기에 클래스로 선언해주자.

⚠️ 주의! ⚠️

• 생성자에 클래스의 데이터 멤버를 선언하고 초기화. 스택의 유일한 데이터인 top을 리스트로 선언
• 모든 메소드의 첫 번째 파라미터로 self를 추가
• 모든 메소드에서 클래스의 멤버를 사용할 때 self.을 추가하여 클래스 내의 변수(데이터 멤버) 및 함수(메소드)임을 표시한다.

class stack
    def __init__(self): #생성자
        self.top = []   #초기화
        
    def isEmpty(self): return len(self.top) == 0 #비었당
    def size(self): return len(sel.top) #들었당
    def clear(self) : return self.top = [] #다시 초기화
    
    def push(self, item):
        self.top.append(item)
        
    def pop(self):
        if not isEmpty():
    	    return self.top.pop(-1)
            
    def peek(self):
        if not isEmpty():
    	    return self.top[-1]


🔥 이상 모두 상수 시간 걸림 🔥 
이후에 쓰려면? S = stack()처럼 불러오고 
for i in range(10):
	S.push(i) 
    
    등으로 써주면 됨!
            

---

📚 4.3 스택의 응용 : 괄호 검사

괄호는 가장 가까운 거리에 있는 괄호끼리 서로 쌍을 이뤄야 함을 알 수 있다. 우선은 책에서의 구현을 살펴보고 비슷한 예제로 백준에도 있었다. 여기서는 라이브러리를 import해서 해결해봄!

def checkBrackets(state):
    s = Stack()
    for ch in state:
        if ch in ('{', '[', '('):
            stack.push(ch)
        
        elif ch in ('}', ']', ')'):
             if s.isEmpty():
                return False   #비었으면 왜하닝 
        
             else:  # 🔥else는 비어있지 않으면의 의미! 들여쓰기 조심
                 left = s.pop()
                 if (ch == '}' and left !='{') or
                 if (ch == ']' and left !='[') or
                 (ch == ')' and left !='(')   #괄호가 짝지어지지 않았다면
                 return False 
                 
         return s.isEmpty()
                

이건 배운거구 이제 적용해보자.
요 문제이다

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

num = int(input())
    
    for i in range(num):
        stack = [] #초기화
        state = input() #받아오기
        
        for toke in state:
            if token == '(':
                stack.append (token)
                
            elif token == ')':
                 if stack:
                    stack.pop()
                
                else:
                     print("NO")
                     breack 
                     
            else:
                if not stack: print('Yes')
                else : print('NO')
                
        

요렇게 해결했다. 실제 테스트나 이후에는 변수명을 좀 더 축약해야겠다.

---

📚 4.4 스택의 응용 : 수식의 계산

def evalPost(exp):
    s = Stack()
    
    for token in exp:
        if token in "+-*/": 연산자에 들어 있다면 
           val2 = s.pop() 	#피연산자2
           val1 = s.pop() 	#피연산자1
           
           if(token == '+'): s.push(val1 + val2) 
           elif(token == '-'): s.push(val1 - val2)
           elif(token == '*'): s.push(val1 * val2)
           elif(token == '/'): s.push(val1 / val2) 
           #연산 수행, 결과는 스택에 다시 저장
           
         else:			  #항목이 피연산자이면 
             s.push(float(token)) #실수로 변경해서 스택에 저장
             
     return s.pop() #최종결과를 반환

📚 중위표기식의 후위 변환 구현

def precedence(op):
    if op == '(' or op==')' : return 0 #괄호를 가장 낮게 
    elif op == '+' or op == '-' : return 1 
    elif op == '*' or op == '/' : return 2 
   	else: return -1

먼저 연산자들의 우선순위를 정하는 함수를 구현해야 한다. 여는 괄호는 쌓기 위해서 우선순위가 가장 낮아야 하므로 0을 반환. + - 는 우선순위가 1, * / 은 젤 높은 2 부여.

def Infixpost(exp):
    s = Stack()
    output = []
    
    for term in expr : 
        if term in '(':
           s.push('(') 
           
        elif term in ')':
             while not s.isEmpty():
             op = s.pop()
             if op == '(' : break;	#왼쪽 괄호가 나올 때까지 계속 끄내!
             else :
                  output.append(op)
                  
        elif term in "+-*/":			#연산자이면
             while not s.isEmpty():		#비지 않았을 때
                   op = s.peek()		#스택에서 모두 꺼내
                   if(precedence(term) <= precedence(op)): 
			#우선순위가 높거나 같은 연산자를
                      output.append(op)
                      s.pop()
                   else:break
              s.push(term)
          else:
              output.append(term)
              
         while not s.isEmpty():
              output.apppend(s.pop())
              
              
         return output 
     

---