Queue

큐(Queue)

- 선형큐

- 원형큐

- 연결큐

- 우선순위큐

 

기본적으로 앞부분은 개념 설명을 진행합니다.
초반부는 개념부분이라 상관없지만
C나 java쓰시는 분들은 linked list를 쓰는데
여기선 python이라 쓰지 않습니다
대략적인 개념만 이해하고 (빠르게 쭉 읽자.)
실전 개념으로 넘어가면 됩니다

삼성역량평가 기준으로 A, A+은 python으로는 덱 쓰면 됩니다.

• 삽입, 삭제의 위치가 제한적인 자료구조
  • 큐 뒤: 삽입 / 큐 앞: 삭제(꺼내쓴거다.)
• 선입선출구조(FIFO: First in First Out)
  • 큐에 삽입한 순서대로 원소가 저장
  • 가장 먼저 삽입(First In)된 원소는 가장 먼저 삭제(First Out)됨
  • 후입선출인 stack과 비교된다고 할 수 있다.
• 예: 맛집가면 줄선 순서대로 입장한다.

 

---

 

 

화살표 방향으로만 자료가 움직인다.

​      ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

<=                                                                <=

     ​ ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

• 저장된 원소 중 첫 번째 원소 있는 왼쪽이 front(머리)
  • 꺼내쓰는 쪽
• 저장된 원소 중 마지막 번쨰 원소 있는 오른 쪽이 rear(꼬리)
  • 저장하는쪽

이 때 front, rear은 index값을 나타낸다.

 

---

 

연산 과정

front와 rear인 2개의 인덱스를 사용한다.

front - 꺼내진 위치
rear - 저장한 위치

긴 원통에서 왼쪽 부터 쌓인다고 생각하자.
값을 빼도 옆으로 이동하지 않고 그 자리(지정된인덱스)에 고정되어있다.
앞에꺼 빼면 앞으로 밀린다고 생각하지말자.

처음에 둘다 자료가 없는 상태면 front와 rear값이 -1로 최기화 된다. (-1이면 자료가 나가는 곳에 붙어있고 실제 공간안에 존재하지 않음.)

 

 

 

삽입

원소 A를 삽입하면 가장 왼쪽에 있는 인덱스[0]에 들어가고 rear 값만 0으로 변한다.(rear가 오른쪽으로 한칸 이동)
그 후 원소 B를 삽입하면 왼쪽인 인덱스[1]에 들어가고 rear 값이 1으로 변한다

삽입의 경우 front는 고정이고 rear만 바뀐다.
rear는 마지막 저장한 자리를 가르킨다.

 

 

 

삭제

가장먼저 삽인된 원소가 삭제된다.(가장 왼쪽)
원소 A가 삭제되고 front 값이 0이된다.
그 후에 원소 C를 삽입하면 B에서 1이었던 rear값은 2가 된다.

세번의 삽입과 세번의 삭제가 이루어 지면 큐는 비어 있고 front와 rear값이 둘다 2로 같아진다.

즉, front와 rear이 같으면 큐는 비어있다고 할 수 있다.

 

 

 

참고)

삽입 : enQueue

삭제 : deQueue

creareQueue() - 공백상태의 큐를 생성

isEmpty() - 공백상태인지 확인

isFull() - 포화상태인지 확인

Qpeek() - 큐의 앞쪽(front)에서 원소를 삭제 없이 반환(그냥 읽어오는거다.)

위는 그냥 함수이름을 저렇게 지정한거지 저런 라이브러는 없다.

 

---

 

Queue의 종류

• 선형 큐
• 원형 큐
• 연결 큐

셋을 응용한 것이 우선순위 큐.

 

 

선형 큐

1차원 리스트를 이용.

• 큐의 크기 = 리스트의 크기
• 추가로 필요한 자료구조
  • front: 저장된 첫 번째 원소의 인덱스(마지막으로 꺼낸자리)
  • rear: 저장된 마지막 원소의 인덱스(마지막으로 저장된 자리)
• 상태 표현(3가지)
  • 초기 상태 : front = rear = -1 (비어있어서 저장된 원소가 없음)
  • 공백 상태 : front = rear (연산 진행중의 공백상태)
  • 포화 상태 : rear = n-1 (n: 리스트의 크기, n-1: 리스트의 마지막 자리 인덱스)
    • rear값이 큐의 마지막 위치 값이 되어있는 경우 큐가 가득차있음
    • 포화 상태가 된 상태에서 데이터를 추가로 넣어야 될 상황이 벌어 졌다면... Queue를 작게 만들었을꺼다.. 즉, 문제 풀때 포화 상태가 될 일은 없다.

 

 

구현

크기정해놓고 하는게 속도가 굉장히 빨라진다. C하는걸 대비해서도 공부해 놓으면 좋다. 파이썬은 크기조정이 자동으로 된다.

• 우선 초기 공백큐 생성

  • 크기 n인 1차원 리스트 생성
  • front, rear = -1 로 초기화

  enQueue() -큐에 아이템 삽입

  • 마지막 원소 뒤에 새로운 원소를 삽입하기 위해서는
    • rear 값을 하나 증가시켜 새로운 원소를 삽입할 자리를 마련함
    • 그 인덱스에 해당하는 리스트 원소 Q[rear]에 item을 저장

def enQueue(item):
    global rear
    if isFull():             #####
        print("Queue_Full")    #####
    else:
        rear +=1
        Q[rear] = item

 

 

rear를 하나 증가 시키고 그자리에 저장.

rear 값이 list의 크기와 같은 상태인 큐가 가득 찬 상태에서는 더이상 원소를 삽입 할 수 없기 때문에 큐가 가득차있음을 알려주아야 한다.

 

 

deQueue() - 큐에서 아이템을 삭제

• 가장 앞에 있는 원소를 삭제하기 위해
  • front 값을 하나 증가시켜 큐에 남아있는 첫 번째 원소로 이동함
  • 새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능을 함

def deQueue(item):
    global rear
    if isEmpty():             #####
        print("Queue_Empty")    #####
    else:
        rear +=1
        return Q[front]

큐가 비어있는 경우 더이상 원소를 삭제 할 수 없기 때문에 큐가 비어있음을 알려주어야 한다.

 

 

isEmpty(), isFull()

• 큐에서 삽입과 삭제를 하기 위해서는 큐가 가득 차있거나 비어있는 상태 확인 필요.\
  • 공백상태 : front = rear
  • 포화상태 : rear = n-1 (n : 리스트의 크기, n-1 : 리스트의 마지막 인덱스)

def isEmpty():
    return front == rear
def isFull():
    return rear == len(Q)-1

공백상태이면 True 반환
rear 값이 리스트의 마지막 인덱스 값이 되면 큐가 포화 상태가 되므로 True 반환

 

 

Qpeek()

• 가장 앞에 있는 원소를 검색하여 확인
• 현재 front의 한자리 뒤(front+1)에 있는 원소, 즉 큐의 첫 번쨰에 있는 원소를 반환

def Qpeek():
    if isEmpty() : 
        print("Queue_Empty")
    else:
        return Q[front+1]

큐가 비어있는지 확인하고 비어있으면 비어있다고 말해주면된다.
주의 할 점은 front 값이 변경되지 않아야 한다.

---

 

 

python 선형 큐 구현

def enq(n):
    global rear
    if rear == len(q)-1:
        print('Full')
    else:
        rear += 1
        q[rear] = n

q = [0]*3
front = -1
rear = -1

# 실제 문제 풀때
rear += 1 #enq(1)
q[rear] = 1
rear += 1 #enq(2)
q[rear] = 2
rear += 1 #enq(3)
q[rear] = 3


front +=1
print(q[front])
front +=1
print(q[front])
front +=1
print(q[front])

#while front!=rear:
#    front +=1
#    print(q[front])

파이썬은 이런식으로 접근하면 된다. 좀더 쉽게 가려면 아래 처럼 구현하면된다.

# 이렇게 간단하게도 가능. 리스트의 크기가 자동변경되는 방법이라 속도 고려하면 위쪽 방법 쓰자.
Q = []
Q.append(1)    #enqueue(1)
print(Q.pop(0)) #dequeue

 

 

선형 큐의 문제점: 잘못된 포화 상태 인식!

리스트의 크기를 동적으로 바꾸지 않고 고정하면
사용할 큐의 크기만큼을 미리 확보해야 하므로
메모리의 낭비가 발생 할 수 있다.

선형 큐는 삽입, 삭제의 처리속도가 빠르다는 장점이 있지만,
메모리 낭비가 심하다는 단점이 있다.

1. 삽입, 삭제를 계속할 경우 리스트의 앞부분에 활용할 수 있는 공간이 있음에도, rear=n-1인 상태 즉, 포화 상태로 잘못 인식( 그러나 우리 문제풀이수준에서 선형큐 쓴다고 공간 모자라지 않는다.)
2. 더 이상의 삽입을 수행할 수 없음

• 선형 큐의 단점 해결방법
  • *앞으로 다 당기는건 시간공간 낭비가 너무 심하므로 절대 하지마. *
  • 원형 큐 사용으로 메모리 절약
  • 파이썬의 리스트 특성(동적으로 변경됨)을 사용한 큐 사용으로 메모리 절약
    • 단점: 삽입, 삭제 시 복사, 데이터 이동시키는 연산 수행에 많은 시간 소모
  • 단순연결 리스트로 구현한 큐 사용으로 메모리 동적 확보
  • 큐 라이브러리 사용해서 구현

 

 

해결방법2) 원형큐

rear과 front가 마지막 인덱스 까지가면 그다음 인덱스는 0으로 갈 수 있게 만드는 것을 의미한다.

but, 가득 차는 경우에 문제가 다시 생긴다. 즉 deQueue가 안일어나면 가득 차면 원형 큐 못쓴다.

• 1차원 배열을 사용하되, 논리적으로는 배열의 처름과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용

원형 큐의 특징

• 초기 공백 상태
  • front = rear = 0
    • 원형 순환을 위해 설정 된 값
• Index의 순환
  • front와 rear의 위치가 리스트의 마지막 인덱스인 n-1를 가리킨 후, 논리적 순환을 이루어 리스트의 처음 인덱스인 0으로 이동해야함
  • 이를 위해 나머지 연산자 %를 사용
• front 변수
  • 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠
• 삽입위치 및 삭제 위치

테이블 인덱스	삽입 위치	삭제 위치
선형 큐	rear=rear+1	front=front+1
원형 큐	rear=(rear+1)%n	front=(front+1)%n

원형 큐는 n이 넘어가면 n의 나머지를 구하여 위치를 재 조정한다.

 

 

원형 큐의 기본 연산 과정

큐 생성 시 시작은 0에서 front와 rear이 시작하고, 인큐는 rear값이 1증가하고 rear위치에 A를 삽입된다.
즉, 삽입이 0부터 되는게 아니라 [1]부터 한다.
삭제는 front 를 1증가시키고 프런트위치의 A가 삭제한다.(실제 삭제는 아니고 덮어씌운다고 생각하면 된다.)
마지막 삽입은 [0]에도 가능. 그리고 front위치에는 삽입 불가 하므로 front빼고 삽입 다 됐으면 Full이다.

 

 

원형 큐의 구현(다시 정리)

1. 초기 공백큐 생성

• 크기 n인 1차원 리스트 생성
• front, rear = 0으로 초기화

2. 공백상태 및 포화상태 검사 : isEmpty(), isFull()

• 공백상태 : front = rear
• 포화상태 시 선형큐와 다르다.
  • 삽입할 rear의 다음 위치가 현재 front값일 때이다.
• 삽입한 rear값의 다음위치를 계산할 때, rear에 1더하고 나머지연산을 수행하면 다음 위치를 구할 수 있다.
  • (rear+1) % n = front

ex) 크기가 4인 원형 큐에서 rear값이 3일 때 다음 삽입위치는 0이 된다.

def isEmpty():
    return front == rear

def isFull():
    return (rear+1) % len(cQ) == front
# rear 다음칸이 front만 꽉차있다는 말이다.

3. enQueue(item) - 마지막 원소 뒤에 새로운 원소를 삽입하기 위해.
   1. rear 값을 조정하여 새로운 원소를 삽일할 자리를 마련함: rear <-(rear+1)%n
   2. 인덱스에 해당하는 리스트원소 cQ[rear]에 item을 저장

point) 큐가 가득 차 있지 않을 때만 수행

def enQueue(item):
    global rear
    if isFull:
        print("Queue_Full")
    else:
        rear = (rear+1)%len(cQ)
        cQ[rear] = item

3. deQueue(), delete() - 맨앞의 큐 삭제 시에는 선형 큐와 비슷한 방법을 이용

(가장 앞에 있는 원소를 삭제하기 위해)

• front 값을 조정하여 삭제할 자리를 준비함
• 새로운 front 원소를 리턴함으로써 삭제와 동일한 기능을 함

front 값을 앞으로 이동시킬때 나머지 연산을 수행하여 큐의 마지막 위치에 있는 경우 큐의 제일 앞으로 front값을 이동시킬 수 있다. 역시 큐가 비어있는 경우 알려주어야한다.

def deQueue():
    global front
    if isEmpty():
        print("Queue_Empty")
    else:
        front = (front+1)%len(cQ)
        return cQ[front]
def delete():
    global front
    if isEmpty()
        print("Queue_Empty")
    else:
        front = (front+1)%len(cQ)

파이썬으로 구현한 원형 큐의 삽입 및 삭제 함수

def isEmpty():
    return front == rear
def isFull():
    return (rear+1) % len(cQ) == front
def enQueue(item) :
    global rear
    if isFull():
        print("Queue_Full")
    else:
        rear = (rear+1) % len(cQ)
        cQ[rear] = item
def deQueue():
    global front
    if isEmpty():
        print("Queue_Empty")
    else: 
        front = (front+1)%len(cQ)
        return cQ[front]

cQ_SIZE = 3
cQ = [0]*cQ_SIZE

# front, rear를 0으로 초기화
front = rear = 0

enQueue('A')
enQueue('B')
enQueue('C')
print(deQueue())
print(deQueue())
print(deQueue())

ABC순서대로 입력하면 ABC순서대로 결과를 받을 수 있는 FIFO구조다.

 

 

Queue의 종류3) 리스트의 특성을 사용한 Queue

1. 파이썬의 리스트 특성을 사용한 큐
   1. 리스트는 크기를 동적으로 변경할 수 있어서 메모리 절약!
   2. 삽입, 삭제 시 복사, 데이터를 이동시키는 연산을 수행하는데 많은 시간 소모
2. 리스트의 메서드

메서드	설명
append(item)	마지막위체에 원소 추가
pop(index)	index 위치에 원소 삭제

3. front는 항상 리스트의 맨 앞인: -1 을 가리킨다.
4. rear는 항상 리스트의 맨뒤는 len(queue)-1을 가리킨다.

따라서 front, rear 변수를 따로 관리할 필요 없다.

 

 

Queue의 종류4) 연결큐

참고만 해. 문풀은 이거말고 다른거써도 풀림. 물리적으로 위치가 다음위치이 아니고 뚝뚝 떨어져 위치한다. 있는 자료구조가 linked list라고 한다. 장점은 안쓰는거 날려버릴 수 있다. 구현이 너무 빡세다.

리스트로 이루어진 선형큐와 원형큐위 단점을 개선한 자료구조

• 단순 연결 리스트(Linked List)를 이용한 큐

  • 단순 연결 리스트를 이용하여 구현한 큐
  • front와 rear도 단순한 인덱스가 아닌 노드를 가리키는 링크
  • 큐의 원소 : 단순 연결 리스트의 노드
  • 큐의 원소 순서 : 노드의 연결 순서, 링크로 연결되어 있음
  • front: 첫 번째 노드를 가리키는 링크
  • rear: 마지막 노드를 가리키는 링크

• 상태 표현

  • front와 rear 값이 공백인 경우 , 즉 None 상태인 경우는 초기상태, 공백상태라고 한다.

 

 

연결큐 구현

1. 초기 공백 큐 생성: createLinkedQueue()

• 리스트 노드 없이 포인터 변수만 생성함
• front와 rear를 None로 초기화(파이썬에서는 정의하지 않은 상태)

front = None
rear = None

 

2. 공백상태 검사: isEmpty()

def isEmpty():
    return front == None

 

큐의 원소를 삭제 하기 위해서는 None 확인해야한다.

3. 삽입: enQueue(item)

• 새로운 노드 생성 후 데이터 필드에 item 저장
• 연결 큐가 공백인 경우, 아닌 경우에 따라 front, rear 변수 지정

def enQueue(item): #연결 큐의 삽입 연산
    gloval front,rear
    newNode = Node(item)
    if isEmpty():
        forint = newNode
    else:
        rear.next = newNode
    rear = newNode

 

4. 삭제: deQueue()

• old가 지울 노드를 가리키게 하고, front 재설정
• 삭제 후 공백 큐가 되는 경우, rear도 None로 설정
• old가 가리키는 노드를 삭제하고 메모리 반환

def deQueue():
    global front, rear
    if isEmpty():
        print("Queue_Empty")
        return None
       item = front.next
    if isEmpty():
        rear = None
    return item

 

 

파이썬으로 구현한 연결 큐

class Node:
    def __init__(self, item, n = None):
        self.item = item
        self.next = n
# 노드안에 item과 node을 만듬.


def enQueue(item):
    global front, rear
    newNode = Node(item) # 새로운 노드 생성
    if front == None: # 큐가 비어있으면
        front = newNode
    else:
        rear.next = newNode
    rear = newNode

def isEmpty():
    return front == None

def deQueue():
    global front, rear
    if isEmpty():
        print("Queue_Empty")
        return None

    item = front.item
    front = front.next
    if front == None:
        rear = None
    return item

def Qpeek():
    return front.item

def printQ():
    f = front
    s = ""
    while f:
        s += f.item + " "
        f = f.next
    return s

front = None
rear = None

enQueue('A')
enQueue('B')
enQueue('C')
printQ()
print(deQueue())
print(deQueue())
print(deQueue())

자료구죠 느낌이라. 참고만 하자.

 

 

Queue 활용1)우선순위 큐(Priority Queue)

반드시 써야하는건 아니지만, 쓰면 굉장히 속도가 빨라진다. 들어가더라고 우순위가 높은게 먼저 튀어나온다. 이런게 있구나 정도만 보자

힙소트! 나중에 다시 정리 한다

특성

• 우선순위를 가진 항목들을 저장하는 큐
• FIFO(선입선출) 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.

적용분야

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영체제의 테스크 스케줄링

구현

• 리스트를 이용한 우선순위 큐
• 우선순위 큐 라이브러리 사용

삽입: enQueue- 삽입된 원소를 우선순위에 맞는 위치에 삽입
삭제: deQueue- 우선순위가 가장 높은 가장 앞의 원소 삭제

1. 리스트를 이용하여 자료 저장
2. 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조
3. 가장 앞에 최고 우선순위의 원소가 위치하게 됨

발생하는 문제점

리스트를 사용하므로, 삽입이나 삭제 연산이 일어날 떄 원소의 재배치가 발생

소요되는 시간이 많이 걸림

이러한 문제점을 해결하기 위해 연결리스트를 이용하여 우선순위 큐를 구현하더라도 비교연산이 많이 일어난다.

해결

• 큐 모듈의 우선순위 큐를 구현한 PriorityQueue(maxsize)을 사용
• 힙 자료구조 사용(나중에 활용부분에서 살펴본다)

 

 

Queue 활용2) 버퍼

버퍼의 의미

• 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역
• 버퍼링: 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미

버퍼의 자료 구조

• 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용
• 순서대로 입력/출력/전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용됨

이는 물리적인 장치의 처리 속도 차이에서 발생하는 대기시간을 극복하기위한 방법. 데이터를 전송하는 동안 일시적으로 저장하는 영역이므로 데이터가 순서대로 전달 되어야 한다. 따라서 FIFO(선입선출)의 자료구조인 큐가 활용된다.

ex) 키보드 버퍼

사용자가 입력 후 엔터 누르면
키보드 입력 버퍼에 입력이 들어오고
프로그램 실행 영역에 전달 후 연산한다.

---

추가

역량테스트 B형은 라이브러리를 못쓰니까, 배열을 사용하면 다 터진다. 그러므로 B형 준비하는 사람은 C로 linked list를 만들 수 있어야돼. 파이썬은 씨의 구조체가 없어서 클래스로 만든다. 다음주는 class로 만들어서 하는거 진도로 나간다. A나 A+에서는 링크드 리스트 할 필요 없다.

우선순위 큐는. 힙큐라는걸 쓰는건데 그건 나중에 실습한다. 쓰기보다는 라이브러기 이용해서 한다.

링크리스트는 자료구조에서 사용할일 많지만, 실제 문풀에서 이렇게 쓸일 없다. 참고만 해서 알아두면된다.