Queues · 큐
A queue is FIFO
- A queue is First In, First Out (FIFO).
- The first item you add is the first one to leave.
- Think of a line of people: the person at the front is served first.
큐는 FIFO입니다
- 큐는 선입 선출(FIFO)입니다.
- 가장 먼저 추가한 항목이 가장 먼저 나갑니다.
- 줄 서 있는 사람을 생각해보십시오: 맨 앞 사람이 먼저 서비스를 받습니다.
enqueue and dequeue with a list
- We can build a queue from a Python list.
- enqueue =
queue.append(x)— add to the back. - dequeue =
queue.pop(0)— remove and return the front.
목록을 이용한 enqueue 및 dequeue
- Python list를 사용하여 큐를 구현할 수 있습니다.
- enqueue =
queue.append(x)— 뒤쪽에 추가합니다. - dequeue =
queue.pop(0)— 앞쪽을 제거하고 반환합니다.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front and empty
- Look at the front without removing it:
queue[0]. - A queue is empty when
len(queue) == 0. - Check it is not empty before you dequeue.
front과 empty
- 제거하지 않고 앞쪽을 확인합니다:
queue[0]. - 큐가 비어 있을 때는
len(queue) == 0입니다. - dequeue하기 전에 비어 있지 않은지 확인하십시오.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
A note on speed
pop(0)has to shift every other item forward by one place.- For a big queue that is slow, so it uses more time.
- Real systems use a circular buffer with front and rear pointers instead.
속도 관련 참고 사항
pop(0)는 다른 모든 항목을 한 자리씩 앞으로 밀어야 합니다.- 큰 큐에서는 느리므로 시간이 더 많이 소요됩니다.
- 실제 시스템은 전방 및 후방 포인터가 있는 순환 버퍼를 사용합니다.
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
캐미지아 가위코드에서
- 시험은 queue(대기열)를 배열로 구성하며, 이를 위해
front과rear포인터를 사용합니다.
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
Common mistakes
- A queue is first-in, first-out: join the back, leave from the front.
- Check it is not empty before you dequeue.
흔한 실수
- 큐는 선입 선출입니다: 뒤쪽에 참여하고, 앞에서 나갑니다.
- dequeue하기 전에 비어 있지 않은지 확인하십시오.
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
이제 직접 해보기
- 큐로 list를 사용하십시오(
append로 enqueue,pop(0)로 dequeue). - Answer 확인 버튼을 눌러 코드를 테스트하세요.
A queue is FIFO · 큐는 FIFO입니다
A queue adds at the back and removes at the front — first in, first out. · 큐는 뒷부분에 추가하고 앞부분에서 제거하며, 이는 '선입 선출(First In, First Out)' 원리입니다.
Start with an empty queue. Enqueue "a", then "b", then "c". Then dequeue once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].) · 빈 큐를 시작합니다. enqueue하여 "a", "b", "c"을 순서대로 넣으세요. 이후 dequeue를 한 번 수행하여 제거된 값을 first에 저장합니다. (first은 "a"이어야 하며 큐는 ["b", "c"]이어야 합니다.)
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same order. (result should be [1, 2, 3].) · 큐에 1, 2, 3을 enqueue한 후, 모두 dequeue하여 result에 담습니다. 스타트와 달리 큐는 동일한 순서를 유지합니다. (result은 [1, 2, 3]이어야 합니다.)
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write serve(queue) that dequeues the front item: remove it from the list and return it. The caller's list should get shorter. · serve(queue)을 작성하여 queue의 최전방 요소를 dequeue하세요:列表中에서 제거하고 반환합니다. 호출자의 목록 길이는 짧아져야 합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write front(queue) that returns the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · front(queue)을 작성하여 queue의 최전방 요소를 제거하지 않고 반환하여 queue 상태가 변하지 않도록 하세요. 큐가 비어 있다면 None을 반환합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.