[python] Data Structure Linear Queue 자료구조 선형 큐

 

dbguswls030/Argorithm

---

큐의 예

스택이 나중에 들어온 데이터가 먼저 쓰이는 후입선출 구조 형태의 자료구조였다면, 큐는 먼저 들어온 데이터가 먼저 쓰이는 선입선출 구조 형태의 자료구조이다. 실생활에서의 예로는 은행에서 서비스를 기다리는 손님들의 길게 늘어진 줄로 이해할 수 있다. 먼저 번호표를 뽑고 줄을 서게 되면 줄에 가장 먼저 와서 기다린 손님부터 업무를 처리하는 방식이다.

 

---

다음은 선형 큐를 구현에 쓰인 요소들이다.

 

init() : 큐를 초기화하는 메소드

is_empty() : 큐가 비어있는지 여부를 확인

enqueue(x) : x를 큐에 삽입

dequeue() : 큐에서 rear에 위치한 요소 삭제 후 반환

size() : 큐의 모든 요수 개수를 반환

peek() : 큐에서 rear에 위치한 요소 삭제하지 않고 반환

 

큐는 보통 front와 rear로 삽입 삭제 인덱스를 구현하는데 파이썬의 리스트 특성상 front가 굳이 필요하지 않기 때문에 사용하지 않음

---

def enqueue(x):
    global rear
    rear+=1
    queue.insert(rear,x)

def dequeue():
    global rear
    if is_empty()==False:
        rear-=1
        return queue.pop(0)
    else:
        print("queue is empty")

def peek():
    return queue[0]

def size():
    return len(queue)

def is_empty():
    if rear == -1:
        return True
    else:
        return False

def init():
    global rear

    rear = -1
    queue.clear()


rear = -1
queue=[]

init()
enqueue(1)
print(queue)
enqueue(4)
print(queue)
print(dequeue())
print(queue)
print(peek())
enqueue(5)
print(queue)
print(peek())
print(size())
init()
print(queue)