前の記事でデータ構造の重要性についてすでに学習したので、記事のトピック、つまりキューデータ構造に飛び込みましょう。次のトピックについて説明します。
キューデータ構造の必要性
ある日映画が欲しいとしましょう。マルチプレックスでは、チケットは先着順で発行され、人々は順番を待って互いに後ろに立っていました。それで、あなたは何をしますか？あなたは後ろに行って、チケットを待っている最後の人の後ろに立っていたに違いありません。
ここでは、人々は前後に立っており、彼らはに基づいてサービスを受けています 先入れ先出し（FIFO） 機構。このような配置は、 キュー。
キューの日常生活の例
日常生活で働くキュータイプを使用するいくつかの例を考えてみましょう。
- 電話応答システム- ガジェットを最初に呼び出す人が最初に参加します。
- 手荷物検査機 –最初にコンベヤーベルトに保持されていた荷物をチェックします。
- 通行税橋の車両 –早く到着した車両が最初に出発します。
- コールセンター –電話システムは、サービス担当者が空くまで、キューを使用して、電話をかける人を順番に保持します。
これらの例はすべて次のとおりです ファーストインラストアウト 戦略。
キューデータ構造の作成
補完的な操作とは別に、キューで可能な主な操作は次のとおりです。
1。 エンキュー または、キューの最後に要素を追加します。
2.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 キューで予想される要素の最大数です。
- キューの要素はPythonリストに保存されます
- 後部は、キューの最後の要素のインデックス位置を示します。
- キューが空であるため、リアは最初は-1と見なされます
- Frontは、キューの最初の要素の位置を示します。
- フロントは常にキューの最初の要素を指すため、最初は0と見なされます。
エンキュー
ここで、要素をキューにエンキューしようとするときは、次の点に注意する必要があります。
- キューにスペースが残っているかどうか、つまり、rearがmax_size-1に等しいかどうか
- 後部は、キューに挿入された最後の要素を指します。
では、アルゴリズムはどうなるのでしょうか？
＃キューのmax_sizeを返しますdef get_max_size（self）：return self .__ max_size＃キューがいっぱいかどうかに関係なくブール値を返します。いっぱいの場合は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 + = 1self。 __elements [self .__ Rear] = data＃キューのすべてのコンテンツを表示def display（self）：for i in range（0、self .__ Rear + 1）：print（self .__ elements [i]）＃使用できます__str __（）の下で、def __str __（self）のデバッグ中にDSオブジェクトの要素を出力します。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 = Queue（5）
＃必要なすべての要素をキューに入れます。
queue1.enqueue（ 'A'）
queue1.enqueue（ 'B'）
queue1.enqueue（ 'C'）
queue1.enqueue（ 'D'）
queue1.enqueue（ 'E'）
queue1.display（）
queue1.enqueue（ 'F'）
print（queue1）
出力：
に
B
C
D
IS
キューがいっぱいです。エンキューできません
キューデータ（前から後）：A B C D E
デキュー
ここで、要素をキューに挿入/エンキューしたので、要素をフロントからデキュー/削除する必要があるため、次の点に注意する必要があります。
- キューに要素があります。つまり、rearは-1に等しくてはなりません。
- 次に、要素が前面から削除されるため、前面を削除した後、次の前面を指すようにインクリメントする必要があることを覚えておく必要があります。
- フロントはキューの終わりを指してはいけません。つまり、max_sizeと同じです。
では、アルゴリズムはどうなるのでしょうか？
＃キューが空かどうかをチェックする関数def is_empty（self）：if（self .__ Rear ==-1 or self .__ front == self .__ max_size）：return True else：return False #function to deque a element and return it def dequeue（self）：if（self.is_empty（））：print（ 'キューはすでに空です'）else：data = self .__ elements [self .__ front] self .__ front + = 1 return data #function to display element fromキューが空でない場合は前面から背面へdefdisplay（self）：if（not self.is_empty（））：for i in range（self .__ front、self .__ Rear + 1）：print（self .__ elements [i]）else ：print（ '空のキュー'）
次を実行すると：
queue1 = Queue（5）
＃必要なすべての要素をキューに入れます
queue1.enqueue（ 'A'）
queue1.enqueue（ 'B'）
queue1.enqueue（ 'C'）
c ++に移動
queue1.enqueue（ 'D'）
queue1.enqueue（ 'E'）
print（queue1）
Eclipseでのキュウリの例を含むセレンウェブドライバー
＃必要なすべての要素をデキューします
print（“ Dequeued：“、queue1.dequeue（））
print（“ Dequeued：“、queue1.dequeue（））
print（“ Dequeued：“、queue1.dequeue（））
print（“ Dequeued：“、queue1.dequeue（））
print（“ Dequeued：“、queue1.dequeue（））
print（“ Dequeued：“、queue1.dequeue（））
＃キュー内のすべての要素を表示します。
queue1.display（）
出力：
キューデータ（前から後）：A B C D E
デキュー：A
デキュー：B
デキュー：C
デキュー：D
デキュー：E
キューはすでに空です
デキュー：なし
空のキュー
キューのアプリケーション
今のところ、あなたはすでにキューの基本を理解しています。次に、さらに深く掘り下げて、そのアプリケーションのいくつかを調べます。
- 例1：
Windowsの印刷キュー キューを使用して、アクティブおよび保留中のすべての印刷ジョブを保存します。ドキュメントを印刷したいときは、次々と印刷コマンドを発行します。印刷コマンドに基づいて、ドキュメントは印刷キューに並べられます。プリンタの準備が整うと、ドキュメントは先入れ先出しで送信され、印刷されます。
doc1、doc2、doc3の順に3つのドキュメントに対して印刷コマンドを発行したとします。
以下に示すように、印刷キューにデータが入力されます。
doc-n、ここでdocは印刷用に送信されたドキュメントであり、n、 ドキュメントのページ数です。たとえば、doc2-10は、doc2が印刷され、10ページあることを意味します。これは、印刷キューの操作をシミュレートするコードです。コードを調べて、この実装でキューがどのように使用されるかを観察します。
クラスキュー：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）：return True return False def is_empty（self）：if（self .__ front> self .__ Rear）：return True return False def enqueue（self、data）：if（self.is_full（））： print（ 'キューがいっぱいです!!!'）else：self .__ Rear + = 1 self .__ elements [self .__ Rear] = data def dequeue（self）：if（self.is_empty（））：print（ 'キューが空です！ !! '）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＃以下の__str __（）を使用して、DSオブジェクトの要素を出力できます。＃debugging def __str __（self）：msg = [] index = self .__ front while （インデックス<=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：
キューのデータ構造を使用する別の例を理解してみましょう。コードを理解して、次の関数が何をするのかを教えてください。
- def fun（n）：
- aqueue = Queue（100）
- range（1、n + 1）のnumの場合：
- エンキュー（num）
- 結果= 1
- while（not（aqueue.is_empty（）））：
- num = AQUUE.DEQUEUE（）
- 結果* = num
- 印刷（結果）
nを渡して関数fun（）を呼び出すと、
- 2行目から4行目は、1からnまでの要素をエンキューします。
- 5行目から8行目では、これらの要素の積を1つずつデキューして見つけます。
これで、このキューデータ構造の記事は終わりです。自分でコードを正しく理解して実行した場合、キューデータ構造の初心者ではなくなります。
質問がありますか？この記事のコメントセクションにその旨を記載してください。できるだけ早くご連絡いたします。
Pythonとそのさまざまなアプリケーションに関する詳細な知識を得るには、ライブに登録できます。 24時間年中無休のサポートと生涯アクセス。