큐

큐

입구와 출구가 따로 있는 선입선출의 특징을 가지고 있는 자료구조

인큐(enQueue)  : 데이터 삽입,  데큐(deQueue)  : 데이터 추출을

데이터 추출시 머리(front) 위치의 데이터가 추출 되고 데이터를 삽입시 꼬리(rear) 바로 다음 위치에 삽입

머리 : 저장된 데이터 중 첫번찌, 꼬리: 저장된 데이터 중 마지막

예) 유명 맛집의 대기줄

큐의 자료구조

큐 생성

front와 rear 모두 -1이면 초기 상태이고 큐가 비었다는 의미로 해석

# 큐 생성
queue = [None, None, None, None, None]
front = rear = -1

 

데이터 삽입

#1 rear를1 증가 시킨 후 #2 rear 위치에 데이터 삽입

#데이터 삽입
queue = [None, None, None, None, None]
front = rear = -1

rear += 1 #1
queue[rear] = '화사' #2
rear += 1
queue[rear] = '솔라'
rear += 1
queue[rear] = '문별'

print('-------큐 상태------')
print('[출구]<--', end = ' ')
for i in range(0, len(queue), 1) :
    print(queue[i], end = ' ')
print('<--[입구]')

-------큐 상태------
[출구]<-- 화사 솔라 문별 None None <--[입구]

 

데이터 추출 

#1 front 1 증가 후 #2 front 위치의 데이터를 밖으로 추출 #3 front 위치의 데이터는 None으로 만들기

#데이터 추출
queue = ['화사', '솔라', '문별', None, None]
front = -1
rear = 2

print('-----큐 상태-----')
print('[출구]<--', end = ' ')
for i in range(0, len(queue), 1) :
    print(queue[i], end = ' ')
print('<--[입구]')
print('-----------------')

front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)

front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)

front += 1
data = queue[front]
queue[front] = None
print('deQueue -->', data)
print('-----------------')

print('-----큐 상태-----')
print('[출구]<--', end = ' ')
for i in range(0, len(queue), 1) :
    print(queue[i], end = ' ')
print('<--[입구]')

-----큐 상태-----
[출구]<-- 화사 솔라 문별 None None <--[입구]
-----------------
deQueue --> 화사
deQueue --> 솔라
deQueue --> 문별
-----------------
-----큐 상태-----
[출구]<-- None None None None None <--[입구]

 

큐 초기화

#큐 초기화
queue = [None, None, None, None, None]

 

사이즈만 바꾸면 되는 큐 초기화

#사이즈만 바꾸면 되는 큐 초기화
SIZE = 5 #큐 크기
queue = [None for _ in range(SIZE)]
front = rear = -1

 

큐가 꽉 찼는지 확인하는 함수

#큐가 꽉 찼는지 확인하는 함수
def isQueueFull() :
    global SIZE, queue, front, rear
    if (rear == SIZE - 1) :
        return True
    else :
        return False

SIZE = 5
queue = ['화사', '솔라', '문별', '휘인', '선미']
front = -1
rear = 4

print('큐가 꽉 찼는지 여부 ==>', isQueueFull())

큐가 꽉 찼는지 여부 ==> True

 

큐에 데이터를 삽입하는 함수

#큐에 데이터를 삽입하는 함수
def isQueueFull() :
    global SIZE, queue, front, rear
    if (rear == SIZE - 1) :
        return True
    else :
        return False

def enQueue(data) :
    global SIZE, queue, front, rear
    if(isQueueFull()) :
        print('큐가 꽉 찼습니다.')
        return
    rear += 1
    queue[rear] = data

SIZE = 5
queue = ['화사', '솔라', '문별', '휘인', None]
front = -1
rear = 3

print(queue)
enQueue('선미')
print(queue)
enQueue('재남')

['화사', '솔라', '문별', '휘인', None]
['화사', '솔라', '문별', '휘인', '선미']
큐가 꽉 찼습니다.

 

큐가 비었는지 확인 하는 함수

#큐가 비었는지 확인하는 함수
def isQueueEmpty() :
    global SIZE, queue, front, rear
    if (front == rear) :
        return True
    else :
        return False

SIZE = 5
queue = [None for _ in range(SIZE)]
front = rear = -1

print('큐가 비었는지 여부 ==>', isQueueEmpty())

큐가 비었는지 여부 ==> True

 

큐에서 데이터를 추출하는 함수

#큐에서 데이터를 추출하는 함수
def isQueueEmpty() :
    global SIZE, queue, front, rear
    if (front == rear) :
        return True
    else :
        return False

def deQueue() :
    global SIZE, queue, front, rear
    if (isQueueEmpty()) :
        print('큐가 비었습니다.')
        return None
    front += 1
    data = queue[front]
    queue[front] = None
    return data

SIZE = 5
queue = ['화사', None, None, None, None]
front = -1
rear = 0
print(queue)
retData = deQueue()
print('추출한 데이터 -->', retData)
print(queue)
retData = deQueue()

['화사', None, None, None, None]
추출한 데이터 --> 화사
[None, None, None, None, None]
큐가 비었습니다.

 

데이터 확인

#큐에서 front+1의 위치의 데이터를 확인하는 함수
def isQueueEmpty() :
    global SIZE, queue, front, rear
    if (front == rear) :
        return True
    else :
        return False

def peek() :
    global SIZE, queue, front, rear
    if (isQueueEmpty()) :
        print('큐가 비었습니다.')
        return None
    return queue[front + 1]
SIZE = 5 
queue = ['화사', '솔라', '문별', None, None]
front = -1
rear = 2

print(queue)
retData = peek()
print('다음에 추출될 데이터 확인 -->', retData)
print(queue)

['화사', '솔라', '문별', None, None]
다음에 추출될 데이터 확인 --> 화사
['화사', '솔라', '문별', None, None]