Queue

Queue

What is the Queue?

• Homogeneous한 Item이 순서를 갖고 쌓이는 것
• 한쪽에서는 삽입만 이루어지고, 한쪽에서는 삭제만 이루어지는 것
  • 따라서 끝만 나타냈던 stack과 다르게 앞 뒤를 모두 저장하는 front, rear가 필요함
• FIFO: First In, First Out
• ex) 컴퓨터 운영체제의 테스크 스케줄링

Queue ADT Operation

• Transformer
  • MakeEmpty
  • Enqueue
  • Dequeue
• Observe
  • IsEmpty
  • IsFull

Problem

• Dequeue() 함수를 쓰게 되면 맨 앞에 있던 값이 하나씩 빠져 나가면서 queue의 가용 범위가 줄어들고 재사용이 불가능해짐

  

  • 위처럼 작업하다 보면 0, 1, 2, 3 index의 큐들은 사용하지 못한 채 데이터를 낭비하게 됨

• Solution 1

  • Dequeue를 할 때 front를 증가하지 않고 모든 Queue의 Item을 앞당기는 방법 !
  • Queue의 모든 item을 복사하고 붙여넣기 해야 해서 효율성이 떨어짐

• Solution 2

  • Queue의 가용 범위 끝까지 가면 front를 앞으로 되돌리는 Circular Queue

    
    

  • 하지만 이는 Empty Queue와 Full Queue를 구분하지 못한다는 단점이 있음

    

  • 사용하지 않는 칸인 Reserved Cell을 하나 생성해 문제 해결
    - Reservec Cell: 못 쓰는 공간으로 낭비되는 메모리이며 실제 front의 하나 앞을 포인팅하는 용도

    

  • 기존의 Circular Queue

    • front = 0, rear = -1

  • Reserved Cell Circular Queue

    • front = -1, rear = -1

int length

• int length인 멤버 변수를 추가해 Queue에 몇 개가 저장돼 있는지 카운팅하는 방법
• Enqueue 시에 length++
• Dequeue 시에 length--
• length를 추가하는 일은 비용이 많이 들어 비효율적인 구현 방법
• Enqueue, Dequeue가 빈번하게 사용되는데, 사용할 때마다 length 연산 필요하기 때문
• 길이를 알고자 하는 LengthIs() 함수를 자주 사용한다면 유리한 전략

Array Queue

Array

• Stack의 크기를 처음부터 정해 두고 시작해야 함
• 안 쓰는 메모리가 있을 경우에 낭비적인 방식
• Item에 pointer가 없기 때문에 Item 하나가 차지하는 메모리는 작음
• top 이라는 변수를 사용하여 stack의 가장 끝을 나타내는 위치 저장소 역할을 하도록 함

Reserved Cell Circular Queue with C++

• QueueType.h

  • Queue이 가지는 함수들을 선언해 놓은 헤더 파일

    #include "ItemType.h"
    
    typedef int ItemType;
    
    class FullQueue {
    };
    
    class EmptyQueue {
    };
    
    class QueType {
    public:
    	QueType();
    	QueType(int max);
    	void MakeEmpty();
    	bool IsEmpty() const;
    	bool IsFull() const;
    	void Enqueue(ItemType item);
    	void Dequeue(ItemType& item);
    private:
    	int front;
    	int rear;
    	int maxQue;
    	ItemType* items;
    };

• QueueType.cpp

  • Queue가 가지는 함수들의 기능을 실제로 구현해 놓은 파일

    #include "QueueTypeInt.h"
    
    // 최대 크기 지정하지 않았을 때 생성자
    QueType::QueType() {
    	maxQue = 500;
    	front = maxQue - 1;
    	rear = maxQue - 1;
    	items = new ItemType[maxQue];
    }
    //최대 크기 지정해 줬을 때 생성자
    QueType::QueType(int max) {
    	maxQue = max;
    	front = maxQue - 1;
    	rear = maxQue - 1;
    	items = new ItemType[maxQue];
    }
    // 포인터들을 초기화시키고 아이템 삭제
    void QueType::MakeEmpty() {
    	front = maxQue - 1;
    	rear = maxQue - 1;
    	delete[] items;
    }
    
    bool QueType::IsEmpty() const {
    	return (front == rear);
    }
    
    bool QueType::IsFull() const {
    	return (rear + 1) % maxQue == front;
    }
    // 끝의 index를 올리고 아이템 추가
    void QueType::Enqueue(ItemType item) {
    	if (IsFull()) {
    		throw FullQueue();
    	}
    	else {
    		rear = (rear + 1) & maxQue;
    		items[rear] = item;
    	}
    }
    // 시작의 index를 올리고 처음 들어왔던 아이템 삭제
    void QueType::Dequeue(ItemType& item) {
    	if (IsEmpty()) {
    		throw EmptyQueue();
    	}
    	else {
    		front = (front + 1) % maxQue;
    		item = items[front];
    	}
    }

• Time Complexity

  Function	Time Complexity
  MakeEmpty	O(1)
  IsFull	O(1)
  IsEmpty	O(1)
  Enqueue	O(1)
  Dequeue	O(1)

Queue with Python

MAX_ITEMS = 100

class QueueType():
    def __init__(self):
        self.info = []
        self.rear = MAX_ITEMS - 1
        self.front = MAX_ITEMS -1

    def enqueue(self, data):
		self.rear = (self.rear+1) % MAX_ITEMS
        if(len(self.info) == MAX_ITEMS):
            self.info[self.rear] = data
        elif(len(self.info) != MAX_ITEMS):
            self.info.append(data)
        return self.info[0]

    def dequeue(self):
        self.front = (self.front + 1) % MAX_ITEMS
        return self.info[self.front]
            
    def is_empty(self):
        return (self.rear == self.front)

    def is_full(self):
        return ((self.rear + 1)%MAX_ITEMS == self.front)

    def make_empty(self):
        self.rear = MAX_ITEMS - 1
        self.front = MAX_ITEMS -1
        return len(self.stack)==0

• Python에서 Queue Library 제공
• 공식 문서 queue — 동기화된 큐 클래스 — Python 3.7.16 문서
  

import queue

q = Queue() #queue 생성
q.qsize() #queue 사이즈
q.empty() #IsEmpty
q.full() #IsFull
q.put(item) #Enqueue
q.get() # Dequeue