[자료구조] Queue 큐-설명과 Python 구현하기

1. 큐(Queue) 란? 

 큐는 스택, 연결 리스트 등 자료 구조중 하나입니다. 먼저 들어간 요소가 먼저 나오는 스택의 FILO(First In Last Out) 구조와 다르게 큐는 공항 검색대와 같이 먼저 들어간 순서대로 요소들이 처리되는 FIFO(First In First Out) 자료구조입니다. 큐는 특히 BFS 알고리즘의 구현에서 많이 사용됩니다. 

 

2. 큐의 연산

• pop()                              <-큐의 가장 첫번째 요소를 제가합니다.

• push(Element)                  <-큐의 뒤에 새로운 요소를 추가합니다.

• front()                             <-큐의 첫번째 요소를 반환합니다. 

• back()                             <-큐의 마지막 요소를 반환합니다. 

큐를 그림으로 표현해 보겠습니다. 

  큐에서 pop 명령을 수행하면 가장 앞의 1 원소가 지워졌고, push 명령을 수행했을 때는 가장 뒤에 5라는 원소가 추가되었습니다. 큐의 동작과정은 줄서기에 비유할 수 있습니다. 줄의 앞(front)에 있는 원소들이 먼저 처리된 후, 뒤의 원소들이 처리되게 됩니다. 

 

3. 큐의 구현(Python)

 큐는 배열로 구현할 수 있으나 큰 차이가 있습니다. 바로 큐의 중간에 있는 값을 수정하거나 접근할수도 없다는 것입니다. 큐에서는 오직 첫번째와 마지만 원소, 그리고 큐의 전체 길이 만을 알 수 있습니다. 큐의 중간값을 확인하기 위해서는 큐를 연속적으로 pop 해야 합니다. 

 

class Queue:
    def __init__(self):
        self.arr=[]
    def push(self,a):
        self.arr.append(a)
    def pop(self):
        del self.arr[0]
    def size(self):
        return len(self.arr)
    def top(self):
        return self.arr[-1]
    def siz(self):  #size는 다른 함수로 이미 사용되고 있기 때문에 사용 불가...
        return len(self.arr)

 

파이썬으로 큐를 구현한 코드입니다.