이전 기사에서 데이터 구조의 중요성에 대해 이미 연구했듯이 기사의 주제 즉, 큐 데이터 구조에 대해 바로 살펴 보겠습니다. 다음 주제에 대해 논의 할 것입니다.
큐 데이터 구조의 필요성
언젠가 영화를보고 싶다고 가정 해 봅시다. 멀티 플렉스에서 티켓은 선착순으로 발행되었고 사람들은 차례를 기다리며 서로 뒤에 서있었습니다. 그래서 뭐 할거야?? 뒤로 가서 티켓을 기다리는 마지막 사람 뒤에 서 있어야합니다.
여기에서 사람들은 서로 뒤에 서 있고 그들은 선입 선출 (FIFO) 기구. 이러한 배열은 열.
대기열의 일상 예
일상 생활에서 대기열 유형을 선택하는 몇 가지 예를 살펴 보겠습니다.
- 전화 응답 시스템 가젯으로 먼저 전화를 건 사람이 먼저 참석합니다.
- 수하물 검사기 – 컨베이어 벨트에 먼저 보관 된 수하물을 확인합니다.
- 통행세 다리의 차량 – 일찍 도착하는 차량이 먼저 출발합니다.
- 콜센터 – 전화 시스템은 대기열을 사용하여 서비스 담당자가 무료가 될 때까지 사람들이 순서대로 전화를 걸도록합니다.
이 모든 예는 다음과 같습니다. 선입 선출 전략.
대기열 데이터 구조 생성
보완 작업과 별도로 대기열에서 가능한 주요 작업은 다음과 같습니다.
하나. 대기열에 넣기 또는 큐 끝에 요소를 추가하십시오.
2. 대기열에서 제거 또는 대기열 전면에서 요소 제거
이제 Python에서 클래스 Queue를 생성하여 시작하겠습니다.
클래스 대기열 : def __init __ (self, max_size) : self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0
- max_size 큐에서 예상되는 최대 요소 수입니다.
- 큐의 요소는 파이썬 목록에 저장됩니다.
- rear는 대기열에서 마지막 요소의 색인 위치를 나타냅니다.
- 대기열이 비어 있기 때문에 뒤쪽은 처음에 -1이됩니다.
- 전면은 대기열에서 첫 번째 요소의 위치를 나타냅니다.
- 항상 대기열의 첫 번째 요소를 가리 키기 때문에 처음에는 앞면이 0으로 간주됩니다.
대기열에 넣기
이제 요소를 대기열에 추가하려고 할 때 다음 사항을 기억해야합니다.
- 대기열에 남은 공간이 있는지 여부 (예 : rear가 max_size -1 인 경우)
- 뒤쪽은 대기열에 삽입 된 마지막 요소를 가리 킵니다.
그래서 알고리즘은 무엇입니까 ??
#returns max_size of queue def get_max_size (self) : return self .__ max_size #return self .__ max_size # queue가 꽉 찼는 지 여부에 관계없이 bool 값을 반환하고, 가득 차면 True, 그렇지 않으면 False def is_full (self) : return self .__ rear == self .__ max_size-1 # 전체가 아닌 경우 큐에 데이터를 삽입 / 대기열에 넣습니다. def enqueue (self, data) : if (self.is_full ()) : print ( '대기열이 가득 찼습니다. 큐에 넣을 수 없습니다.') else : self .__ rear + = 1 self. __elements [self .__ rear] = data # 큐의 모든 내용을 표시합니다. def display (self) : for i in range (0, self .__ rear + 1) : print (self .__ elements [i]) # def __str __ (self)를 디버깅하는 동안 DS 객체의 요소를 인쇄하려면 __str __ () 아래 : msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg
이제 다음을 실행할 때 :
queue1 = 대기열 (5)
# 모든 필수 요소를 대기열에 넣습니다.
queue1.enqueue ( 'A')
queue1.enqueue ( 'B')
queue1.enqueue ( 'C')
queue1.enqueue ( 'D')
queue1.enqueue ( 'E')
queue1.display ()
queue1.enqueue ( 'F')
print (대기열 1)
산출:
에
비
씨
디
IS
대기열이 가득 찼습니다. 대기열에 넣을 수 없음
대기열 데이터 (전면에서 후면) : A B C D E
대기열 해제
이제 요소를 큐에 삽입 / 대기열에 넣었으므로 전면에서 큐에서 제거 / 삭제하려고하므로 다음 사항에주의해야합니다.
- 대기열에 요소가 있습니다. 즉 후면이 -1과 같으면 안됩니다.
- 둘째, 요소가 앞면에서 삭제되므로 앞면을 삭제 한 후 다음 앞쪽을 가리 키도록 증가해야한다는 점을 기억해야합니다.
- 앞부분은 대기열의 끝을 가리 키지 않아야합니다. 즉, max_size와 동일합니다.
그래서 알고리즘은 무엇입니까 ??
# 큐가 비어 있는지 확인하는 함수 def is_empty (self) : if (self .__ rear ==-1 or self .__ front == self .__ max_size) : return True else : return False # 요소를 deque하고 return하는 함수 it def dequeue (self) : if (self.is_empty ()) : print ( 'queue is already empty') else : data = self .__ elements [self .__ front] self .__ front + = 1 return data #function to display elements from 대기열이 비어 있지 않은 경우 앞뒤로 def display (self) : if (not self.is_empty ()) : for i in range (self .__ front, self .__ rear + 1) : print (self .__ elements [i]) else : print ( '빈 대기열')
이제 다음을 실행할 때 :
queue1 = 대기열 (5)
Windows에서 Java 경로 설정
# 모든 필수 요소를 대기열에 추가
queue1.enqueue ( 'A')
queue1.enqueue ( 'B')
queue1.enqueue ( 'C')
queue1.enqueue ( 'D')
queue1.enqueue ( 'E')
print (대기열 1)
# 모든 필수 요소 대기열에서 빼기
print ( '대기열에서 빼기 :', queue1.dequeue ())
print ( '대기열에서 빼기 :', queue1.dequeue ())
print ( '대기열에서 빼기 :', queue1.dequeue ())
print ( '대기열에서 빼기 :', queue1.dequeue ())
print ( '대기열에서 빼기 :', queue1.dequeue ())
print ( '대기열에서 빼기 :', queue1.dequeue ())
# 큐의 모든 요소를 표시합니다.
queue1.display ()
산출:
대기열 데이터 (전면에서 후면) : A B C D E
대기열에서 제거됨 : A
대기열에서 제거됨 : B
대기열에서 제거됨 : C
대기열에서 제거됨 : D
대기열에서 제거됨 : E
대기열이 이미 비어 있습니다.
대기열에서 제거됨 : 없음
빈 대기열
대기열의 응용
지금까지 대기열의 기본 사항을 이미 이해했습니다. 이제 더 깊이 들어가기 위해 몇 가지 응용 프로그램을 살펴 보겠습니다.
자바에서 얕은 복사와 깊은 복사의 차이점
- 예 1 :
Windows의 인쇄 대기열 대기열을 사용하여 모든 활성 및 보류중인 인쇄 작업을 저장합니다. 문서를 인쇄하려면 인쇄 명령을 차례로 실행합니다. 인쇄 명령에 따라 문서가 인쇄 대기열에 정렬됩니다. 프린터가 준비되면 문서가 먼저 인쇄되어 인쇄됩니다.
3 개의 문서에 대해 doc1, doc2 및 doc3 순서로 인쇄 명령을 실행했다고 가정합니다.
인쇄 대기열은 아래와 같이 채워집니다.
doc-n, 여기서 doc는 인쇄를 위해 전송 된 문서이고 n, 문서의 페이지 수입니다. 예를 들어, doc2-10은 doc2가 인쇄되고 10 페이지가 있음을 의미합니다. 다음은 인쇄 대기열 작업을 시뮬레이션하는 코드입니다. 코드를 살펴보고이 구현에서 큐가 어떻게 사용되는지 관찰하십시오.
class Queue : def __init __ (self, max_size) : self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0 def is_full (self) : if (self .__ rear = = self .__ max_size-1) : True 반환 False def is_empty (self) : if (self .__ front> self .__ rear) : True 반환 False def enqueue (self, data) : if (self.is_full ()) : print ( 'Queue is full !!!') else : self .__ rear + = 1 self .__ elements [self .__ rear] = data def dequeue (self) : if (self.is_empty ()) : print ( 'Queue is empty! !! ') else : data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self) : for index in range (self .__ front, self .__ rear + 1) : print (self .__ elements [index]) def get_max_size (self) : return self .__ max_size ## debugging def __str __ (self) : msg = [] index = self .__ front while을 사용하여 DS 객체의 요소를 인쇄 할 수 있습니다. (인덱스<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print('Queue is full') else: print_queue.enqueue(doc) print(doc,'sent for printing') #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=='-'): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,'printed') pages_in_printer-=no_of_pages print('Remaining no. of pages in printer:', pages_in_printer) else: print('Couldn't print',doc[:i],'. Not enough pages in the printer.') pages_in_printer=12 print_queue=Queue(10) send_for_print('doc1-5') send_for_print('doc2-3') send_for_print('doc3-6') start_printing()산출:
인쇄를 위해 doc1-5 전송
인쇄를 위해 doc2-3 전송
doc3-6 인쇄용으로 전송 됨
doc1-5 인쇄
남은 번호. 프린터 페이지 수 : 7
doc2-3 인쇄
남은 번호. 프린터 페이지 수 : 4
doc3을 인쇄 할 수 없습니다. 프린터에 페이지가 충분하지 않습니다.
- 예 2 :
Queue 데이터 구조를 사용하는 또 다른 예를 이해해 보겠습니다. 코드를 이해하고 다음 함수가 무엇을하는지 말할 수 있습니까?
- def fun (n) :
- aqueue = Queue (100)
- 범위 (1, n + 1)의 num 인 경우 :
- 대기열에 넣기 (num)
- 결과 = 1
- while (not (aqueue.is_empty ())) :
- 숫자 = AQUUE.DEQUEUE ()
- 결과 * = num
- 인쇄 (결과)
n을 전달하여 fun () 함수를 호출하면
- 2 ~ 4 행은 1 ~ n의 요소를 대기열에 추가합니다.
- 5 ~ 8 행은 대기열을 하나씩 제거하여 해당 요소의 곱을 찾습니다.
이것으로, 우리는이 큐 데이터 구조 기사의 끝으로 왔습니다. 성공적으로 코드를 이해하고 실행했다면 더 이상 Queue Data Structure의 초보자가 아닙니다.
질문이 있으십니까? 이 기사의 댓글 섹션에 언급 해 주시면 가능한 한 빨리 연락 드리겠습니다.
다양한 응용 프로그램과 함께 Python에 대한 심층적 인 지식을 얻으려면 라이브에 등록 할 수 있습니다. 연중 무휴 지원 및 평생 액세스.