교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)
4.1 스택 (stack)
1) 스택
- 선형 리스트의 특별한 형태
- 나중에 들어가는 원소가 가장 먼저 나오는 후입선출(LIFO; Last In First Out) 구조
- 함수 호출 관리, 문법 검사(syntax checking), 수식 평가(expression evalution) 등에 많이 사용한다.
- top : 마지막으로 추가된 원소를 가리키는 변수
- push : 스택에 원소를 추가하는 연산
- pop : 스택에서 원소를 삭제하는 연산
- 정적 배열로 스택을 구현할 경우, push 함수는 스택에 원소를 추가하기 전에 'stack full' 상태인지, pop 함수는 스택에서 원소를 꺼내기 전에 스택이 빈 상태(top이 -1)인지를 검사한다.
2) 코드로 구현
class Stack:
def __init__(self, size):
self.top = -1
self.stack = []
self.size =size
def push(self, item):
if self.top < (self.size -1):
self.top += 1
self.stack.append(item)
self.show_stack()
else:
print("Stack Full")
def pop(self):
if self.top >-1:
self.top -= 1
return self.stack.pop()
else:
print("Stack Empty")
def show_stack(self):
print(self.stack)
4.2 선형 큐 (linear queue)
1) 선형 큐
- 큐(queue) : 작업들이 처리되기 전에 대기하고 있는 선형 리스트 자료구조
- 선형 큐 : 큐의 시작과 끝이 분리되어 있는 구조
- 순환 큐 : 양 끝이 연결된 구조
2) 큐의 구현
- 파이썬의 리스트 이용
- front : 큐의 앞을 가리키는 변수
- rear : 큐의 뒤를 가리키는 변수
- push : 큐에서 원소를 추가하는 연산
- pop : 큐에서 원소를 삭제하는 연산
- 연산을 수행하기 전에 큐에 가득 차 있는지(push),비어 있는지(pop) 확인해야 한다.
3) 코드로 구현
class Queue:
def __init__(self, size):
self.front = -1
self.rear = -1
self.queue = []
self.size =size
def isEmpty(self):
return len(self.queue) == 0
def isFull(self):
return len(self.queue) == self.size
def push(self, item):
if not self.isFull():
self.rear += 1
self.queue.append(item)
self.show_queue()
else:
print("Queue Full")
def pop(self):
if not self.isEmpty():
self.front+=1
return self.queue.pop(0)
else:
print("Queue Empty")
def show_queue(self):
print(self.queue)
4.3 순환 큐 (circular queue)
1) 순환 큐
- 선형 큐의 경우 원소의 추가 삭제 시 rear, front 값이 계속 증가한다.
- 원소들이 큐의 오른쪽에만 몰려 왼쪽에는 빈 공간이 생기게 된다.
- rear 변수에 의해 큐에 가득 찼다는 신호를 받아도 실제 내부에는 빈 공간이 있을 수 있다.
- 큐의 빈 공간을 재사용하기 위해 원소들을 왼쪽으로 이동시키는 작업을 해야 한다.
- 순환 큐 : 선형 큐의 단점을 개선한 자료구조
- 큐의 양쪽 끝을 서로 연결하여 원소의 이동 작업 없이 전체 공간을 모두 사용할 수 있다.
- front, rear 변수의 초기값을 0으로 설정하고, 최소 한 개의 빈 공간을 두거나 count 변수를 사용해 추가된 원소의 개수를 기억해야 한다.
- 고정 크기의 순환 큐를 구현할 때 None 값으로 미리 큐의 모든 공간을 채워둔다.
self.cqueue = [None] * self.size
self.rear = (self.rear + 1) % self.size
self.front = (self.front + 1) % self.size
2) 코드로 구현
class CQueue:
def __init__(self, size):
self.front = 0
self.rear = 0
self.count = 0
self.cqueue = []
self.size =size
def empty(self):
return self.count == 0
def full(self):
return self.count == self.size
def view(self, size):
print(self.cqueue, 'F=%d R=%d' %(self.front, self.rear))
def push(self, item):
if not self.full():
print("Push %2d" % item, end=' ')
self.rear = (self.rear+1)%self.size
self.cqueue[self.rear] = item
self.view()
self.count+=1
else:
print("Queue Full")
def pop(self):
if not self.empty():
print("Pop ", end=' ')
self.front = (self.front+1)%self.size
item = self.cqueue[self.front]
self.cqueue[self.front] = None
self.view()
self.count-=1
return item
else:
print("Queue Empty")
4.4 순환 데크 (circular deque)
1) 순환 데크
- 데크(Deque : double ended queue) : 큐의 앞(front), 뒤(rear) 모두에서 원소의 추가, 삭제가 발생한다.
- 순환 데크는 데크의 앞과 뒤가 서로 연결된 구조이다.
- 다음과 같은 함수가 필요하다.
| 데크 함수 | 작업 |
| add_front() | front 위치에 원소 저장 후 front 감소 |
| del_front() | front를 증가시키고 front의 원소 삭제 |
| add_rear() | rear를 증가시키고 원소 증가 |
| del_rear() | rear의 원소를 삭제하고 rear 감소 |
2) 코드로 구현
class CDeque:
def __init__(self, size):
self.front = 0
self.rear = 0
self.size = size
self.cdeque = []
self.count = 0
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.size
def show_deque(self):
print(self.cdeque,'FR', self.frot, self.rear)
def add_rear(self, item):
print("Add Rear %2d" & item, end = ' ')
if not self.isFull():
self.rear = (self.rear+1)%self.size
self.cdeque[self.rear] = item
self.show_deque()
self.count+=1
else:
print("=> Deque Full")
def add_front(self, item):
print("Add Front %2d" & item, end = ' ')
if not self.isFull():
self.cdeque[self.front] = item
self.front = (self.front-1+self.size)%self.size
self.show_deque()
self.count+=1
else:
print("=> Deque Full")
def del_front(self):
print("Del Front ", end = ' ')
if not self.isEmpty():
self.front = (self.front+1)%self.size
item = self.cdeque[self.front]
self.cdeque[self.front] = None
self.count -= 1
self.show_deque()
return item
else:
print("=> Deque Empty")
def del_rear(self):
print("Del Rear ", end = ' ')
if not self.isEmpty():
item = self.cdeque[self.rear]
self.cdeque[self.rear] = None
self.rear = (self.rear-1+self.size)%self.size
self.count -= 1
self.show_deque()
return item
else:
print("=> Deque Empty")
4.5 수식의 표현과 평가
1) 수식 표기법
- 수식(expression)은 연산자(operator)와 피연산자(operand)의 조합으로 구성된다.
- 수식 표기법은 피연산자에 대한 연산자의 위치에 따라 중위 표기법(infix), 후위 표기법(postfix), 전위 표기법(prefix)으로 나뉜다.
- 중위 수식
- 순서 : 피연산자 연산자 피연산자
- 각 연산자별로 우선순위가 있으며, 괄호를 사용하여 우선 순위를 바꿀 수 있다.
- 계산 순서가 복잡하다.
- 사람이 이해하기 쉬우나, 연산 순서가 복잡하여 프로그래밍이 어렵다.
- ex) 5 + 9 * 7
- 후위 수식
- 순서 : 피연산자 피연산자 연산자
- 연산자의 우선순위가 없고 괄호를 사용하지 않는다.
- 왼쪽에서 오른쪽 방향으로 1회 스캔하여 계산하므로 프로그래밍이 쉽지만 사람이 직관적으로 이해하기 어렵다.
- ex) 5 9 7 * +
2) 후위 수식 계산하기
- 알고리즘
- 후위 수식(expr)에서 읽은 토큰(token)이 피연산자이면 스택에 넣는다.
- 토큰이 연산자이면 스택에서 피연산자 2개를 꺼내서 계산한 후 그 결과 값을 다시 스택에 넣는다
- 모든 토큰이 입력되면 스택에 마지막으로 저장된 계산값을 꺼내 반환한다.
- 코드
class Sym:
OPEN_B = 1
CLOSE_B = 2
PLUS = 3
MINUS = 4
TIMES = 5
DIVIDE = 6
MOD = 7
OPERAND = 8
class Expression:
def __init__(self,expr):
self.stack = []
self.size = 100
self.expr= expr
self.top=-1
def push(self, item):
self.top+=1
self.stack.append(item)
self.stack_show()
def pop(self):
if len(self.stack) > 0:
self.top -=1
return self.stack.pop()
else:
print("Stack Empty")
def show_stack(self):
print(self.stack)
def eval_postfix(self):
for sym in self.expr:
print(sym, end=' ')
sym_type = self.getSymtype(sym)
if sym_type == Sym.OPERAND:
self.push(int(sym))
else:
op2 = self.pop()
op1 = self.pop()
if sym_type == Sym.PLUS:
self.push(op1 + op2)
elif sym_type == Sym.MINUS:
self.push(op1 - op2)
elif sym_type== Sym.TIMES:
self.push(op1 * op2)
elif sym_type == Sym.DIVIDE:
self.push(op1 / op2)
elif sym_type== Sym.MOD:
self.push(op1 % op2)
return self.pop()
def getSymtype(self, sym):
if sym == '(':
sym_type = Sym.OPEN_B
elif sym == ')':
sym_type = Sym.CLOSE_B
elif sym == '+':
sym_type = Sym.PLUS
elif sym == '-':
sym_type = Sym.MINUS
elif sym == '*':
sym_type = Sym.TIMES
elif sym == '/':
sym_type = Sym.DIVIDE
elif sym == '%':
sym_type = Sym.MOD
else:
sym_type = Sym.OPERAND
return sym_type
3) 중위 수식을 후위 수식으로 바꾸기
- 알고리즘
- 중위 수식의 토큰(token)이 피연산자(operand)이면 그대로 후위 수식으로 출력한다.
- 토큰이 연산자인 경우 스택이 비어 있거나, 스택 연산자(stack_top)보다 우선 순위가 높으면 스택에 추가한다.
- 토큰이 스택 연산자보다 우선 순위가 낮거나 같으면, 스택에서 연산자를 먼저 제거한다.
- 토큰이 '('이면 그대로 스택에 추가한다.
- 토큰이 ')'이면 스택에서 '('이 나올 때까지 모든 연산자를 제거하여 출력하고 '('은 출력 없이 버린다.
- 토큰이 문자열 끝이면 스택에 남은 연산자를 모두 출력한다.
- 코드
class Sym:
OPEN_B = 1
CLOSE_B = 2
PLUS = 3
MINUS = 4
TIMES = 5
DIVIDE = 6
MOD = 7
OPERAND = 8
class Expression:
def __init__(self,expr):
self.stack = []
self.size = 100
self.expr= expr
self.top=-1
self.output = ""
def isFull(self):
return len(self.stack)==self.size
def isEmpty(self):
return len(self.stack)==0
def push(self, item):
if not self.isFull():
self.top+=1
self.stack.append(item)
self.stack_show()
else:
print("Stack Full")
def pop(self):
if not self.isEmpty():
self.top -=1
return self.stack.pop()
else:
print("Stack Empty")
def show_stack(self):
print(self.stack)
def eval_postfix(self):
for sym in self.expr:
print(sym, end=' ')
sym_type = self.getSymtype(sym)
if sym_type == Sym.OPERAND:
self.push(int(sym))
else:
op2 = self.pop()
op1 = self.pop()
if sym_type == Sym.PLUS:
self.push(op1 + op2)
elif sym_type == Sym.MINUS:
self.push(op1 - op2)
elif sym_type== Sym.TIMES:
self.push(op1 * op2)
elif sym_type == Sym.DIVIDE:
self.push(op1 / op2)
elif sym_type== Sym.MOD:
self.push(op1 % op2)
return self.pop()
def getSymtype(self, sym):
if sym == '(':
sym_type = Sym.OPEN_B
elif sym == ')':
sym_type = Sym.CLOSE_B
elif sym == '+':
sym_type = Sym.PLUS
elif sym == '-':
sym_type = Sym.MINUS
elif sym == '*':
sym_type = Sym.TIMES
elif sym == '/':
sym_type = Sym.DIVIDE
elif sym == '%':
sym_type = Sym.MOD
else:
sym_type = Sym.OPERAND
return sym_type
def precedence(self, op):
if op == '(':
return 0
elif op in ['+', '-']:
return 1
elif op in ['*', '/', '%']:
return 2
def infix_postfix(self):
for token in self.expr:
print(token, end=' ')
if token.isalum():
self.output +=token
elif token == '(':
self.push(token)
elif token == ')':
sym = self.pop()
while sym!='(':
self.output+=sym
sym = self.pop()
else:
while not self.isEmpty() and self.precedence(self.stack[-1]) >= self.precedence(token):
sym = self.pop()
self.output+=sym
self.push(token)
while not self.isEmpty():
self.output += self.pop()
print()'전공과목 정리 > 자료구조' 카테고리의 다른 글
| [자료구조💾] 6장 이진 트리 (0) | 2024.01.18 |
|---|---|
| [자료구조💾] 5장 연결 리스트 (0) | 2024.01.17 |
| [자료구조💾] 3장 재귀호출 (2) | 2024.01.10 |
| [자료구조💾] 2장 파이썬 자료구조 (0) | 2024.01.09 |
| [자료구조💾] 1장 자료구조 개요 (2) | 2024.01.09 |