Help us understand the problem. What is going on with this article?

循環配列を用いたキューの実装

概要

キュー(Queue)は先入れ先出し(First In First Out)を実現するためのデータ構造です。無限の長さを持つ配列があれば末尾に要素を追加していくだけでキューを実装できますが、実際には有限長の配列でキューを実装する必要があります。有限長の配列に要素を追加する際、配列の末尾がすでに埋まっていたら配列の先頭から格納していく必要があるため、剰余算術を用いて格納位置を決定します。下記に実装例を示します。

Screen Shot 2019-10-14 at 13.09.14.png

実装例

class MyCircularQueue(object):
    def __init__(self, k):
        # サイズkの配列を用いてキューを実装する
        self.k = k
        self.q = [None] * k
        self.first = 0 # 要素の先頭を表すindex
        self.last = 0  # 要素の末尾を表すindex

    # キューの末尾にデータを追加する
    def enQueue(self, value):
        if self.isFull():
            return False
        else:
            # 剰余をindexとして返す
            idx = self.last % self.k
            self.q[idx] = value
            self.last += 1
            return True

    # キューの先頭からデータを取り出す
    def deQueue(self):
        if self.isEmpty():
            return None
        else:
            # 剰余をindexとして返す
            idx = self.first % self.k
            val = self.q[idx]
            self.q[idx] = None
            self.first += 1
            return val

    # キューの先頭のデータを参照する
    def front(self):
        idx = self.first % self.k
        return self.q[idx]

    # キューの末尾のデータを参照する
    def rear(self):
        idx = (self.last - 1) % self.k
        return self.q[idx]

    # キューが空かどうか判定する
    def isEmpty(self):
        return self.first == self.last

    # キューが一杯かどうか判定する
    def isFull(self):
        return self.last - self.first == self.k

注意点

本来はキューが一杯になったら配列の長さを拡張する等の対応を行うことが望ましいですが、本記事では簡略化のため省略しています。

参考

https://ja.wikipedia.org/wiki/キュー_(コンピュータ)

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away