[자료구조] 스택

1. 스택의 개념과 동작 원리

 (1) 스택의 기본 개념

  - 스택 : 쌓아놓은 더미

  - 후입 선출((LIFO) : 가장 최근에 들어간 데이터가 가장 먼저 나감

 [Stack ADT]

  - Stack() : 비어있는 새로운 스택을 만듬

  - inEmpty() : 스택이 비어있으면 True를 아니면 False를 반환함

  - push(e) : 항목 e를 스택의 맨 위에 추가함

  - peek() : 스택의 맨위에 있는 항목을 삭제하지 않고 반환함

  - size() : 스택 내의 모든 항목들의 개수를 반환함

  - clear() : 스택을 공백 상태로 만듬

  - 스택의 용도 : 되돌리기, 함수 호출, 괄호 검사, 미로 탐색 

 (2) 스택의 구현

  - 배열을 이용한 구현 : 항목 삽입.삭제의 위치는 리스트 맨 뒤가 유리

2. 스택의 응용

 (1) 괄호 검사

  [조건]

  - 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 함

  - 같은 타입의 괄호에서 왼쪽 괄호가 오른쪽 괄호가 먼저 나와야 함

  - 서로 다른 타입의 괄호 쌍이 서로 교차하면 안됨

  [방법]

  - 스택 정의

  - 입력 문자열의 문자를 하나씩 읽어 왼쪽 괄호를 만나면 스택에 삽입함

  - 오른쪽 괄호를 만나면 pop()연산으로 가장 최근에 삽입된 괄호를 꺼낸다

     > 스택이 비었으면 return error

     > 꺼낸 괄호와 오른쪽 괄호의 짝이 맞지 않으면 return error

  - 끝까지 처리했는데 괄호가 남아있으면 return error

  - 아무것도 없이 정상 처리된 경우 return True

 (2) 계산기

  - 수식 표기 방법 : 중위(5+a*b) 전위(+5*ab) 후위(5ab*+)

  - 컴퓨터는 우선 순위를 신경쓰지 않는 후위 연산을 선호

  - 8 2 / 3 - 3 2 * + = 8 / 2 > 4 - 3 > 1 + (3 * 2) = 7

  - 

 (3) 미로 탐색

 (4) 실습

Class로 스택 ADT 구현 class Stack :     def __init__(self) :         self.top = []     def isEmpty(self) : return len(self.top)==0     def size(self) : return len(self.top)     def clear(self) : self.top = []     def push(self, item) : self.top.append(item)     def pop(self) :         if not self.isEmpty() : return self.top.pop(-1)     def peek(self) :         if not self.isEmpty() : return self.top[-1]     def __str__(self) :         return str(self.top[::-1]) print('even : ', even.top) print('odd : ', odd.top) print('even peek : ', even.peek(), ' odd peek : ', odd.peek()) for _ in range(2) : even.pop() print('even : ', even.top)

 

괄호 검사 def check(stat) :     stack = Stack()     for ch in stat :         if ch in "{[(" :             stack.push(ch)         elif ch in "}])" :             if stack.isEmpty() :                 return False             else :                 left = stack.pop()                 if (ch == "}" and left != "{") or \                    (ch == ")" and left != "(") or \                    (ch == "]" and left != "[") :                     return False     return stack.isEmpty() st1 = ("{A[(i+1)] = 0;}", "if((i=0)&&(j==0)}", "A[(i+1])") for s in st1 :     m = check(s)     print(s, "--->",m)

계산기 def pfix(ex) :     s = Stack()     for tk in ex :         if tk in "+-*/" :             val2 = s.pop()             val1 = s.pop()             if (tk == '+') : s.push(val1+val2)             elif (tk == '-') : s.push(val1-val2)             elif (tk == '*') : s.push(val1*val2)             elif (tk == '/') : s.push(val1/val2)         else :             s.push(float(tk))     return s.pop() exp1 = ['8','2','/','3','-','3','2','*','+'] print(exp1, '---->', pfix(exp1)) 중위 계산 def pre (op) :     if op == '(' or op == ')' : return 0     elif op == '+' or op == '-' : return 2     else : return 1 def midp(exp) :     s = Stack()     output = []     for term in exp :         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 (pre(term) <= pre(op)) :                     output.append(op)                     s.pop()                 else : break             s.push(term)         else :             output.append(term)     while not s.isEmpty() :         output.append(s.pop())     return output infix1 = ['8','/','2','-','3','+','(','3','*','2',')'] profix = midp(infix1) print(profix)

미로 탐색 class Stack :     def __init__(self) :         self.top = []     def isEmpty(self) : return len(self.top)==0     def size(self) : return len(self.top)     def clear(self) : self.top = []     def push(self, item) : self.top.append(item)     def pop(self) :         if not self.isEmpty() : return self.top.pop(-1)     def peek(self) :         if not self.isEmpty() : return self.top[-1]     def __str__(self) :         return str(self.top[::-1]) MAX_SIZE = 6 def vaild(x, y) :     if x<0 or y<0 or x>=MAX_SIZE or y>=MAX_SIZE :         return False     else :         return map[y][x] == '0' or map[y][x] == 'x'   def DFS() :     stack = Stack()     stack.push((0,1))     print('DFS')     while not stack.isEmpty():         here = stack.pop()         print(here, end='->')         (x, y) = here         if(map[y][x] == 'x') :            return True         else :             map[y][x] = '.'             if vaild(x, y-1) : stack.push((x,y-1))             if vaild(x, y+1) : stack.push((x,y+1))             if vaild(x-1, y) : stack.push((x-1,y))             if vaild(x+1, y) : stack.push((x+1,y))         print(stack)     return False map = [['1','1','1','1','1','1'],        ['e','0','0','0','0','1'],        ['1','0','1','0','1','1'],        ['1','1','1','0','0','x'],        ['1','1','1','0','1','1'],        ['1','1','1','1','1','1']] result = DFS() print(result)