큐, 환형큐 실습

 

 

 

In [ ]:

#14강 큐
'''자료를 보관할 수 있는 (선형)구조
넣을 때는 한쪽 끝에서 넣고(인큐), 꺼낼땐 반대로 꺼냄(디큐)

선입선출 구조

Q=Queue()
Q.enqueue(A)
Q.enqueue(B)
큐 A B
r1=Q.dequeue() 큐 B
r2=Q.dequeue() 큐 

(1) 배열을 이용해 구현 : 파이썬 리스트와 메서드들을 이용
(2) 연결 리스트를 이용해서 구현 : 양방향 연결리스트

연산의 정의
size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함
isEmpty() - 현재 큐가 비어 있는지를 판단
enqueue(x) - 데이터 원소 x를 큐에 추가
dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거(반환)
peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환(제거 않음)

배열로 구현한 큐

class ArrayQueue:
    #큐의 크기를 리턴
    def size(self):
        return len(self.data)
        
    #큐가 비어 있는지 판단
    def isEmpty(self):
        return self.size()==0

class ArrayStack:
    # 데이터 원소를 추가
    def enqueue(self,item):
        self.data.append(item)
    
    #데이터 원소를 삭제(리턴)
    def deque(self):
        #가장 먼저 들어간것 리턴(+나머지 전부 재배치)
        return self.data.pop(0)
class ArrayStack:
    #큐의 맨 앞 원소 반환
    def peek(self):
        return self.data[0]
        
배열로 구현한 큐의 연산 복잡도
size()    O(1)
isEmpty() O(1)
enqueue() O(1)
dequeue() O(n) + 재배치 시간
peek()    O(1)

만약 양방향 연결리스트를 이용한다면 이런 재배치 시간 절약

라이브러리로도 있음 : 
from pythons.basic.queue import Queue
Q=Queue()
dir(Q) '''
#14강 양방향 연결 리스트로 구현하는 큐

class Node:
    def __init__(self, item):
        self.data = item  # 노드의 데이터 값
        self.prev = None  # 이전 노드를 가리키는 포인터
        self.next = None  # 다음 노드를 가리키는 포인터

class DoublyLinkedList:
    def __init__(self):
        self.nodeCount = 0  # 연결 리스트에 포함된 노드 수
        # 헤드와 테일 노드 초기화
        self.head = Node(None)  # 빈 데이터 값을 가진 헤드 노드
        self.tail = Node(None)  # 빈 데이터 값을 가진 테일 노드
        # 더미 노드 설정:
        self.head.prev = None  # 헤드 이전은 없음
        self.head.next = self.tail  # 헤드 다음은 테일
        self.tail.prev = self.head  # 테일 이전은 헤드
        self.tail.next = None  # 테일 다음은 없음

    def __repr__(self):
        # 노드가 0개일 때, 연결된 리스트가 없음을 출력
        if self.nodeCount == 0:
            return 'LinkedList: empty'
        s = ''
        curr = self.head
        #테일 노드에 도착할때까지 루프를 계속
        while curr.next.next:
            #현재 노드 한칸씩 이동
            curr = curr.next
            #현재 노드의 데이터 값을 문자열로 변환하여 s에 추가
            s += repr(curr.data)
            #테일 노드가 아니라면 노드 사이에 ' -> ' 문자열을 추가
            if curr.next.next is not None:
                s += ' -> '
        #노드 사이에 ' -> ' 문자열이 있는 표현 반환
        return s
    
    #노드 길이 반환
    def getLength(self):
        return self.nodeCount
    
    #노드 데이터 리스트 정방향으로 반환
    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result
    
    #노드 데이터 리스트 역방향으로 반환
    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result

    #특정 포지션 노드 얻기
    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None
        
        #포지션이 절반 이상부분에 있을때
        if pos > self.nodeCount // 2:
            i = 0
            #꼬리부터 시작해
            curr = self.tail
            #포지션이 나올때까지 탐색
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        #그 외 경우는 처음부터 시작해 탐색
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1
        #현재노드 반환
        return curr
    
    #뒤에 삽입
    def insertAfter(self, prev, newNode):
        #다음 노드를(next) 뭘로할지를 먼저 지정
        next = prev.next
        
        #새 노드(newNode) 앞 뒤로 연결
        newNode.prev = prev
        newNode.next = next
        
        #기존 노드들도 newNode로 포인터 연결 
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True
    
    #해당 장소에 삽입
    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        #pos로 전노드 찾음
        prev = self.getAt(pos - 1)

        #insertAfter메서드 활용해서 삽입
        return self.insertAfter(prev, newNode)
    
    #다음꺼 빼기
    def popAfter(self, prev):
        #삭제전 양쪽 값 찾음
        curr = prev.next
        next = curr.next
        #빼는값 제외하고 양쪽값 연결
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data
    
    #특정 포지션 빼기
    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError('Index out of range')
        #이전값 구하고 popAfter활용
        prev = self.getAt(pos - 1)
        return self.popAfter(prev)
    
    #두개 연결리스트 합치기
    def concat(self, L):
        # 양쪽 더미노드 제끼고 연결
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        # 테일 노드 업데이트
        self.tail = L.tail
        # 노드 수 업데이트
        self.nodeCount += L.nodeCount

class LinkedListQueue:
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.getLength()

    def isEmpty(self):
        return self.data.getLength() == 0
    
    #큐의 끝에 항목 추가
    def enqueue(self, item):
        node = Node(item)
        #insertAt 메소드 활용, 마지막 다음(self.size() + 1) 위치에
        #node 삽입
        self.data.insertAt(self.size() + 1, node)
    
    # 큐의 처음 항목 제거 및 반환
    def dequeue(self):
        return self.data.popAt(1)
    
    # 큐의 처음(빠질) 항목 참조
    def peek(self):
        return self.data.getAt(1).data

def solution(x):
    return 0

 

In [ ]:

#15강 환형 큐(circular queue)
'''자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로
일어나는 경우

자료 생성 작업이 여러 곳에서 일어나는 경우

생성과 이용이 여러 곳에서 일어나는 경우

큐의 활용 : 자료를 처리해서 새로운 자료를 생성하고, 나중에 그 자료를
또 처리해야 하는 작업

환형 큐 : 정해진 개수의 저장 공간을 빙 돌려가며 이용

Q.enqueue(A), Q.enqueue(B) , Q.enqueue(C)
r1=Q.dequeue()
Q.enqueue(D)
r2=Q.dequeue()

a(rear) b c d(front) e   (a와 e은 연결된 환형)  
rear : 데이터 집어넣으면서 다음 빈쪽으로 계속 이동
front : 데이터 꺼내는쪽 다음 꺼내는쪽으로 계속 이동

주의 : 큐 길이를 기억하고 있어야 원소를 그만큼만 넣을수 있음

size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함
isEmpty() -현재 큐가 비어 있는지를 판단
enqueue(x)-데이터 원소x를 큐에 추가
dequeue() -큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환)
peek()- 큐의 맨 앞에 저장된 데이터 원소를 반환(제거안함)

새롭게 추가된것
isFull()- 큐에 데이터 원소가 꽉 차 있는지를 판단
'''
#배열로 구현한 환형 큐
class CircularQueue:
    
    # 빈 큐를 초기화
    def __init__(self, n):
        self.maxCount = n
        #길이 n인 큐 생성
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1
    
    #현재 큐길이 반환
    def size(self):
        return self.count
    
    #큐가 비어있는지
    def isEmpty(self):
        return self.count == 0
    
    #큐가 꽉차있는지
    def isFull(self):
        return self.count == self.maxCount
    
    #큐에 데이터 원소 추가
    def enqueue(self, x):
        if self.isFull():
            raise IndexError('Queue full')
        # 원형 큐에서 rear 포인터를 다음 위치로 이동
        self.rear = (self.rear + 1) % self.maxCount
        # rear 포인터가 가리키는 위치에 새로운 요소(x)를 삽입
        self.data[self.rear] = x
        # 큐의 요소 개수(count) 증가
        self.count += 1
        

    def dequeue(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        # 큐에서 front 포인터를 다음 위치로 이동    
        self.front = (self.front + 1) % self.maxCount
        
        # front 포인터가 가리키는 위치의 요소(x)를 가져옴
        x = self.data[self.front]
        
        # 큐의 요소 개수(count) 감소
        self.count -= 1
        # 가져온 요소 반환
        return x

    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        # front 포인터 다음 위치에 있는 요소를 반환 
        #(큐에서 가장 앞의 요소, 다음에 dequeue될 요소)    
        return self.data[(self.front + 1) % self.maxCount]
        
def solution(x):
    return 0

 

In [ ]:

#16강 우선순위 큐
'''원소들의 우선순위가 각각있어, 그 순서대로 빠져나옴
사용예) 운영체제의 CPU 스케줄러

how(두가지 방법)
(1)Enqueue 할 때 우선순위 순서 유지 -> 약간 더 유리
(2)Dequeue 할 때 우선순위 높은 것을 선택 
why? Dequeue 할때 모든 데이터 원소를 다 봐야함
->큐의 길이에 비례하는 시간

우선순위 큐의 구현
(1) 선형 배열 이용 :공간덜차치
(2) 연결 리스트 이용:시간 우세로 약간 더 유리
-> 어느 것이 더 유리할까?
'''

 

In [ ]:

#16강 실습: 우선순위 큐의 enqueue 연산 구현
class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1
        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail
        self.nodeCount += L.nodeCount


class PriorityQueue:
    # 양방향 연결 리스트로 초기화
    def __init__(self):
        self.queue = DoublyLinkedList()

    def size(self):
        return self.queue.getLength()

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head
        while curr.next !=self.queue.tail and curr.next.data>x:
            curr = curr.next
        self.queue.insertAfter(curr, newNode)

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data

def solution(x):
    return 0

#차이점 getAt() 메서드를 이용하지 않음 : 처음부터 찾아서 비효율적