๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Posts/CS

[Python ์ž๋ฃŒ๊ตฌ์กฐ] ํ (Queue)

๋ฐ˜์‘ํ˜•

๐Ÿ’ก Goal
- ํ๋ฅผ ์ดํ•ดํ•œ๋‹ค.
- ํ๋ฅผ ํŒŒ์ด์ฌ์œผ๋กœ ๊ตฌํ˜„ํ•œ๋‹ค.
- ํ ํŠน์ง• 2๊ฐ€์ง€ ์ด์ƒ ๋งํ•˜๊ธฐ.


๊ฐœ๋…


FIFO(First In First Out)์œผ๋กœ ๋™์ž‘ํ•˜๋ฉฐ ๋ฐ์ดํ„ฐ๊ฐ„ ์ˆœ์„œ๋ฅผ ์•ฝ์†ํ•˜๋Š” ์ถ”์ƒ์ž๋ฃŒํ˜•์„ ๋งํ•œ๋‹ค.

๊ฐ€์žฅ ๋จผ์ € ๋“ค์–ด์˜จ ๋ฐ์ดํ„ฐ๊ฐ€ ๊ฐ€์žฅ ๋จผ์ € ์‚ญ์ œ

๋Œ€๊ธฐ์—ด๊ณผ ๊ฐ™์€ ๊ฐœ๋… (ATM๊ธฐ ์ค„์„œ์žˆ๋Š” ์‚ฌ๋žŒ๋“ค ๋ชจ์Šต)


ํŠน์ง•


  • deque๋ฅผ ์‚ฌ์šฉํ•ด ํ ์ž๋ฃŒ๊ตฌ์กฐ ๊ตฌํ˜„ (doubly-ended-queue์˜ ์•ฝ์ž)
    • deque๋Š” ๋‚ด๋ถ€์ ์œผ๋กœ doubly linked list๋กœ ๊ตฌํ˜„
    • ๋งจ ์•ž, ๋’ค์— ๋ฐ์ดํ„ฐ๋ฅผ ์‚ญ์ œํ•˜๊ณ  ์‚ญ์ œํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•˜๋Š” ์ž๋ฃŒํ˜•
    • enqueue: ๋์— ์‚ฝ์ž…
    • peek: ์‹œ์ž‘ ๊ฐœ์ฒด๊ฐ’ ๋ฆฌํ„ด
    • dequeue: ์‹œ์ž‘ ๊ฐœ์ฒด๊ฐ’ ์ œ๊ฑฐ
  • ํ์˜ ํ™œ์šฉ
    • ์Šค์ผ€์ค„๋ง
      • ๋™์‹œ์— ์‹คํ–‰๋˜๋Š” ์—ฌ๋Ÿฌ ํ”„๋กœ์„ธ์Šค์˜ ์ž์›์„ ๋ฐฐ์ •์„ ์ ์ ˆํžˆ ์กฐ์ ˆํ•ด ์„ฑ๋Šฅ ๊ฐœ์„ 
    • ์–ด๋–ค ์ž‘์—…์ด ๋ณ‘๋ ฌ์ ์œผ๋กœ ์ฒ˜๋ฆฌ๋ ๋•Œ ํ์— ์ €์žฅํ•˜์—ฌ ๊ด€๋ฆฌ

์‹œ๊ฐ„๋ณต์žก๋„ O(1)

https://user-images.githubusercontent.com/48043799/148674083-5b0a710a-6834-4656-925f-4e95a3180c81.png

  • popleft: O(1)

์ฝ”๋“œ ๊ตฌํ˜„

from collections import deque

class Queue:
    def __init__(self, value=[]):
        self.items = deque(value)

    def enqueue(self, data):
        self.items.append(data)

    def dequeue(self):
        if not self.is_empty():
            self.items.popleft()
        else:
            print("underflow")
            exit()

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        else:
            print("underflow")
            exit()

    def is_empty(self):
        return len(self.items) == 0

queue = Queue()

queue.enqueue(1)
queue.enqueue(3)
queue.dequeue()
queue.enqueue(5)

print(queue.items[1]) # 5
print(queue.peek()) # 3

References

๋ฐ˜์‘ํ˜•