์คํ๊ณผ ๊ฐ์ด ํ๋ก๊ทธ๋๋ฐ์ด๋ผ๋ ๊ฐ๋ ์ด ํ์ํ ๋๋ถํฐ ์ฌ์ฉ๋ ๊ฐ์ฅ ๊ณ ์ ์ ์ธ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
https://www.programiz.com/dsa/queue
ํ์ด์ฌ์์ ์คํ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ฆฌ์คํธ๊ฐ ํ์ ๋ชจ๋ ์ฐ์ฐ์ ์ง์ํ๋ค. ๋ค๋ง ๋ฆฌ์คํธ๋ ๋์ ๋ฐฐ์ด๋ก ๊ตฌ์ฑ๋์ด ์์ด ํ์ ์ฐ์ฐ์ ์ํํ๋๋ฐ ํจ์จ์ ์ด์ง ์๋ค.
( Array์์ pop(0)์ O(n)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.)
๋ฐ๋ผ์ ๋ฐํฌ(Deque)๋ผ๋ ๋ณ๋์ ์๋ฃํ์ ์ฌ์ฉํด์ผ ์ข์ ํจ์จ์๊ฐ์ง๋ค.
๐ค ๋ฐํ(Deque)๋?
Deque๋ double-ended queue์ ์ค์๋ง๋ก, ์๊ณผ ๋ค ์ฆ ์๋ฐฉํฅ์์ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ ์ ์๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๋งํ๋ค.
์คํ๊ณผ ํ์ ๊ธฐ๋ฅ์ ๋ชจ๋ ๊ฐ์ก๋ค.
- ๋ค(์ค๋ฅธ์ชฝ) ๋ฐ์ดํฐ ์ถ๊ฐ ๋ฐ ์ญ์
์ถ๊ฐ: append()
์ญ์ : pop()
(O(1)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ฉฐ, ์คํ๊ณผ ๋์ผํ๋ค.)
- ์(์ผ์ชฝ) ๋ฐ์ดํฐ ์ถ๊ฐ ๋ฐ ์ญ์
์ถ๊ฐ: appendleft()
์ญ์ : popleft()
(O(1)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ฉฐ, ์์์ ์ธ๊ธ ํ๋ฏ์ด Array๋ณด๋ค ๋ ํจ์จ์ ์ธ ์ฐ์ฐ์ฒ๋ฆฌ๋ฅผ ํ๋ค.)
class QueueByArray:
def __init__(self):
self.queue = []
# ์ถ๊ฐ
def push(self, value):
self.queue.append(value)
# ์ญ์
def pop(self):
# ํ ์์ ๋ฐ์ดํฐ๊ฐ ์์ ๋์ ์์ธ์ฒ๋ฆฌ
if not self.queue:
return None
# O(n)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
return self.queue.pop(0)
# ์กฐํ
def peek(self):
return self.queue[0]
def is_empty(self):
if len(self.queue) == 0:
return True
return False
class QueueByArray:
def __init__(self):
self.queue = collections.deque()
# ์ถ๊ฐ
def push(self, value):
self.queue.push(value)
# ์ญ์
def pop(self):
# ํ ์์ ๋ฐ์ดํฐ๊ฐ ์์ ๋์ ์์ธ์ฒ๋ฆฌ
if not self.queue:
return None
# O(1)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
return self.queue.popleft()
# ์กฐํ
def peek(self):
return self.queue[0]
def is_empty(self):
if len(self.queue) == 0:
return True
return False
class Node:
def __init__(self, item, next):
self.item = item
self.next = next
class QueueByLikedList:
def __init__(self):
# front ์ด๊ธฐํ
self.front = None
# ์ถ๊ฐ
def push(self, value):
if not self.front:
self.front = Node(value, None)
return
node = self.front
while node.next:
node = node.next
node.next = Node(value, None)
# ์ญ์
def pop(self):
# ๋ฐ์ดํฐ๊ฐ ์์ ๋ ์์ธ์ฒ๋ฆฌ
if self.front is None:
return None
node = self.front
self.front = self.front.next
return node.item
# ํ ๋น์๋์ง ํ์ธ
def is_empty(self):
if not self.front:
return True
return False
์ฐธ์กฐ)
ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ ์ธํฐ๋ทฐ