データ構造とはデータを格納する入れ物の構造のことです。適切なデータ構造を選ぶ事でデータの扱いが効率的になります。
データ構造
アルゴリズムはデータを扱うため、データの構造は非常に重要です。代表的なデータ構造を挙げます。
配列
添字を使って参照できるデータ構造で、プログラミング言語では添字の最初の数字は0であることが多いです。PythonではListを用いて配列を表すことができます。
PythonではListの代わりにより効率的なarrayモジュールを利用することもできます。ただしarrayモジュールは格納する型を定義するので、同じ型のデータしか格納できません。
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
| import array as arr
def tolist(*args):
return list(args)
def toarray(lis: list):
return arr.array('i', lis)
if __name__ == "__main__":
lis = tolist(1, 3, 2, 4, 7, 6, 8, 5)
print('list')
print(lis[0])
print(lis[1])
print(lis[2])
print(lis[3])
print(lis[4])
print(lis[5])
a = toarray(lis)
print('\narray')
print(a[0])
print(a[1])
print(a[2])
print(a[3])
print(a[4])
print(a[5])
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| list
1
3
2
4
7
6
array
1
3
2
4
7
6
|
PythonのListと似たデータ構造としてTupleもあります。こちらはListと違いイミュータブルになるという違いがあります。
スタック
最後に入れたデータが最初に取り出されるデータ構造のことです。データは格納した順序とは逆の順序で取り出されるます。このようなデータ構造のことをLIFO(Last In First Out)とも呼びます。
スタックに対する操作としてデータを格納する push とデータを取り出す pop が必要になります。
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
| class Stack:
def __init__(self) -> None:
self.lis = []
def pop(self):
if self.lis:
return self.lis.pop()
return None
def push(self, elem) -> None:
self.lis.append(elem)
if __name__ == '__main__':
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
|
キュー
最初に入れたデータが最初に取り出されるデータ構造のことです。データは格納した順序通りに取り出されます。このようなデータ構造のことをFIFO(First In First Out)とも呼びます。
キューに対する操作としてデータを格納する enqueue とデータを取り出す dequeue が必要になります。
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
| class Queue(object):
def __init__(self) -> None:
self.stack1 = []
self.stack2 = []
def enqueue(self,element) -> None:
self.stack1.append(element)
def dequeue(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
if not self.stack2:
return None
return self.stack2.pop()
if __name__ == '__main__':
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
|