データ構造ノート-スタックとキューpython
6815 ワード
概要
スタックとキューは、プログラム設計で広く応用されている2つの重要なデータ構造であり、いずれも特定の範囲のメモリセル内にデータを格納し、これらのデータは再取り出して使用することができ、線形テーブルに比べて、挿入と削除はより多くの制約を受け、限定的な線形テーブル構造とも呼ばれている.データ・アイテムのストレージとアクセスのみをサポートし、データ・アイテム間の関係はサポートしません.したがって,この2つのデータセットはいずれも小さく,簡単であり,その中で最も重要な操作は要素の格納と取り出しである.データ構造としては、構造の作成、空の状態であるかどうかを確認するなど、いくつかのデータ構造に必要な操作が必要です.
計算では,中間データオブジェクトの生成が早いか遅いか,時間的な前後順が存在する.これらの要素を後で使用する場合は、生成時間の順序も考慮する必要があります.
→スタックは,要素の後進先出(後進先出,Last In First Out,LIFO)関係を保証する構造である.
→キューは,要素の先進的な先出し(先入者が先に使用し,First In First Out)関係を保証する構造である.
1.スタック
スタックはコンテナで、データを格納したり、要素にアクセスしたり、要素を削除したりすることができます.スタックに格納された要素は互いに具体的な関係がなく、到来した時間の前後順しかありません.ここでは要素の位置,要素の前後順などの概念はない.スタックの基本的な性質は、いつでもアクセスでき、削除された要素は、その前の最後に格納された要素であることを保証します.したがって、スタックはデフォルト要素のアクセス順序を決定し、アクセス数は他の情報を必要としません.
1_1.スタックの抽象データ型の説明:
スタックとキューは、プログラム設計で広く応用されている2つの重要なデータ構造であり、いずれも特定の範囲のメモリセル内にデータを格納し、これらのデータは再取り出して使用することができ、線形テーブルに比べて、挿入と削除はより多くの制約を受け、限定的な線形テーブル構造とも呼ばれている.データ・アイテムのストレージとアクセスのみをサポートし、データ・アイテム間の関係はサポートしません.したがって,この2つのデータセットはいずれも小さく,簡単であり,その中で最も重要な操作は要素の格納と取り出しである.データ構造としては、構造の作成、空の状態であるかどうかを確認するなど、いくつかのデータ構造に必要な操作が必要です.
計算では,中間データオブジェクトの生成が早いか遅いか,時間的な前後順が存在する.これらの要素を後で使用する場合は、生成時間の順序も考慮する必要があります.
→スタックは,要素の後進先出(後進先出,Last In First Out,LIFO)関係を保証する構造である.
→キューは,要素の先進的な先出し(先入者が先に使用し,First In First Out)関係を保証する構造である.
1.スタック
スタックはコンテナで、データを格納したり、要素にアクセスしたり、要素を削除したりすることができます.スタックに格納された要素は互いに具体的な関係がなく、到来した時間の前後順しかありません.ここでは要素の位置,要素の前後順などの概念はない.スタックの基本的な性質は、いつでもアクセスでき、削除された要素は、その前の最後に格納された要素であることを保証します.したがって、スタックはデフォルト要素のアクセス順序を決定し、アクセス数は他の情報を必要としません.
1_1.スタックの抽象データ型の説明:
ADT Stack:
Stack(self) #
is_empty(self) # , True False
push(self,e) # elem ，
pop(self) # ，
top(self) # ，
1_2.
， size， arr， arr[size]， arr[size-1] ， size ， 。
#!/usr/bin/python
# -*- coding:utf-8 -*-
#
# ：
class MyStack:
__slots__ = ('items')#
#
def __init__(self):
self.items = []
#
def is_empty(self):
return len(self.items)==0
#
def size(self):
return len((self.items))
#
def top(self):
if not self.is_empty():
return self.items[len(self.items)-1]
else:
return None
#
def pop(self):
if len(self.items)>0:
return self.items.pop()
else:
print(' ')
return None
#
def push(self,item):
self.items.append(item)
if __name__ == "__main__":
s = MyStack()
s.push(4)
s.push(3)
s.push(2)
s.push(1)
print(' : '+str(s.top()))
print(' : '+str(s.size()))
s.pop()
print(' ')
: 1
: 4
[Finished in 0.1s]
1_3.
， ， ， ， 。 ， next ， next ， ， head.next.next ， head.next.data 。
# ：
class LNode:
def __init__(self,x,next_=None):
self.data = x
self.next = next_
class MyStack:
def __init__(self):
#pHead=LNode()
self.data = None
self.next = None
# stack , true, false
def empty(self):
if self.next ==None:
return True
else:
return False
#
def size(self):
size = 0
p = self.next
while p != None:
p = p.next
size += 1
return size
# :
def push(self,e):
p = LNode(e)
p.next = self.next#None
self.next = p
def pop(self):
tmp = self.next
if tmp != None:
self.next = tmp.next
return tmp.data
print(' ')
return None
def top(self):
if self.next != None:
return self.next.data
print(' ')
return None
if __name__ == '__main__':
stack = MyStack()
stack.push(4)
stack.push(3)
stack.push(2)
stack.push(1)
print(' ： '+str(stack.top()))
print(' : '+str(stack.size()))
stack.pop()
print(' ')
， LNode.
： 1
: 4
[Finished in 0.1s]
2.
， ， ， ， 。 ， ， 。
2_1. ：
ADT Queue:
Queue(self) #
is_empty(self) # ， True False
enqueue(self,e) # elem ，
dequeue(self) # ，
peek(self) # ，
2_2.
front rear ， rear ， rear＋， front＋ 。
#!/usr/bin/python
# -*- coding:utf-8 -*-
# ：
class MyQueue:
def __init__(self):
self.arr = []
self.front = 0#
self.rear = 0#
def isEmpty(self):
return self.front == self.rear
#
def size(self):
return self.rear - self.front
#
def getFront(self):
if self.isEmpty():
return None
return self.arr[self.front]
#
def getBack(self):
if self.isEmpty():
return None
return self.arr[self.rear-1]
#
def deQueue(self):
if self.rear>self.front:
self.front +=1
else:
print(" ")
#
def enQueue(self,item):
self.arr.append(item)
self.rear += 1
if __name__ == '__main__':
queue = MyQueue()
queue.enQueue(1)
queue.enQueue(2)
print(' '+str(queue.getFront()))
print(' '+str(queue.getBack()))
print(' :'+str(queue.size()))
1
2
:2
[Finished in 0.1s]
2_3.
， pHead pEnd ， pEnd pEnd+1， pHead pHead.next.next， 。
# ：
class LNode:
def __init__(self,x,next_=None):
self.data = x
self.next = next_
class MyQueue:
#
def __init__(self):
self.pHead = None
self.pEnd = None
#
def isEmpty(self):
if self.pHead == None:
return True
else:
return False
#
def size(self):
size = 0
p = self.pHead
while p != None:
p = p.next
size += 1
return size
# ： e
def enQueue(self,e):
p = LNode(e)
p.next = None
if self.pHead == None:
self.pHead = self.pEnd = p
else:
self.pEnd.next = p
self.pEnd = p
#
def deQueue(self):
if self.pHead == None:
print(" ， ")
print(' ：'+str(self.pHead.data))
self.pHead = self.pHead.next
if self.pHead == None:
self.pEnd = None
#
def getFront(self):
if self.pHead == None:
print(" ")
return None
return self.pHead.data
#
def getBack(self):
if self.pEnd == None:
print(" ")
return None
return self.pEnd.data
if __name__ == "__main__":
queue = MyQueue()
queue.enQueue(1)
queue.enQueue(2)
print(' '+str(queue.getFront()))
print(' '+str(queue.getBack()))
print(' :'+str(queue.size()))
1
2
:2
[Finished in 0.1s]