[파이썬] 0328 수업 아카이빙 : 자료구조 (stack, queue)

스택(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()