👩‍💻LEARN : ML&Data/Code

[자료구조와 알고리즘] #6. 큐

쟈니유 2023. 4. 5. 15:30
728x90

#6. 큐 

 

큐란?

  • 선형 자료구조 
  • 선입선출의 성격 (enqueue - dequeue) / 스택과는 반대 (스택 : 후입선출)

 

큐의 동작 

  • 비어있는 큐가 있음  Q = Queue()
  • 데이터원소 A,B...를 큐에 추가  Q.enqueue(A), Q.enqueue(B)...
  • 선입선출로 원소 빼기  r1 = Q.dequeue() , r2 = Q.dequeue() ... 

 

큐의 추상적 자료구조 구현 

  • 배열(array) 이용
    • 파이썬 리스트와 메서드 이용 
  • 연결리스트(linkedlist) 이용
    • 이전 강의에서 작업한 양방향 연결 리스트 이용 
  • 연산의 정의 
    • size() : 현재 큐의 데이터 원소 수를 구함
    • isEmpty() : 큐가 비어있는 지 판단 
    • enqueue(x) : 데이터원소를 추가
    • dequeue() : 맨 앞에 저장된 데이터 원소를 제거 및 반환 
    • peek() : 맨 앞에 저장된 데이터 원소를 반환 (제거하진 않음) 

 

배열로 만든 큐 

class ArrayQueue:

	def __init__(self):
    	self.data = []
        
    def size(self):
    	return len(self.data)
        
    def isEmpty(self):
    	return self.size == ()
        
    def eunqueue(self,item):
    	self.data.append(item) 
        
    def dequeue(self):
    	return self.data.pop(0)      #0번 인덱스의 원소를 꺼내라, O(n)의 복잡도. 없애면 한칸씩댕겨와야함  
        
    def peek(self):
    	return self.data[0]

 

양방향 연결로 만든 큐 

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:
            raise IndexError('Index out of range')

        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.size() ==0


    def enqueue(self, item):
        node = Node(item)
        
		self.data.insertAt(self.data.nodeCount +1 ,node)


    def dequeue(self):
        return 
		self.data.popAt(1)


    def peek(self):
        return 
		self.data.getAt(1).data



def solution(x):
    return 0

 

기존 라이브러리 이용 

from pythonds.basic.queue import Queue

Q = Queue()
dir(Q)    #	정의된 연산 확인 가능

 

환형큐

큐의 활용처 

  • 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우 
  • 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 
  • 자료를 이용하는 작업이 여러 곳에서 일어나는 경우 
  • 자료 생성, 이용 작업이 양쪽 다 여러 곳에서 일어나는 경우 
  • 자료를 처리하여 새로운 자료를 생성하고 나중에 그 자료를 또 처리해야 하는 작업의 경우 

 

환형 큐

  • 정해진 개수의 저장공간을 돌려가면서 이용 (원형으로 이어진 저장공간)
  • 데이터를 집어 넣는 포인트 : rear, 꺼내는 포인터 : front 
  • 빈 공간이 없을 경우 더 이상 원소를 추가할 수 없음 (큐 길이를 기억하고 있어야)

 

환형 큐의 추상적 자료 구조 구현 

연산의 정의 

  • isFull() 하나 더 추가 

 

배열로 구현한 환형 큐 

  • 정해진 길이 n의 리스트를 확보 (해당 개수만큼의 원소만 가능)
  • 원소 넣기 @ [0] 부터 by Q.enqueue(A) → rear로 포인터 
  • 원소 빼기 @ [0] 부터 by r1 = Q.dequeue → front로 포인터
  • 원소 빠진 이후 빈 자리에 덮어쓰기 가능 
class CircularQueue:

    def __init__(self, n):
        self.maxCount = 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')
        self.rear = (self.rear+1)% self.maxCount
        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
        if self.size() == 0:
            raise IndexError('Queue empty')
        self.front = (self.front+1) % self.maxCount
        x = self.data[self.front]
        self.count -= 1
        return x

    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        return self.data[(self.front+1) % self.maxCount]


def solution(x):
    return 0

 

※ 환형으로 구현하기 위해 유의해야할 것 

  • 끝까지 차면 앞으로 돌아와야함 → 총 길이로 나눈 것의 나머지!로 새로운 값을 세팅해줘야 함 
    • n = 6개일 경우 6개를 enqueue하고 2개를 dequeue 했다고 가정하면 
      • rear : 0,1,2,3,4,5(6으로 나눠도 자기자신) →front : 0,1 →rear : 0,1 (6%6이되면 0으로 초기 세팅됨) 

 

 

우선순위 큐 

선입선출을 따르지 않고 원소들의 우선순위에 따라 큐에서 dequeue 시 빠져나오는 방식 

e.g. CPU 스케쥴러 

 

우선순위 큐의 구현 

1) Enqueue 시 우선순위 순서를 유지하도록 (유리)

2) Dequeue 할 때 우선순위 높은 것을 선택 

 

1) 선형배열 이용 : 메모리 차지 측면에 유리 

2) 연결리스트 이용 : 시간 측면에서 유리 (링크에만 넣으면 됨)

 

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 x < curr.next.data:
            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

※ 유의해야할 것

  • curr 은 우선 초기화 
  • 다음 칸이 tail이 아니고, 우선순위 고려했을 때 curr.next.data보다 x가 숫자가 작을때(=우선순위가 높을때)
    • 다음 칸으로 가라 
  • 이 둘에 해당하지 않으면 뉴노드 삽입 

 

'👩‍💻LEARN : ML&Data > Code' 카테고리의 다른 글

[자료구조와 알고리즘] #8. 힙(Heap)  (0) 2023.04.07
[자료구조와 알고리즘] #7. 트리  (0) 2023.04.06
[자료구조와 알고리즘] #5. 스택  (0) 2023.04.04
[자료구조와 알고리즘] #3. 연결리스트:양방향  (0) 2023.04.03
[자료구조와 알고리즘] #3. 연결리스트:단방향  (0) 2023.04.02

'👩‍💻LEARN : ML&Data/Code'의 다른글

  • 현재글[자료구조와 알고리즘] #6. 큐

관련글

댓글

티스토리툴바