[자료구조] 3. 스택

3강. 스택

1. 스택의 개념

💡 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형 가장 나중에 들어온 자료가 가장 먼저 나가는 형태(LIFO, 후입선출)

• TOP : 스택에서 가장 최근에 삽입 된 자료의 메모리 주소를 지칭
• push : 스택에 자료 하나를 삽입하는 함수. 스택의 저장공간이 충분한지 확인해야 한다.
• pop : 스택의 최상단 자료형을 반환(제거) 하는 함수. 스택에 데이터가 존재하는지 확인해야 한다.

2. 스택의 추상 자료형

1. Stack CreateS(maxStackSize)
2. 스택의 크기가 maxStackSize인 빈 스택을 생성하고 반환한다.
3. Boolean IsFull(stack, maxStackSize)
4. 스택이 가득 찼는지 여부를 확인하여 반환한다.
5. Stack Push(stack, item)
6. 스택이 가득 차지 않았다면 최상단 메모리에 데이터를 삽입한다.
7. Boolean IsEmpty(stack)
8. 스택에 자료가 하나도 존재하지 않는지 여부를 확인하여 반환한다.
9. Element Pop(stack)
10. 스택이 비어있는지 확인한 뒤 그렇지 않다면 최상단의 자료를 꺼내 삭제하고 반환한다.

3. 스택의 응용

1. 시스템 스택(system stack)
2. 변수의 생명주기 관리를 위해 사용
3. 서브루틴 호출(subroutine call)
4. 서브루틴의 수행이 끝난 후 되돌아갈 함수 주소를 저장하기 위해 사용
5. 수식 계산(evaluation of expression)
6. 연산자들 간의 우선순위에 의해 계산 순서를 결정
7. 인터럽트(interrupt) 처리와 처리 후 되돌아갈 명령 수행지점 저장
8. 컴파일러의 문법 검사, 순환 호출 등…

4. 스택의 연산

직접 구현으로 정리

5. 배열을 이용한 스택의 구현

직접 구현으로 정리

파이썬을 이용한 스택 구현

class Stack:      # 스택 메모리를 저장할 변수     # 생성과 동시에 초기화 됨. 외부에서 접근하지 못하도록 private 하게 선언해야 함.     # 멤버 변수 앞에 '__'를 붙이면 외부에서 접근할 수 없음     __node = None      # 스택 최상단 인덱스를 가르키는 함수     # None 으로 선언할 시 증감연산자에서 에러가 나므로 -1로 선언     top = -1      # 스택 최대 저장공간     max_stack_size = 0      # 스택 객체 초기화와 동시에 선언     def __init__(self, max_stack_size_p):         self.__node = list()         self.max_stack_size = max_stack_size_p      # 스택이 가득 찼는지 확인하는 함수     # 스택의 최상단의 주소가 가르키는 값이 스택의 메모리 최대값 주소와 일치할 때          # is_full True 를 리턴한다.     def is_full(self):         if self.top == self.max_stack_size - 1:             return True         else:             return False      # 스택에 object 를 하나 밀어넣는 함수     # 스택에 공간이 있다면 원소를 하나 추가하고 그렇지 않다면 반환함     def push(self, item):         if self.is_full():             print('this stack is full')         else:             self.__node.append(item)             self.top += 1             return self      # 스택에 자료가 존재하는지 확인하는 함수     # 자료가 없다면 true 를 반환하고 그렇지 않다면 false 를 반환함     def is_empty(self):         if self.top < 0:             return True         else:             return False      # 스택 메모리 최상단 자료를 삭제하고 반환하는 함수     # 스택이 비어있지 않다면 실행 가능     def pop(self):         if self.is_empty():             print('this stack is empty')         else:             self.top -= 1             return self.__node.pop()

6. 사칙연산식의 중위/후위/중위 표현

💡 일반적으로 사용하는 수식의 형태는 '중위 표기법' 이고, 컴퓨터가 연산자의 우선순위를 결정하여 이를 효율적으로 계산하기 위해서는 '후위 표기법'으로 변환 할 필요가 있음

6.1 전위 표기법

연산자를 피연산자 앞에 가져다 놓는 방법 ex) 'A+B' → '+AB'

스택을 사용하여 처리하기 상당히 복잡함. 사람이 하는게 더 빠름

6.2 후위 표기법

A + B를 AB+ 와 같이 표현하는 기법. 컴퓨터가 해석하기 좋음

ex) E + (A - B) * C/D → E(((AB-)C*)D/)+