기능 vs 구현
예) 삽입연산
기능 - 연산이’무엇’을 하는지
순서데이터에서 원하는 위치에 데이터를 저장
구현 - 연산의 기능을 ‘어떻게’하는지
추상화 - 구현을 몰라도 기능만 알면 프로그래밍을 할 수 있게 해주는 개념
추상화를 하면 이미 쓴 코드를 재활용하고 개발자들끼리 협력하기 쉬워짐
자료구조를 사용할때도 추상화를 많이 사용
추상자료형(Abstract Data Type)
자료구조를 추상화 한것
데이터를 저장/사용할때 구현 부분을 생각하지 않고 순수한 기능이 무엇인지 나열한 것
추상자료형을 생각하면 코드의 흐름에 집중할 수 있다
파이썬 - 추상화가 많이 된 고수준 언어, 많은 자료형 이름이 추상 자료형
FIFO : First-in-first-out
-> 먼저 들어온 데이터가 먼저 삭제된다.
데이터간 순서 관계를 유지할 수 있다
-맨뒤 데이터 추가
-맨앞 데이터 삭제
-맨앞 데이터 접근
큐는 동적배열과 링크드 리스트로 구현할수 있다.
<시간복잡도>
동적 배열 | 더블리 링크드 리스트 | |
---|---|---|
맨앞삭제 | O(n) | O(1) |
맨뒤삽입 | 분할상환-> O(1) | O(1) |
맨앞접근 | O(1) | O(1) |
-> 파이썬에서는 deque 를 이용하여 큐를 쓸 수 있음
Deque : Doubly-ended-queue(양면큐)
맨 앞과 뒤에서 데이터 삽입, 삭제를 모두 할 수 있게 해주는 자료형
파이썬 deque는 내부적으로 더블리 링크드 리스트로 구현되어 있다.
# deque 는 파이썬 collections 모듈에서 가지고 온다.
from collections import deque
queue = deque()
# 큐의 맨 끝에 데이터 삽입
queue.append('Sam')
queue.append('Jane')
queue.append('Tom')
queue.append('Erin')
queue.append('Sera')
print(queue) # 큐 출력.
# 큐의 가장 앞 데이터에 접근
print(queue[0])
# 큐 맨앞 데이터 삭제
print(queue.popleft()) # popleft() 제일 앞 데이터 삭제하는 메소드
print(queue.popleft())
print(queue.popleft())
print(queue)
# 고객센터 문의 처리.
from collections import deque
class CustomerComplaint:
"""고객 센터 문의를 나타내는 클래스"""
def __init__(self, name, email, content):
self.name = name
self.email = email
self.content = content
class CustomerServiceCenter:
"""고객 서비스 센터 클래스"""
def __init__(self):
self.queue = deque() # 대기 중인 문의를 저장할 큐 생성
def process_complaint(self):
"""접수된 고객 센터 문의 내용 처리하는 메소드"""
if self.queue:
complaint = self.queue.popleft()
print(f"{complaint.name}님의 {complaint.content} 문의 내용 접수되었습니다. "
f"담당자가 배정되면 {complaint.email}로 연락드리겠습니다!")
else:
print("더 이상 대기 중인 문의가 없습니다!")
def add_complaint(self, name, email, content):
"""새로운 문의를 큐에 추가 시켜주는 메소드"""
new_complaint = CustomerComplaint(name, email, content)
self.queue.append(new_complaint)
LIFO : Last-in-first-out
-> 가장 마지막에 들어온 데이터가 가장 먼저 삭제된다
데이터간 순서관계를 유지할 수 있다
맨 뒤 데이터 추가, 맨 뒤 데이터 삭제, 맨 뒤 데이터 접근.
파이썬에는 스택의 이름을 갖는 자료형은없다. 큐를 이용할 때와 같이 데크를 이용한다.
동적배열과 링크드 리스트를 이용해서 구현할 수 잇다.
출력결과나 시간 복잡도는 같다. -> O(1)
# Stack 은 파이썬 collections 모듈에서 가지고 온다
from collections import deque
stack = deque()
# 스택 맨 끝에 데이터 추가
stack.append('E')
stack.append('s')
stack.append('w')
stack.append('q')
stack.append('t')
print(stack)
# 맨 끝 데이터 접근
print(stack[-1])
# 맨 끝 데이터 삭제
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack)
# 스택을 이용해 괄호 짝이 맞는지 확인하기
from collections import deque
def parentheses_checker(string):
"""주어진 문자열 인풋의 모든 괄호가 짝이 있는지 확인해주는 메소드"""
print(f"테스트하는 문자열: {string}")
stack = deque() # 사용할 스택 정의
for i in range(len(string)):
if string[i] == '(':
stack.append(i)
if string[i] == ')':
if stack:
stack.pop()
else:
print(f'문자열 {i} 번째 위치에 있는 닫는 괄호에 맞는 열리는 괄호가 없습니다.')
while stack:
print(f"문자열 {stack.pop()} 번째 위치에 있는 괄호가 닫히지 않았습니다")
# 이렇게 입력하게 되면 정답이 나온다
case1 = "(1+2)*(3+5)"
case2 = "((3*12)/(41-31))"
case3 = "((1+4)-(3*12)/3"
case4 = "(12-3)*(56/3))"
case5 = ")1+14)/3"
case6 = "(3+15(*3"
parentheses_checker(case1)
parentheses_checker(case2)
parentheses_checker(case3)
parentheses_checker(case4)
parentheses_checker(case5)
parentheses_checker(case6)