큐란?
- 큐는 선입선출의 특성을 가지는 자료구조이다.
- front와 rear(또는 back)을 가지고 있으며 각각 맨앞, 맨뒤를 나타낸다.
- 값 추가 push(enqueue), 값 삭제 pop(dequeue), 값 확인 peek이 존재한다.
그래서 큐는 무엇이고?
큐 잡다, 큐 돌려라 이런 말 들어보거나 해본적 있을 것이다. 큐는 직역하면 기다리는 줄, 대기열이다. 대기열은 먼저 들어온 사람이 먼저 빠져나간다. 누가 내 앞을 새치기 하려하면 놔둘리 없다. 당연히 큐 중간에 무언가 끼어들지 못하고, 맨 뒤에서 줄을 이어서거나 맨 앞의 사람이 빠지기를 기다려야 한다. 큐는 이처럼 선입 선출의 특성을 가지고 있다.
구현
파이썬의 클래스를 통해 구현해 줄 것이다. 스택이라는 클래스는 __init__과 push,pop,peek 이 3개의 함수로 구현해줄 것이다.
1. __init__
__init__은 해당 클래스가 기본적으로 가지고 있는 값을 설정해준다고 생각하면 된다.
크기가 정해진 배열을 통해서 스택을 구현할 것이다. 그러므로 그 크기를 전달받아야 하고, 그 크기만큼의 크기를 갖는 배열, 맨 앞의 값을 표시하는 front, 맨 뒤의 값을 표시하는 rear이 필요하다.
front + 1 에는 항상 맨 앞의 값이 존재하고 rear+1에는 항상 맨 뒤의 값이 존재한다.
def __init__(self,maxsize):
self.maxsize=maxsize # 최대 크기 저장
# 스택의 경우 스택 맨 위에서 값의 삽입과 삭제가 모두 일어났으므로 그 위치만 표시해주면 된다.
# 그러나 큐의 경우 앞에서는 값의 삭제 뒤에서는 값의 삽입이 일어나므로 맨 앞과 맨 뒤 이렇게 두 곳을 나타내야 한다.
self.front=-1 # 맨 앞을 나타내는 변수 , 해당 위치에서 값의 삭제가 이루어진다.
self.rear=-1 # 맨 뒤를 나타내는 변수 , 해당 위치에서는 값의 삽입이 이루어진다.
# 큐에서는 front와 rear 모두 값의 증가만 이루어진다. 맨 뒤에서 값의 삭제와 맨 앞에서의 값의 삽입이 이루어지지 않으므로,
self.arr=[0]*self.maxsize # 값을 저장해줄 배열2. ENQUEUE
큐에 값의 삽입이 이루어질 때 rear의 값이 증가한다.
맨 앞 (front)에서는 값의 삭제 rear에서는 값의 삽입이 이루어진다.
지금 들어있는 값들의 개수는 rear에서 front를 뺀 값의 개수와 같다.
최대 크기보다 크면 값의 삽입이 불가능해야 한다. rear - front를 이용해 비교해주면 된다.
def ENQUEUE(self,num): # 값을 전달받아 큐에 값을 삽입하는 함수
# 큐에 값의 삽입이 이루어질 때 rear의 값이 증가한다.
# 맨 앞 (front)에서는 값의 삭제 rear에서는 값의 삽입이 이루어진다.
# 최대 크기보다 크면 값의 삽입이 불가능해야 한다. 큐의 크기는 rear - front를 통해 알 수 있다.
if self.rear-self.front==self.maxsize:
print('큐가 가득 찼습니다')
else:
self.rear+=1 # 위치의 이동이 먼저 이루어지고 값이 저장된다. 이렇게 하면 rear는 항상 값이 맨 뒤의 값을 가르키게 된다.
self.arr[self.rear]=num # 전달받은 값 저장3. DEQUEUE
큐에 값의 삭제가 이루어질때 front의 값이 증가한다.
front는 항상 맨 앞의 값의 위치 - 1 의 값을 갖는다.
만약 rear의 값과 front의 값이 같다면 큐는 비어있다.
def DEQUEUE(self): # 맨 앞의 값을 삭제하고 그 값을 반환해주는 함수
# 큐에 값의 삭제가 이루어질때 front의 값이 증가한다.
# front는 항상 맨 앞의 값의 위치 - 1 의 값을 갖는다.
# 만약 rear과 front의 값이 같은 경우 큐의 크기는 0, 즉 큐가 비어있다
if self.rear-self.front==0:
print('큐가 비어있습니다')
else:
self.front+=1 # 위치의 이동이 먼저 이루어진다. 이동한 위치에는 큐의 맨 앞의 값이 존재한다.
return self.arr[self.front]4. PEEK
DEQUEUE와 똑같다. 다만 front 값의 증가 없이 front+1의 위치의 인덱스를 반환해준다.
def PEEK(self): # 큐의 맨 앞의 값을 반환, 값의 삭제는 이루어지지 않는다.
if self.rear-self.front==0: # 큐가 비어있다면 맨 앞의 값도 존재하지 않는다
print('큐가 비어있습니다')
else:
return self.arr[self.front+1] # 앞서 설명하였듯이 self.front는 항상 맨 앞의 값 위치 - 1의 값을 가진다. 따라서 +1한 값은 맨 앞의 값
코드의 실행 예시를 들어보겠다. 큐의 크기는 4이다.
맨 처음 형태는 다음과 같다. front와 rear은 실제로는 -1의 값을 갖고 있지만 지금 배열에는 나타낼 수 없다고 가정하였다.
| 큐 배열 | 0 | 0 | 0 | 0 |
| front,rear |
큐에 ENQUEUE(2)를 해주는 경우
| 큐 배열 | 0 | 0 | 0 | 0 |
| front | rear |
rear이 +=1 된다.
| 큐 배열 | 2 | 0 | 0 | 0 |
| front | rear |
배열의 rear 인덱스의 값을 2로 갱신해준다.
계속해서 3을 넣었다고 가정해보자. rear+=1이므로
| 큐 배열 | 2 | 0 | 0 | 0 |
| front | rear |
값의 갱신
| 큐 배열 | 2 | 3 | 0 | 0 |
| front | rear |
여기서 DEQUEUE를 해보겠다.
front는 +=1이 되고,
| 큐 배열 | 2 | 3 | 0 | 0 |
| front | rear |
배열의 front 인덱스의 값을 반환해준다.
여기서 여러가지를 알 수 있다.
일단 ENQUEUE와 DEQUEUE연산 모두 공통적인 특성을 가지고 있다. 각 함수를 실행시키면 front 또는 rear이 오른쪽으로 이동한다.
그리고 front번째 인덱스가 가르키는 값은 맨 앞의 값이였던 값이고 사라지게 되므로 front+1번째 인덱스의 값이 큐의 맨 앞의 값이 된다. DEQUEUE연산은 삭제시키는 연산이므로 2라는 값은 사라지게 되지만 배열에서의 값에 변화는 주지 않았다. 모두 오른쪽으로 이동하므로 왼쪽의 값을 참조할 일은 없다.
지금 이 상태에서 한번더 DEQUEUE 연산을 할 경우 다음과 같다.
| 큐 배열 | 2 | 3 | 0 | 0 |
| front,rear |
front와 rear이 같은 위치에 있는 경우 값은 0이다. 이 상태에서 DEQUEUE를 하게 되면 앞서 설정해둔 것 처럼 빈 큐임을 알리는 메시지가 뜨게 된다.
값을 계속 추가하고 삭제하여서 front와 rear이 끝에 도달하였다고 가정해보자.
| 큐 배열 | 2 | 3 | 1 | 2 |
| front,rear |
해당 큐에 들어간 원소의 개수는 0개이고 아직 4개를 채울 수 있어야 한다.
그런데 여기서 ENQUEUE(8)를 하게 되면 어떻게 될까?
rear은 이미 배열의 마지막 인덱스를 가르키고 있다. 여기서 rear에 1을 더해준다면 INDEX_ERROR이 발생할 것이다.
다음은 예시 코드이다.
queue=QUEUE(5)
for i in range(6):
print('큐에 넣으려는 값',i)
queue.ENQUEUE(i)
print('현재 큐 :',end=' ')
queue.SHOW()
print('큐의 맨 앞에 존재하는 값 :',queue.PEEK())
print('현재 큐 :',end=' ')
queue.SHOW()
for i in range(6):
frontvalue=queue.DEQUEUE()
print('큐의 맨 앞에 있던 값',frontvalue)
print('현재 큐 :',end=' ')
queue.SHOW()
# 해당 부분에서 문제가 발생한다.
print('큐에 넣으려는 값',10)
queue.ENQUEUE(10)위에 구현한 큐는 '선형 큐' 이고 선형 큐가 갖는 문제점이다.
큐는 비어있지만 이미 front와 rear의 값은 끝에 도달해있다. 이 상태에서 큐에 값을 삽입하려 하면 rear의 값이 배열 밖으로 벗어나게 되서 에러가 발생한다.
큐를 채워넣은 크기 (rear-front)는 최대 크기(maxsize)보다 작지만 값의 삽입이 불가능해졌다.
이를 해결하기 위해서 원형 큐를 이용하면 된다.
그럼 원형 큐를 어떻게 간단하게 구현할 수 있을 까?
진짜 간단하다. front와 rear을 최대 크기로 나눠주고 그 나머지를 이용하면 된다.
그럼 크기가 4인 배열을 기준으로 rear의 값은 다음과 같이 변화한다. 0 -> 1 -> 2 -> 3 -> 0 -> 1 -> 2 -> 3 - > 0
아까 그 상황에서 원형 큐의 경우 다음과 같이 작동하게 된다.
| 큐 배열 | 2 | 3 | 1 | 2 | 배열 밖 |
| rear%maxsize | front | rear |
maxsize의 경우 맨 처음에 전달한 배열의 크기이다. rear의 값을 계속 증가시켜도 나머지로 작동하게 되므로 rear은 배열 범위 밖의 인덱스를 가르키지만 rear%maxsize의 경우 맨 처음의 값을 가르킨다. front도 마찬가지로 작동시킬 수 있다.
이렇게 하면 계속 순환하면서 값을 갱신시킬 수 있다.
구현한 코드는 다음과 같다.
선형 큐
class QUEUE:
def __init__(self,maxsize):
self.maxsize=maxsize # 최대 크기 저장
# 스택의 경우 스택 맨 위에서 값의 삽입과 삭제가 모두 일어났으므로 그 위치만 표시해주면 된다.
# 그러나 큐의 경우 앞에서는 값의 삭제 뒤에서는 값의 삽입이 일어나므로 맨 앞과 맨 뒤 이렇게 두 곳을 나타내야 한다.
self.front=-1 # 맨 앞을 나타내는 변수 , 해당 위치에서 값의 삭제가 이루어진다.
self.rear=-1 # 맨 뒤를 나타내는 변수 , 해당 위치에서는 값의 삽입이 이루어진다.
# 큐에서는 front와 rear 모두 값의 증가만 이루어진다. 맨 뒤에서 값의 삭제와 맨 앞에서의 값의 삽입이 이루어지지 않으므로,
self.arr=[0]*self.maxsize # 값을 저장해줄 배열
def ENQUEUE(self,num): # 값을 전달받아 큐에 값을 삽입하는 함수
# 큐에 값의 삽입이 이루어질 때 rear의 값이 증가한다.
# 맨 앞 (front)에서는 값의 삭제 rear에서는 값의 삽입이 이루어진다.
# 최대 크기보다 크면 값의 삽입이 불가능해야 한다. 큐의 크기는 rear - front를 통해 알 수 있다.
if self.rear-self.front==self.maxsize:
print('큐가 가득 찼습니다')
else:
self.rear+=1 # 위치의 이동이 먼저 이루어지고 값이 저장된다. 이렇게 하면 rear는 항상 값이 맨 뒤의 값을 가르키게 된다.
self.arr[self.rear]=num # 전달받은 값 저장
def DEQUEUE(self): # 맨 앞의 값을 삭제하고 그 값을 반환해주는 함수
# 큐에 값의 삭제가 이루어질때 front의 값이 증가한다.
# front는 항상 맨 앞의 값의 위치 - 1 의 값을 갖는다.
# 만약 rear과 front의 값이 같은 경우 큐의 크기는 0, 즉 큐가 비어있다
if self.rear-self.front==0:
print('큐가 비어있습니다')
else:
self.front+=1 # 위치의 이동이 먼저 이루어진다. 이동한 위치에는 큐의 맨 앞의 값이 존재한다.
return self.arr[self.front]
def PEEK(self): # 큐의 맨 앞의 값을 반환, 값의 삭제는 이루어지지 않는다.
if self.rear-self.front==0: # 큐가 비어있다면 맨 앞의 값도 존재하지 않는다
print('큐가 비어있습니다')
else:
return self.arr[self.front+1] # 앞서 설명하였듯이 self.front는 항상 맨 앞의 값 위치 - 1의 값을 가진다. 따라서 +1한 값은 맨 앞의 값
def SHOW(self): # 큐에 들어있는 원소를 앞에서부터 출력해주는 코드
for i in range(self.front+1,self.rear+1): # self.front는 맨앞의 값 위치 - 1이므로 맨 앞에서 부터 출력해주기 위해서 +1
# self.rear는 맨뒤의 값 위치, 그 위치까지 출력하기 위해서는 +1을 해줘야 하므로 +1 해주었다.
print(self.arr[i],end=' ')
print()원형 큐
class CIRCULAR_QUEUE:
# 원형 큐
# 원형 큐에서는 만약 front가 이동하여 앞에는 빈 공간이 생기고 rear은 맨 끝에 도달한 상태에서 값의 추가가 일어나면 rear을 다시 맨 처음으로 돌려보낸다.
# 선형 큐와 달리 이미 지나간 공간을 다시 활용할 수 있다.
# 간단하게 %(나머지)를 이용해 구현 가능하다. 배열의 크기로 나눈 나머지는 최대크기를 이상의 값을 가질수 없다.
# rear과 front의 값을 최대크기의 값으로 나눠주면 최대 크기의 값이 m이라 했을 때 다음과 증가한다.
# rear의 값 기준 : m-2 -> m-1 -> 0 -> 1 ... -> m-2 -> m-1 -> 0 -> 1 ... (무한 반복)
def __init__(self,maxsize):
self.maxsize=maxsize # 최대 크기 저장
# 스택의 경우 스택 맨 위에서 값의 삽입과 삭제가 모두 일어났으므로 그 위치만 표시해주면 된다.
# 그러나 큐의 경우 앞에서는 값의 삭제 뒤에서는 값의 삽입이 일어나므로 맨 앞과 맨 뒤 이렇게 두 곳을 나타내야 한다.
self.front=-1 # 맨 앞을 나타내는 변수 , 해당 위치에서 값의 삭제가 이루어진다.
self.rear=-1 # 맨 뒤를 나타내는 변수 , 해당 위치에서는 값의 삽입이 이루어진다.
# 큐에서는 front와 rear 모두 값의 증가만 이루어진다. 맨 뒤에서 값의 삭제와 맨 앞에서의 값의 삽입이 이루어지지 않으므로,
self.arr=[0]*self.maxsize # 값을 저장해줄 배열
def ENQUEUE(self,num): # 값을 전달받아 큐에 값을 삽입하는 함수
# 큐에 값의 삽입이 이루어질 때 rear의 값이 증가한다.
# 맨 앞 (front)에서는 값의 삭제 rear에서는 값의 삽입이 이루어진다.
# 최대 크기보다 크면 값의 삽입이 불가능해야 한다. 큐의 크기는 rear - front를 통해 알 수 있다.
if self.rear-self.front==self.maxsize:
print('큐가 가득 찼습니다')
else:
self.rear+=1 # 위치의 이동이 먼저 이루어지고 값이 저장된다. 이렇게 하면 rear는 항상 값이 맨 뒤의 값을 가르키게 된다.
self.arr[self.rear%self.maxsize]=num # 전달받은 값 저장
def DEQUEUE(self): # 맨 앞의 값을 삭제하고 그 값을 반환해주는 함수
# 큐에 값의 삭제가 이루어질때 front의 값이 증가한다.
# front는 항상 맨 앞의 값의 위치 - 1 의 값을 갖는다.
# 만약 rear과 front의 값이 같은 경우 큐의 크기는 0, 즉 큐가 비어있다
if self.rear-self.front==0:
print('큐가 비어있습니다')
else:
self.front+=1 # 위치의 이동이 먼저 이루어진다. 이동한 위치에는 큐의 맨 앞의 값이 존재한다.
return self.arr[self.front%self.maxsize]
def PEEK(self): # 큐의 맨 앞의 값을 반환, 값의 삭제는 이루어지지 않는다.
if self.rear-self.front==0: # 큐가 비어있다면 맨 앞의 값도 존재하지 않는다
print('큐가 비어있습니다')
else:
return self.arr[(self.front+1)%self.maxsize] # 앞서 설명하였듯이 self.front는 항상 맨 앞의 값 위치 - 1의 값을 가진다. 따라서 +1한 값은 맨 앞의 값
def SHOW(self): # 큐에 들어있는 원소를 앞에서부터 출력해주는 코드
for i in range(self.front+1,self.rear+1): # self.front는 맨앞의 값 위치 - 1이므로 맨 앞에서 부터 출력해주기 위해서 +1
# self.rear는 맨뒤의 값 위치, 그 위치까지 출력하기 위해서는 +1을 해줘야 하므로 +1 해주었다.
print(self.arr[i%self.maxsize],end=' ')
print()'프로그래밍 > 자료구조' 카테고리의 다른 글
| [PYTHON] 배열을 통해 구현한 스택 (0) | 2022.01.29 |
|---|