(2) Queue

Huisu·2023년 3월 28일
0

Data Structure

목록 보기
2/4
post-thumbnail

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의 가용 범위가 줄어들고 재사용이 불가능해짐

    https://i1.faceprep.in/fp/articles/img/33685_1675484469.gif

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

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

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

      https://cwh-full-next-space.fra1.digitaloceanspaces.com/videos/data-structures-and-algorithms-in-hindi-43/Image_1.webp

    • 하지만 이는 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
    FunctionTime Complexity
    MakeEmptyO(1)
    IsFullO(1)
    IsEmptyO(1)
    EnqueueO(1)
    DequeueO(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
import queue

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

0개의 댓글