コンテンツにスキップ

Week 4 (2025/5/2)

今週の目的

ファイルのデータをスタックやキューに格納する。

今週のキーワード

  • スタック
  • プッシュ
  • ポップ
  • キュー
  • エンキュー
  • デキュー
  • ダックタイピング（ポリモーフィズム）

今回は連結リストを用いてスタックとキューを実装し、プッシュとポップ、エンキューとデキューを行うプログラムを作成する。スタックは、リスト(配列)や連結リストと同じ順序付きのデータを格納するデータ構造で、データの入口と出口が同じものである。つまり、 データの挿入および取り出しが先頭か末尾のどちらか一方だけで行われる。 スタックへのデータの追加をプッシュ、スタックからのデータの取り出しをポップという。最後に追加したデータから取り出されるため、 LIFO(Last-In First-Out) とも呼ばれる。

一方、キューは、リストや連結リストと同じ順序付きのデータを格納するデータ構造で、データの入口と出口が異なるものである。つまり、 データが先頭に挿入されるのであれば、末尾からデータが取り出され、データが末尾に挿入されるのであれば、先頭からデータが取り出される。 キューへのデータの追加をエンキュー、キューからのデータの取り出しをデキューという。最初に追加したデータから取り出されるため、FIFO(First-In First-Out)とも呼ばれる。

本演習では連結リストを用いて、スタック(Stackインスタンス)にプッシュし、スタックからポップするプログラムと、キュー(Queueインスタンス)にエンキューし、キューからデキューするプログラムを作成する。

今回作成するStackクラスとQueueクラスの仕様は、以下の通りである

Stackクラス

class Stack()
スタックのクラス

インスタンス変数

  • top: 連結リストの先頭の節（Nodeインスタンス）

push(data)
スタックにデータをプッシュするメソッド

パラメータ

  • data: スタックに挿入するデータ（Stopインスタンス）

pop()
スタックからデータをポップするメソッド

返り値

  • スタックの先頭に格納されていたデータ（Stopインスタンス）。スタックが空であればNoneを返す。

display()
スタックの中身を表示するメソッド

Queueクラス

class Queue()
キューのクラス

インスタンス変数

  • top: 連結リストの先頭の節（Nodeインスタンス）
  • rear: 連結リストの末尾の節（Nodeインスタンス）

enqueue(data)
キューにデータをエンキューするメソッド

パラメータ

  • data: キューに挿入するデータ

dequeue()
キューからデータをデキューするメソッド

返り値

  • キューの先頭に格納されていたデータ(Stopインスタンス）。キューが空であればNoneを返す。

display()
キューの中身を表示するメソッド

なお、前回作成したNodeクラスの定義をimportするために、def_node.py をダウンロードし、同一ディレクトリに保存して用いよ。

課題1：スタックにデータをプッシュする

以下のプログラムの穴あき部分を埋めて、スタックにデータをプッシュするメソッド(push(self, data))を完成させ、実行例の通りに動くことを確認せよ。 pushメソッドは、dataがStopインスタンスであることを確認してから、スタック内の連結リストの先頭(top)に節を挿入する。また、Stopインスタンス以外がpushされた時は「Stopインスタンス以外はPUSHできません。」と表示すること。

ヒント

第３週で取り組んだ「連結リストの先頭へのデータの挿入方法」を思い出そう。なお、あるオブジェクトがStopインスタンスかどうか確認するには、以下のisinstance(object, class)関数を用いるとよい。

isinstance関数

isinstance(object, class)
オブジェクトがあるクラスのインスタンスかどうか確認する関数

パラメータ

  • object: 対象のオブジェクト
  • class: 対象のクラス

返り値

  • 対象のオブジェクトが対象のクラスのインスタンスであればTrue、そうでなければFalseを返す（ブール値）

使用例 

print(isinstance('123', str))

APIの詳細は公式のページを参照すること。

week4_1.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 穴埋め問題用のプログラム
# StopクラスおよびStopインスタンスのimport
from def_stop import Stop, ritsumeikan, doshisha, kyodai, kyosan, ryukoku
# Nodeクラスの定義をdef_node.pyからインポート
from def_node import Node

# Stackクラスの定義
class Stack:
    def __init__(self):
        self.top = None  # 連結リストの先頭を指すリストヘッドのインスタンス変数

    def display(self):  # スタック内の連結リストを表示するメソッド
        print('======スタックの先頭======')
        message = '{}(ID:{})のバス停の緯度経度は({},{})です。'
        p = self.top  # 走査用変数pを連結リストの先頭に設定する
        while p is not [____]:  # 走査用変数pが連結リストの終端でない限り、以下の処理を繰り返す
            print(message.format(p.data.name, p.data.id, p.data.lat, p.data.lng))
            p = [____]  # 走査用変数pを次の節に一つ進める
        print('======スタックの底======')

    def push(self, data):  # PUSHメソッド
        if(isinstance(data, Stop)):  # PUSHするデータがStopインスタンスかどうか確認
            [____] = Node(data, [____])  # 連結リストの先頭に節を挿入
        else:
            print('Stopインスタンス以外はPUSHできません。')

s = Stack()  # スタック(Stackインスタンス)を生成
s.display()  # 空のスタックを表示する
s.push(1)  # Stopインスタンス以外をpush
s.push([____])  # スタックにStopインスタンスをPUSHする
s.push([____])
s.push([____])
s.push([____])
s.push([____])
s.display()  # スタックを表示する

======スタックの先頭======
======スタックの底======
Stopインスタンス以外はPUSHできません。
======スタックの先頭======
龍谷大学前(ID:ED01_2263)のバス停の緯度経度は(34.9631519,135.76834405)です。
京都産大前(ID:ED01_2244)のバス停の緯度経度は(35.07182049,135.75638731)です。
京大正門前(ID:ED01_1841)のバス停の緯度経度は(35.02548675,135.7786403)です。
同志社前(ID:ED01_1922)のバス停の緯度経度は(35.02913136,135.76314762)です。
立命館大学前(ID:ED01_1914)のバス停の緯度経度は(35.03497163,135.72602961)です。
======スタックの底======

課題2：スタックからデータをポップする

課題1のプログラムを修正し、スタックに積まれたデータをポップするメソッド(pop(self))を追加せよ。popメソッドはスタック内の連結リストの先頭(top)の節を切り取り、その節に格納されているStopインスタンスを返す(return)こと。さらに、スタックが空の時は「スタックが空でPOPできません。」と表示してNoneを返す(return)こと。

課題1の通りにStopインスタンスをスタックに追加した後、popメソッドを用いて、スタックが空になるまでスタックから一つずつStopインスタンスを取り出しそのStopインスタンスを表示して、実行例の通りに動くことを確認せよ。

ヒント

第3週で取り組んだ「連結リストのデータの切り取り」を思い出そう。

龍谷大学前(ID:ED01_2263)のバス停の緯度経度は(34.9631519,135.76834405)です。
京都産大前(ID:ED01_2244)のバス停の緯度経度は(35.07182049,135.75638731)です。
京大正門前(ID:ED01_1841)のバス停の緯度経度は(35.02548675,135.7786403)です。
同志社前(ID:ED01_1922)のバス停の緯度経度は(35.02913136,135.76314762)です。
立命館大学前(ID:ED01_1914)のバス停の緯度経度は(35.03497163,135.72602961)です。
スタックが空でPOPできません。

課題3：キューを作る

課題1と課題2で実装したスタックのプログラムを参考に、キューにデータをエンキューするメソッドと、キューからデータをデキューするメソッドをもつ以下のQueueクラスを実装せよ。

enqueueメソッドは、スタックのpushメソッドのようにdataがStopインスタンスであることを確認してから、キュー内の連結リストの末尾(rear)に節を挿入すること。また、Stopインスタンス以外がenqueueされた時は「Stopインスタンス以外はENQUEUEできません。」と表示すること。一方、dequeueメソッドは、スタックのpopメソッドと同様にキュー内の連結リストの先頭(top)から節を切り取り、その節に格納されているStopインスタンスを返す(return)こと。さらに、キューが空の時は「キューが空でDEQUEUEできません。」と表示してNoneを返す(return)すること。

このenqueueメソッドを用いて、数字の「1」および「立命館大学前」「同志社前」「京大正門前」「京都産大前」「龍谷大学前」の各Stopインスタンスを順にエンキューせよ。次にdisplayメソッドを用いてキューの中身を表示し、実行例の通り、キューの末尾にデータが追加されていることを確認せよ。さらに、dequeueメソッドを用いて、キューが空になるまでキューから一つずつStopインスタンスを取り出してそのStopインスタンスを表示し、実行例の通りに動くことを確認せよ。

ヒント

連結リストの末尾への挿入は、連結リストの末尾を指すリストヘッド(rear)を用いよう。挿入後に忘れずにその末尾のリストヘッドの位置を更新すること。連結リストの先頭の切り取りは課題2を参考にするとよい。

Stopインスタンス以外はENQUEUEできません。
======キューの先頭======
立命館大学前(ID:ED01_1914)のバス停の緯度経度は(35.03497163,135.72602961)です。
同志社前(ID:ED01_1922)のバス停の緯度経度は(35.02913136,135.76314762)です。
京大正門前(ID:ED01_1841)のバス停の緯度経度は(35.02548675,135.7786403)です。
京都産大前(ID:ED01_2244)のバス停の緯度経度は(35.07182049,135.75638731)です。
龍谷大学前(ID:ED01_2263)のバス停の緯度経度は(34.9631519,135.76834405)です。
======キューの末尾======
立命館大学前(ID:ED01_1914)のバス停の緯度経度は(35.03497163,135.72602961)です。
同志社前(ID:ED01_1922)のバス停の緯度経度は(35.02913136,135.76314762)です。
京大正門前(ID:ED01_1841)のバス停の緯度経度は(35.02548675,135.7786403)です。
京都産大前(ID:ED01_2244)のバス停の緯度経度は(35.07182049,135.75638731)です。
龍谷大学前(ID:ED01_2263)のバス停の緯度経度は(34.9631519,135.76834405)です。
キューが空でDEQUEUEできません。

発展課題4：リストでスタックとキューを作る

リストクラスのappendメソッドとpopメソッドを用いて、pushメソッドとpopメソッド、displayメソッドを備えたListStackクラスと、enqueueメソッドとdequeueメソッド、displayメソッドを備えたListQueueクラスを実装せよ。displayメソッドは内部のリストを表示するものとし、ListStackクラスのdisplayメソッドは「======スタックの先頭======」と「======スタックの底======」、ListQueueクラスのdisplayメソッドは「======キューの先頭======」と「======キューの末尾======」を表示すること。なお、スタックはデータを出入り口を先頭、キューはデータの入り口を末尾、出口を先頭とする。

今回作成するListStackクラスとListQueueクラスの仕様は、以下の通りである

ListStackクラス

class ListStack()
スタックのクラス

インスタンス変数

  • list: データ格納用のリスト

push(data)
スタックにデータをプッシュするメソッド

パラメータ

  • data: スタックに挿入するデータ（Stopインスタンス）

pop()
スタックからデータをポップするメソッド

返り値

  • スタックの先頭に格納されていたデータ（Stopインスタンス）。スタックが空であればNoneを返す。

display()
スタックの中身を表示するメソッド

ListQueueクラス

class ListQueue()
キューのクラス

インスタンス変数

  • list: データ格納用のリスト

enqueue(data)
キューにデータをエンキューするメソッド

パラメータ

  • data: キューに挿入するデータ

dequeue()
キューからデータをデキューするメソッド

返り値

  • キューの先頭に格納されていたデータ(Stopインスタンス）。キューが空であればNoneを返す。

display()
キューの中身を表示するメソッド

さらに、kyotocitybus_stop.datからバス停データを読み込み、読み込んだ順に全てのデータをスタックにプッシュし、その後ポップしたデータを全て表示せよ。同様に、kyotocitybus_stop.datからバス停データを読み込み、読み込んだ順に全てのデータをキューにエンキューし、その後デキューしたデータを全て表示せよ。また、実行例の通りに動くことを確認し、出力結果がスタックとキューで逆順になっていることに注意せよ。

京都駅八条口(ID:ED01_4102)のバス停の緯度経度は(34.98401063,135.75866056)です。
京都駅前(ID:ED01_4089)のバス停の緯度経度は(34.98719397,135.75802795)です。
京都会館美術館前(ID:ED01_2307)のバス停の緯度経度は(35.01363868,135.78107416)です。
(途中省略)
大宮総門口町(ID:ED01_1639)のバス停の緯度経度は(35.05831804,135.74403767)です。
神光院前(ID:ED01_1638)のバス停の緯度経度は(35.06134071,135.74395031)です。
西賀茂車庫前(ID:ED01_1637)のバス停の緯度経度は(35.06385669,135.74499864)です。
スタックが空でPOPできません。
西賀茂車庫前(ID:ED01_1637)のバス停の緯度経度は(35.06385669,135.74499864)です。
神光院前(ID:ED01_1638)のバス停の緯度経度は(35.06134071,135.74395031)です。
大宮総門口町(ID:ED01_1639)のバス停の緯度経度は(35.05831804,135.74403767)です。
(途中省略)
京都会館美術館前(ID:ED01_2307)のバス停の緯度経度は(35.01363868,135.78107416)です。
京都駅前(ID:ED01_4089)のバス停の緯度経度は(34.98719397,135.75802795)です。
京都駅八条口(ID:ED01_4102)のバス停の緯度経度は(34.98401063,135.75866056)です。
キューが空でDEQUEUEできません。

発展課題5：ポリモーフィズムを使う

課題１のスタック（Stackクラス）と発展課題4のListStackクラス、課題3のキュー（Queueクラス）と発展課題4のListQueueクラスを用いて、kyotocitybus_stop.datから読み込んだ全てのバス停データを、読み込んだ順に各スタックおよび各キューに格納せよ。その後、displayメソッドを用いて、格納したデータを表示し比較せよ。なお、ポリモーフィズムを用いて実装すること。

ヒント

ポリモーフィズムとは、同じメソッド名を用いることで、呼び出し方法を変えずにオブジェクトを変えるだけで振る舞いを変えることである。スタックの各インスタンスをリストに格納し、for文で一つずつ異なる実装のスタックインスタンスを取り出して、ループ内でそれぞれのpushメソッドを用いてスタックにデータを格納するとよい。キューも同様である。

======スタックの底======
西賀茂車庫前(ID:ED01_1637)のバス停の緯度経度は(35.06385669,135.74499864)です。
神光院前(ID:ED01_1638)のバス停の緯度経度は(35.06134071,135.74395031)です。
大宮総門口町(ID:ED01_1639)のバス停の緯度経度は(35.05831804,135.74403767)です。
(途中省略)
京都会館美術館前(ID:ED01_2307)のバス停の緯度経度は(35.01363868,135.78107416)です。
京都駅前(ID:ED01_4089)のバス停の緯度経度は(34.98719397,135.75802795)です。
京都駅八条口(ID:ED01_4102)のバス停の緯度経度は(34.98401063,135.75866056)です。
======スタックの先頭======
======スタックの先頭======
京都駅八条口(ID:ED01_4102)のバス停の緯度経度は(34.98401063,135.75866056)です。
京都駅前(ID:ED01_4089)のバス停の緯度経度は(34.98719397,135.75802795)です。
京都会館美術館前(ID:ED01_2307)のバス停の緯度経度は(35.01363868,135.78107416)です。
(途中省略)
大宮総門口町(ID:ED01_1639)のバス停の緯度経度は(35.05831804,135.74403767)です。
神光院前(ID:ED01_1638)のバス停の緯度経度は(35.06134071,135.74395031)です。
西賀茂車庫前(ID:ED01_1637)のバス停の緯度経度は(35.06385669,135.74499864)です。
======スタックの底======
======キューの先頭======
西賀茂車庫前(ID:ED01_1637)のバス停の緯度経度は(35.06385669,135.74499864)です。
神光院前(ID:ED01_1638)のバス停の緯度経度は(35.06134071,135.74395031)です。
大宮総門口町(ID:ED01_1639)のバス停の緯度経度は(35.05831804,135.74403767)です。
(途中省略)
京都会館美術館前(ID:ED01_2307)のバス停の緯度経度は(35.01363868,135.78107416)です。
京都駅前(ID:ED01_4089)のバス停の緯度経度は(34.98719397,135.75802795)です。
京都駅八条口(ID:ED01_4102)のバス停の緯度経度は(34.98401063,135.75866056)です。
======キューの末尾======
======キューの先頭======
西賀茂車庫前(ID:ED01_1637)のバス停の緯度経度は(35.06385669,135.74499864)です。
神光院前(ID:ED01_1638)のバス停の緯度経度は(35.06134071,135.74395031)です。
大宮総門口町(ID:ED01_1639)のバス停の緯度経度は(35.05831804,135.74403767)です。
(途中省略)
京都会館美術館前(ID:ED01_2307)のバス停の緯度経度は(35.01363868,135.78107416)です。
京都駅前(ID:ED01_4089)のバス停の緯度経度は(34.98719397,135.75802795)です。
京都駅八条口(ID:ED01_4102)のバス停の緯度経度は(34.98401063,135.75866056)です。
======キューの末尾======
Back to top