프로그래머스 강의_14

큐(Queue)

자료 (data element)를 보관할 수 있는 (선형)

• 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고
  ===> 인큐(enqueue) 연산
• 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음.
  ===> 디큐(dequeue) 연산
• 선입선출(FIFO:First-In First-Out)특징을 가지는 선형 자료구조

  큐의 동작

  데이터 원소 A를 큐에 추가, B를 추가

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

큐의 추상적 자료구조 구현

(1) 배열(array)을 이용하여 구현
=> Python 리스트와 메서드들을 이용
(2) 연결 리스트(linked list)를 이용하여 구현
=> 이전 강의에서 마련한 양방향 연결 리스트 이용

(3) 연산의 정의

• size() : 현재 큐에 들어있는 데이터 원소의 수를 구함
• isEmpty() : 현재 큐가 비어 있는지를 판단
• enqueue(x) : 데이터 원소 x를 큐에 추가
• dequeue() : 큐의 매 앞에 저장된 데이터 원소를 제거(또한, 반환)
• peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음) (4) 배열로 구현한 큐

  class ArrayQueue:
    
    # 큐의 크기를 리턴
    def __init__(self):
        self.data = []
    # 큐가 비어 있는지 판단
    def isEmpty(self):
        return self.size() == 0
    # 데이터 원소를 추가
    def enqueue(self,item):
        self.data.append(item)
    # 데이터 원소를 삭제(리턴)
    def dequeue(self):
        return self.data.pop(0)
    # 큐의 맨 앞 원소 반환
    def peek(self):
        return self.data[0]

 (5) 배열로 구현한 큐의 연산 복잡도 
  size() => O(1)
  isEmpty() => O(1)
  enqueue() => O(1)
  #### dequeue() => O(n)  큐가 길어지면 길어질수록 오래걸린다.
  #### 맨 앞 원소를 꺼냈을 때 뒤에 있는 원소를 앞으로 당겨줘야하기 떄문에 큐의 길이가 길수록 n개에 비례하는 시간이 걸린다.
  peek() => O(1) 

 (6) 이중 연결 리스트로 큐를 구현
 
#### 연습문제 - 코드 구현
 => 연산의 복잡도에 대해서도 생각해볼 것!
 
class LinkedListQueue:

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

    def size(self):
        # DoublyLinkedList는 size 메소드가 없기 때문에 getLength로 데이터의 길이를 확인할 수 있다.
        return self.data.getLength()

    def isEmpty(self):
        # 데이터의 길이가 0이라면 비어있다는 것을 알 수있다.
        return self.data.getLength()==0

    def enqueue(self, item):
        node = Node(item)
        # 노드 삽입 위치는 nodeCount(갯수) + 1 마지막에 삽입한다.
        self.data.insertAt(self.data.nodeCount+1, node)

    def dequeue(self):
        # 데이터의 맨 앞 1번째 위치에 있는 데이터를 popAt으로 꺼낸다.
        return self.data.popAt(1)
        
    def peek(self):
        # 1번째 위치에 있는 데이터를 값만 확인한다.
        return self.data.getAt(1).data