스택, 큐

스택구현하기 (LIFO)

 

 

---

Queue

큐 구현해보기

 

테스트코드

def test_node():
# 노드가 제대로 되는 것인지 확인을 하기 위한 코드
# Node 객체에 item 1을 넣고 다음을 가리키는 것은 없다.
# 해당 값의 item이 넣은 것과 같냐 라고 test한다.
    assert Node(1, None).item == 1, "아이템 값을 바꾸면 ERROR!"

def test_queue():
    queue = Queue()
    queue.push(1)
    queue.push(2)
    queue.push(3)

    queue.pop() == 1
    queue.pop() == 2
    queue.pop() == 3
    queue.is_empty()

큐의 공간을 왔다갔다 하는 Node가 있어야 한다. Node는 value와 다음을 가리키는 포인터(next)를 갖고 있다.

Node를 테스트 하기 위해 Node에 value로 1을 넣고 다음은 없다고 하여 생성한 후 넣은 값이 1이 맞는지 확인한다.

assert는 파이썬에서 하나의 예외처리이다. 해당 값이 맞으면 넘어가고 그렇지 않으면 ,(컴마) 다음의 에러메세지를 보여준다.

 

Node의 테스트가 완료되었다면 본격적으로 Queue를 만들어 해당 객체가 갖고 있는 함수를 사용해본다.

내가 구현한 Queue의 함수는 push, pop, is_empty 3가지가 있다.

queue를 생성한 후 해당 메소드를 모두 실행해 주는 코드를 작성한다.

queue의 특성에 맞게 FIFO 에 맞는 코드를 작성한다.

 

---

큐 구현하기

class Node:
    def __init__(self, item, next):
#Node는 넣고자 하는 데이터(item), 다음을 가리키는 포인터 next를 받는다.
        self.item = item
        self.next = next

class Queue:
    def __init__(self):
        self.front = None

    def push(self, value):
        # push는 넣고자 하는 value를 받아야한다.
        if not self.front:
            self.front = Node(value, None)
            return

        #현재 포인터가 가리키고 있는 부분을 갖고온다.
        node = self.front
        while node.next:
            node = node.next
            # 해당 코드는 가장 최근에 들어온 데이터의 노드를 가리킨다.
        node.next = Node(value, None)
        # 현재 node의 포인터 다음으로 value를 넣으면서 노드를 생성한다.
        # 다음을 가리키는 노드는 존재하지 않기에 None으로 설정한다.

    def pop(self):
        #꺼내고자 하는 값이 없으면 None 리턴
        if not self.front:
            return None
        #현재 front가 이는 노드를 받아온다.
        node = self.front
        # 포인터를 현재 다음을 가리키도록 바꿔준다.
        self.front = self.front.next
        return node.item # 이전에 가리키던 포이넡의 value를 return 한다.

    def is_empty(self):
        return self.front is None