[자료구조,Python] 파이썬으로 만들어보는 큐 Queue

Queue

Queue의 자료구조에서 핵심은 First in First Out 입니다. 즉 제일 먼저 들어온 데이터블록이 제일 처음에 나갑니다.

이번 실과 빨간색 데이터 블록에서는 매듭이 없습니다. 그리고 진행 방향만 존재하죠. 이 그림처럼 말이죠. 이 그림을 보면 빨간색 데이터는 한 방향으로만 들어오고 나갈 수 있습니다. 마치 톨게이트를 지나가는 자동차들 처럼요. 그래서 제일 먼져 들어온 빨간색 데이터블록이 제일 먼져 나가게 됩니다.

우리는 이와같은 현상을 First in First Out 이라고 이야기합니다.

그리고 이것은 Queue의 모든 것 입니다.

Queue는 대표적인 2가지 메소드가 있습니다. 각각 enqueue 와 dequeue 라고 부릅니다.

enqueue 와 dequeue

1. enqueue

enqueue 는 큐 자료구조에 데이터를 추가하는 과정의 메소드이다. singly_linked_list 의 append , Stack 의 push 처럼 데이터를 추가하지만 enqueue의 특징은 First in First out을 하기위해서 제일 최근에 들어간 노드 뒤에 추가한다. 즉 제일 처음에는 처음 데이터 값을 가르키는 front 에 추가하지만, 그 후 데이터는 제일 마즈막에 있는 데이터 rear 뒤에 추가된다.

enqueue method

def enqueue(self,data):
    new_node = Node(data)
    self.size += 1
    if self.front == None:
        self.front = new_node
    else:
        self.rear.set_prev(new_node)
    self.rear = new_node

코드 설명

method의 시그니처는 아래와 같다.

1. 메소드 이름 - enqueue
2. 파라미터 - data
3. 리턴타입 - Node

데이터의 값이 증가하기 때문에 size의 크기를 올리고, 제일 첫 데이터를 가리키는 fron의 값이 none이면 아무런 데이터도 갖고있지 않는다는 뜻이므로 새로들어온 data를 참조하게 하였다.
만약 다른경우에는 제일 끝에 데이터를 가리키는 rear 의 prev에 새로들어온 데이터를 추가시키고, rear가 그 데이터 노드를 가리키게 설계했다.

1. dequeue

dequeue는 큐자료구조에서 데이터를 제거하는 과정의 메소드 이다. Singly_linked_list 의 delete_at , Stack 의 pop처럼 데이터를 제거하지만 dequeue의 특징은 First in First out을 하기위해서 제일 처음에 들어간 데이터부터 제거한다.. 즉 제일 처음에는 처음 데이터 값을 가르키는 front 값을 계속 제거하는 과정이다. dequeue method

def dequeue(self):
    front_node = self.front
    if front_node == None:
        return front_node
    elif self.size == 1:
        self.size -= 1
        self.rear = None
        front_node = None
        return front_node
    else:

        self.size -= 1
        self.front = front_node.get_prev()
        return front_node
        

코드 설명

method의 시그니처는 아래와 같다.

1. 메소드 이름 - dequeue
2. 파라미터 - 없음
3. 리턴타입 - Node

dequeue가 갖을 수 있는 경우의 수는 총 3가지이다.

• 노드가 비어있는 경우
  if문을 통하여 노드가 비어있는지 확인한 후 None 값을 리턴하게 설계하였다.
  
• 노드에 데이터가 1개만 있을경우
  front와 rear가 가르키고 있는 데이터 노드가 동일함으로 사이즈를 감소시키고 reaer와 front 값을 초기화 시키게 설계하였다.
  
• 노드에 데이터가 여려개 있을 경우
  데이터가 감소함으로 사이즈를 감소시키고, front가 가르키는 값을 front 의 prev에 있는 값으로 지정한 front객체의 값을 front의 prev가 가르키는 데이터로 지정해주고 리턴값은 현재 front가 있는 값을 return 했다. 이유는 추후에 이 메소드를 작동시켰을 때 dequeue된 데이터의 이름을 출력하기 위해서 self.front의 값이 아닌 front_node의 값을 리턴하였다.