[파이썬] DAY10 스택&큐
l = []
l.append("data1") # 우측에서 넣는다.
l.pop(0) # 인덱스를 넣어 가장 왼쪽에서 빼낸다.
l1 = [1,2,3,4]
l2 = [2,3,4,5]
print(id(l1)) # 리스트 객체의 주소를 보여준다.
print(id(l2))
#l1 = l1 + l2
#print(id(l1)) # 새로운 주소를 만들어버린다.
l1 = l1.extend(l2)
print(id(l1)) # 새로운 주소를 만들어버린다. 순차리스트이기 때문에 주소가 바뀌지만 동적 할당이기 때문에 연결리스트처럼 동작할 수 있다.1. 스택
1:1 관계인 선형 관계로 쌓는다.
선입후출 = 후입선출 LIFO
스택을 쓰는 이유
시스템은 스택형식으로 동작한다.
스텍 프레임
삽입연산: push
삭제연산: pop(입출구는 하나다, 선입후출)
순차 자료구조로 구현한 스택의 한계
장점: 1차원 배열을 사용하여 쉽게 구현할 수 있다.
단점: 크기가 고정되어 스택의 크기를 변경하기 어렵다.
연결 자료구조를 이용한 스택의 구현
연결리스트로 스택을 만들었다.
링크 포인터를 이용하여 연결한다.
push 연산
입출구는 top
def push(item): # push 연산
global size
global top
top = Node(item, top)
size +=1
pop 연산
데이터는 꺼내고 빈 노드는 지운다. 남은 노드 끼리 연결시킨다.
def pop(): # pop 연산
global size
global top
if size !=0 :
top_item = top.item
top =top.next
size-=1
return top_item
리스트로 스택 만들기
(파이썬의 리스트는 동적 할당으로 사이즈가 자유자재로 움직일 수 있다. 클래스는 정적으로 사이즈 자유자재로 움직이기 어려움)
def push(item): # 삽입연산
stack.append(item)
def peek(): # top 항목 접근
if len(stack) !=0:
return stack[-1]
def pop(): # 삭제 연산
if len(stack) != 0:
item = stack.pop(-1)
return item
stack = []
push('apple')
push('orange')
push('cherry')
print('사과, 오랜지, 체리 push 후:\t', end="")
print(stack, '\t < - top')
print('top 항목: ', end="")
print(peek())
push('pear')
print('배 push 후:\t', end="")
print(stack, '\t < - top')
pop()
push('grape')
print('pop(), 포도 push 후:\t', end="")
print(stack, '\t<- top')연결 리스트는 성능을 높이기 위해 존재한다.
2. 큐
선입선출(FIFO)
입구와 출구는 다르다.
단방향
삭제는 머리에서
삽입은 꼬리에서 동작한다.
-> 단순 연결리스트로 만든다.
정석
def add(item): # 삽입연산
q.append(item)
def remove(): # 삭제연산
if len(q) != 0:
item = q.pop(0)
return item
def print_q(): # 큐 출력
print('front -->', end ="")
for i in range(len(q)):
print(f'{q[i]} ', end="")
print(' <--rear')
q = []
add('apple')
add('orange')
add('cherry')
add('pear')
print('사과, 오렌지, 체리, 배 삽입 후: \t', end='')
print_q()
remove()
print('remove한 후: \t', end="")
print_q()
remove()
print('remove한 후: \t', end="")
print_q()
add('grape')
print('포도 삽입 한 후: \t', end="")
print_q()삽입이나 삭제가 다른 입구에서 동작하기 때문에 다르게 명명한다.
삽입 enQue
삭제
잘 안 다루므로 생략한다.
3가지를 고려한 연결 큐 동작 코드
class Node:
def __init__(self,item,link):
self.item = item
self.next = link
def add(item): # 삽입연산
global rear
global front
global size
new_node = Node(item, None)
if size == 0:
front = new_node
else:
rear.next = new_node
rear = new_node
size+=1
def remove(): # 삭제연산
global rear
global front
global size
if size !=0:
fitem = front.item
front = front.next
size -= 1
if size == 0:
rear == None
return fitem
def print_q(): # 큐 출력
p = front
print('front:\t', end="")
while p:
if p.next !=None:
print(p.item, '-> ', end = "")
else:
print(p.item, end ="")
p = p.next
print(' :rear')
# 초기화 3개
size = 0
rear = None
front =None
add('apple')
add('orange')
add('cherry')
add('pear')
print('사과, 오렌지, 체리, 배 삽입 후: \t', end='')
print_q()
remove()
print('remove한 후: \t', end="")
print_q()
remove()
print('remove한 후: \t', end="")
print_q()
add('grape')
print('포도 삽입 한 후: \t', end="")
print_q()삭제 연산: 데이터를 꺼낸다.
c는 클래스만 써야 하지만
파이썬은 연결 리스트 등 도구를 다양하게 써도 된다.
파이썬은 동적 할당이다. 이론만 알면 굳이 정석적으로 말고 간단하게 알고리즘을 구현하자
l = []
l.append("data1") # 우측에서 넣는다.
l.pop(0) # 인덱스를 넣어 가장 왼쪽에서 빼낸다.
l1 = [1,2,3,4]
l2 = [2,3,4,5]
print(id(l1)) # 리스트 객체의 주소를 보여준다.
print(id(l2))
#l1 = l1 + l2
#print(id(l1)) # 새로운 주소를 만들어버린다.
l1 = l1.extend(l2)
print(id(l1)) # 새로운 주소를 만들어버린다. 순차리스트이기 때문에 주소가 바뀌지만 동적 할당이기 때문에 연결리스트처럼 동작할 수 있다.연결리스트처럼 쓰이는 것뿐 연결리스트는 아니다.
cf) 인공지능 쪽을 많이하려면 numpy를 많이 쓴다. 매트릭스를 많이 쓴다.
numpy는 c 구조 배열과 같이 생겼고 1:1로 매핑해주는 역할을 한다.
운영체제 작업은 큐로 구성되어있다.
큐구조로 되어있다. 즉 순서대로 진행된다.
먼저 실행 시킨 작업이 먼저 끝난다.
버퍼 큐: 장치간의 처리속도는 다르므로
스케쥴링 큐
1:1관계: 하나가 나가면 하나가 대기, 또 하나가 나가면 하나가 대기 하는 구조
3. 덱
큐 2개를 서로 다른 방향으로 붙인다.
양방향으로 삭제 삽입이 가능하다.
이중 연결 리스트를 이용해서 연결한다.
우선순위 큐
코드 ----------------
collections 에 알고리즘 관련 모든 모듈이 다 담겨있다. 외부 모듈이다.
append(입력한 원소) : 입력한 원소를 하나로 뭉쳐서 넣는다.
expend(반드시 구조로 입력할 것) : 구조의 원소들을 하나씩 쪼개서 넣는다.
둘 다 오른쪽에서 넣는다 덱 입장에서는 꼬리에서 넣는다.
왼쪽에서 넣고 싶다면
appendleft()
왼쪽에서 빼고 싶다면
popleft()
extendleft(reverse(" 데이터 "))
나갈 때 왼쪽에서부터 나간다.