Study/Python
[파이썬] 0328 수업 아카이빙 : 자료구조 (stack, queue)
minulbora
2024. 3. 28. 14:37
스택(Stack): 데이터를 일시적으로 저장하기 위해 사용하는 구조로, 데이터의 입력과 출력 순서는 후입선출(last in first out)로 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 구조
자료구조를 파이썬으로 공부하는 이유 : 문법이 비교적 간단하므로 직관적으로 원리에 집중할 수 있다.
pop, push, peek, isEmpty
스택 1 (리스트로 스택 구현하기)
#리스트를 이용한 스택
class Stack:
def __init__(self):
self.stack_items = []
def push(self, a):
self.stack_items.append(a)
#pop 기능 구현
def pop(self):
item_length=len(self.stack_items)
#stack 이 비어있을 때
if item_length<=0:
print('stack 이 비어 있습니다.')
return False
#가장 위에 있는 값을 반환하고 삭제
result = self.stack_items[item_length-1]
del self.stack_items[item_length-1]
return result
def isEmpty(self):
return not self.stack_items
#리스트를 이용한 스택 실행
test = Stack()
print(test.stack_items)
test.push(3)
print(test.stack_items)
test.push(4)
test.push(5)
test.push(6)
test.push(7)
print(test.stack_items)
print(test.isEmpty())
print(test.pop())
print(test.pop())
print(test.pop())
print(test.pop())
print(test.isEmpty())
print(test.pop())
print(test.isEmpty())결과
[] [3] [3, 4, 5, 6, 7] False 7 6 5 4 False 3 True
스택 2 (노드를 이용해서 해보기)
#node 를 이용한 스택 구현
class Node:
def __init__(self,data):
self.data = data
self.next = None #자바에서 null = 파이썬에서 None, 다음 노드의 주소값
class Stack:
def __init__(self):
self.head = None
def is_empty(self):
if not self.head:
return True
return False
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
#node 가 초기화되고 next에는 next 주소값이 들어가게 됨. 그걸 head가 쳐다보고 있음.
#디버깅용
if new_node.next != None:
print('self.head.data : ',self.head.data,
' new_node.next.data : ',new_node.next.data)
else:
print('self.head.data : ',self.head.data,
' new_node.next : ',new_node.next)
def pop (self):
if self.is_empty():
return None
retData = self.head.data
self.head = self.head.next
return retData
def peek(self):
if self.is_empty():
return None
return self.head.data
s = Stack()
print(s.is_empty())
s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.push(5)
print('peek of data : {}'.format(s.peek()))
while not s.is_empty():
print(s.pop())#결과
True
self.head.data : 1 new_node.next : None
self.head.data : 2 new_node.next.data : 1
self.head.data : 3 new_node.next.data : 2
self.head.data : 4 new_node.next.data : 3
self.head.data : 5 new_node.next.data : 4
peek of data : 5
5
4
3
2
1큐 (리스트를 이용해 구현) : item을 삽입하는 Enqueue 기능과 요소를 빼내는 Dequeue 기능이 있음. 처음에 삽입한 요소가 먼저 빠지게 되는 First In First Out 특징을 가짐.
#리스트를 이용한 큐 구현
class Queue:
def __init__(self):
self.Queue_item = []
def Enqueue(self, a):
self.Queue_item.append(a)
return None
def Dequeue (self):
item_length = len(self.Queue_item)
if item_length <1:
print('Queue is Empty...')
return False
result = self.Queue_item[0]
del self.Queue_item[0]
return result
def isEmpty(self):
return not self.Queue_item
queue = Queue()
print(queue.Queue_item)
queue.Enqueue(1)
print(queue.Queue_item)
print(queue.Dequeue())
queue.Enqueue(2)
queue.Enqueue(3)
queue.Enqueue(4)
queue.Enqueue(5)
print(queue.Queue_item)
print(queue.Dequeue())
print(queue.Dequeue())
print(queue.Dequeue())
print(queue.Dequeue())
print(queue.isEmpty())
print(queue.Dequeue())#결과
[]
[1]
1
[2, 3, 4, 5]
2
3
4
5
True
Queue is Empty...
False큐 2 (노드)
#노드를 이용한 큐 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__ (self):
self.head = None
self.tail = None
def is_empty(self):
if not self.head:
return True
return False
def enqueue (self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
#디버깅 (처음에만 찍힘)
print('self.is_empty()- new_node : ', new_node)
print('self.is_empty()- self.head : ', self.head)
print('self.is_empty()- self.tail : ', self.tail)
return
self.tail.next = new_node
self.tail = new_node
#디버깅
print('enqueue() 결과 head.data :',self.head.data)
print('enqueue() 결과 tail.data :',self.tail.data)
def dequeue (self):
if self.is_empty():
return None
retData = self.head.data
self.head = self.head.next
return retData
def peek(self):
if self.is_emtpy():
return None
return self.head.data
q = Queue()
print(q.is_empty())
q.enqueue(1)
print('deleted data : {}'.format(q.dequeue()))
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)
while not q.is_empty():
print(q.dequeue())
print (q.is_empty())결과
True
self.is_empty()- new_node : <__main__.Node object at 0x000002611D2373E0>
self.is_empty()- self.head : <__main__.Node object at 0x000002611D2373E0>
self.is_empty()- self.tail : <__main__.Node object at 0x000002611D2373E0>
deleted data : 1
self.is_empty()- new_node : <__main__.Node object at 0x000002611D1FF1A0>
self.is_empty()- self.head : <__main__.Node object at 0x000002611D1FF1A0>
self.is_empty()- self.tail : <__main__.Node object at 0x000002611D1FF1A0>
enqueue() 결과 head.data : 2
enqueue() 결과 tail.data : 3
enqueue() 결과 head.data : 2
enqueue() 결과 tail.data : 4
enqueue() 결과 head.data : 2
enqueue() 결과 tail.data : 5
2
3
4
5
True연결리스트 (linked list) : 데이터를 순서대로 나열한 자료구조. 링크드 리스트는 아래와 같이 세 개의 형태를 가지고 있음. 단방향 연결 리스트는 Data와 Next 가 존재함 양방향 연결리스트는 Prev가 존재하여 자신의 앞 요소를 가리킴. 맨 처음은 Prev 가 존재하지 않으며, Next 가 존재. 맨 마지막은 Prev가 존재하고 Next 가 존재하지 않음.
단방향 링크드 리스트의 단점: 검색할 때 무조건 맨 앞에서부터 시작해야 함. (비효율)
class Node(object):
def __init__ (self, data):
self.data=data
self.next = None
class SLinckedList (object):
def __init__ (self):
self.head = None
def append (self, node):
if self.head == None:
self.head = node
#디버깅용
print('11 node : ',node.data,' self.head.data : ',self.head.data)
else:
cur = self.head
while cur.next != None:
cur = cur.next
cur.next = node
#디버깅
print(' append end node : ',node.data
,'\n self.head : ',self.head.data
,'\n cur.next.data : ', cur.next.data)
#data 값이 위치한 index 번호 return
def getDataIndex (self, data):
cur = data
idx =0
while cur:
if cur.data == data:
return idx
cur = cur.next
idx += 1
return -1
#중간에 값을 삽입할 때
def insertNodeAtIndex (self, idx, node):
curn = self.head
prevn = None
cur_i = 0
if idx == 0:
if self.head:
nextn = self.head
self.head = node
self.head.next = nextn
else:
while cur_i < idx:
if curn :
prevn = curn
curn = curn.next
else :
break
cur_i +=1
if cur_i ==idx:
node.next = curn
prevn.next = node
else:
return -1
#전체 삭제
def clear(self):
self.head = None
def print(self):
curn = self.head
string = ""
while curn:
string += str(curn.data)
if curn.next:
string += "=>"
curn = curn.next
print(string)
#특정 위치값 삭제
def deleteAtIndex(self, index):
curn_i = 0
curn = self.head
prevn = None
nextn = self.head.next
if index == 0:
self.head = nextn
else:
while curn_i < index:
if curn.next:
prevn = curn
curn = nextn
nextn = nextn.next
else:
break
curn_i+=1
if curn_i == index :
prevn.next = nextn
else :
return -1
#실행
sl = SLinckedList()
sl.append(Node(1))
sl.append(Node(2))
sl.append(Node(3))
sl.append(Node(5))
#중간삽입
sl.insertNodeAtIndex(3,Node(4))
sl.print()
#인덱스 찾기
sl.getDataIndex(1)
sl.getDataIndex(4)
sl.getDataIndex(5)
sl.print()
#인덱스로 삭제 (값 아님)
sl.deleteAtIndex(2)
sl.print()