Python의 대기열 구현
- Python의 대기열 구현
- 대기열에 요소 추가: 대기열에 넣기 작업
- 대기열에서 요소 제거: 대기열에서 빼기 작업
- Python의 대기열에 대한 기타 작업
- Python에서 목록을 사용한 대기열 구현
- Python에서 연결 목록을 사용한 대기열 구현
- Python에서 컬렉션 모듈을 사용한 대기열 구현
- 파이썬에서 가장 효율적인 큐 구현
우리는 Python에서 대기열을 사용하여 선입선출(FIFO) 작업을 수행합니다. 이 기사에서는 Python에서 큐를 구현하는 세 가지 다른 방법에 대해 설명합니다.
Python의 대기열 구현
대기열에서 다양한 작업을 수행할 수 있습니다. 먼저 모든 작업의 일반적인 개념에 대해 논의한 다음 다양한 구성을 사용하여 대기열 작업을 구현합니다.
대기열의 첫 번째 요소를 앞 요소라고 합니다. 마찬가지로 대기열의 마지막 요소를 후면 요소라고 합니다.
예를 들어, 다음과 같은 일련의 숫자를 대기열로 간주하십시오. 1은 전면 요소이고 6은 후면 요소입니다.
1,2,3,4,5,6
대기열에 요소 추가: 대기열에 넣기 작업
대기열에 넣기 작업에서는 사람이 매표소에서 대기열에 합류하는 것처럼 요소를 대기열에 추가합니다. 새로 추가된 요소는 항상 뒤 요소가 됩니다.
예를 들어 위의 큐에 숫자 7을 추가하면 큐는 아래와 같이 표시됩니다.
1,2,3,4,5,6,7
큐의 뒤에만 요소를 추가할 수 있다는 점에 유의해야 합니다.
대기열에서 요소 제거: 대기열에서 빼기 작업
Dequeue 작업에서는 사람이 매표소에서 티켓을 받은 후 대기열에서 나가는 것처럼 대기열의 앞부분을 제거합니다.
대기열에서 빼기 작업 후 앞 요소는 대기열에서 제거되고 앞 요소 뒤의 요소는 새로운 앞 요소가 됩니다. 예를 들어 큐에서 빼기 작업 후 이전 예제에서 사용된 큐는 다음과 같습니다.
2,3,4,5,6,7
대기열에서 빼기 작업에서는 앞 요소만 제거할 수 있습니다. 대기열은 항상 선입선출 순서를 따릅니다. 따라서 대기열에 먼저 추가된 요소도 먼저 제거됩니다.
Python의 대기열에 대한 기타 작업
큐에 요소가 없으면 비어 있다고 합니다. 다른 구현에서 큐가 비어 있는지 확인하기 위해 다른 접근 방식을 사용할 수 있습니다.
때로는 대기열의 길이를 찾아야 할 수도 있습니다. 또한 이 작업의 구현에 대해서도 논의할 것입니다.
Python에서 목록을 사용한 대기열 구현
목록을 사용하여 Python에서 가장 간단하게 대기열을 구현할 수 있습니다. 목록을 사용하여 대기열을 만들려면
- 세 가지 속성으로
Queue클래스를 정의합니다. - 목록의 요소를 저장할 빈 목록
데이터를 정의합니다. front와rear라는 두 개의 변수를 초기화합니다.- 대기열이 비어 있음을 표시하기 위해 변수를
-1로 초기화합니다.
암호:
class Queue:
def __init__(self):
self.data = list()
self.front = -1
self.rear = -1
Queue 개체를 생성할 때 빈 목록이 생성되어 속성 data에 할당됩니다. 그런 다음 목록은 대기열의 요소를 저장합니다.
빈 큐를 생성한 후 큐에서 다른 작업을 구현합니다.
Python에서 대기열이 비어 있는지 확인
대기열이 비어 있는지 확인하기 위해 front 및 rear 속성이 -1로 초기화되었는지 확인할 수 있습니다. 이를 위해 isEmpty() 메서드를 정의합니다.
isEmpty() 메서드는 대기열에서 호출될 때 전면 및 후면 속성 값이 -1인지 여부를 확인합니다. 그렇다면 큐가 비어 있음을 나타내는 True를 반환합니다. 그렇지 않으면 False를 반환합니다.
암호:
def isEmpty(self):
if self.rear == -1 and self.front == -1:
return True
else:
return False
Python에서 목록을 사용하여 대기열에 넣기 작업
큐에 요소를 삽입하기 위해 먼저 큐가 비어 있는지 확인합니다. 위에서 정의한 isEmpty() 메서드를 사용할 수 있습니다.
- 대기열이 비어 있으면
append()메서드를 사용하여data속성에 포함된 목록에 요소를 추가합니다. 목록에서 호출되면append()메서드는 요소를 입력 인수로 사용하여 목록에 추가합니다. - 이제 목록에 하나의 요소만 있으므로
front및rear속성 값을0으로 업데이트합니다.front및rear요소는 모두data목록의 인덱스0에 있습니다. - 목록이 비어 있지 않으면 먼저
append()메서드를 사용하여 목록에 요소를 추가합니다. - 그런 다음 추가 요소가 대기열에 추가되었음을 나타내는
rear속성의 값을 증가시킵니다.
큐에 넣기 작업에서 front 속성의 값은 큐에서 요소를 제거하지 않기 때문에 변경되지 않습니다.
전체 작업은 다음과 같이 Python으로 구현할 수 있습니다.
암호:
def enQueue(self, element):
if self.isEmpty():
self.data.append(element)
self.front = 0
self.rear = 0
else:
self.data.append(element)
self.rear += 1
Python에서 목록을 사용하여 대기열에서 빼기 작업
대기열에서 빼기 작업을 위해 먼저 대기열이 비어 있는지 확인합니다. 그렇다면 운영할 수 없습니다. 그렇지 않으면 다음을 수행합니다.
- 대기열에 요소가 하나만 있는지 확인합니다.
front및rear속성이 동일한 값을 갖고 있는지, 그리고 그 중 어느 것도-1이 아닌지 확인할 수 있습니다. - 큐에 요소가 하나만 있는 경우
pop()메서드를 사용하여 큐의front인덱스에 있는 요소를 제거하고 사용자에게 반환합니다. 그런 다음front및rear속성을-1로 업데이트하여 대기열이 비었음을 표시합니다. - 위의 조건 중 어느 것도
True가 아닌 경우 대기열에 두 개 이상의 요소가 있는 것입니다. 이 경우front인덱스의 요소를 임시 변수에 저장합니다. - 그런 다음
front속성의 값을 증가시켜 목록의 다음 요소가front요소가 되었음을 나타냅니다. - 마지막으로 임시 변수에 저장된 값을 반환합니다.
암호:
def deQueue(self):
if self.isEmpty():
print("Queue is Empty. Cannot remove element")
elif self.front == self.rear and self.front != -1:
element = self.data[self.front]
self.front = -1
self.rear = -1
return element
else:
element = self.data[self.front]
self.front = self.front + 1
return element
Python에서 대기열 길이 찾기
Python에서 대기열의 길이를 찾기 위해 다음 단계를 수행할 수 있습니다.
- 큐가 비어 있으면 큐의 길이는 0이 됩니다. 따라서 먼저
isEmpty()메서드를 사용하여 큐가 비어 있는지 확인합니다. isEmpty()메서드가True를 반환하면 대기열 길이로0을 반환합니다.- 그렇지 않으면 목록의 길이는
후면-전면+1로 계산됩니다.
아래와 같이 length() 메서드에 이를 구현했습니다.
암호:
def length(self):
if self.isEmpty():
return 0
return self.rear - self.front + 1
우리는 모든 방법을 구현했습니다. 이제 모든 작업을 한 번 실행해 보겠습니다.
전체 코드:
class Queue:
def __init__(self):
self.data = list()
self.front = -1
self.rear = -1
def isEmpty(self):
if self.rear == -1 and self.front == -1:
return True
else:
return False
def enQueue(self, element):
if self.isEmpty():
self.data.append(element)
self.front = 0
self.rear = 0
else:
self.data.append(element)
self.rear += 1
def deQueue(self):
if self.isEmpty():
print("Queue is Empty. Cannot remove element")
elif self.front == self.rear and self.front != -1:
element = self.data[self.front]
self.front = -1
self.rear = -1
return element
else:
element = self.data[self.front]
self.front = self.front + 1
return element
def length(self):
return self.rear - self.front + 1
myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()
출력:
Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is Empty. Cannot remove element
예제에서는 목록을 사용하여 Python에서 대기열을 구현한 후 몇 가지 메서드를 실행했습니다. 코드를 복사하여 IDE에 붙여넣고 코드를 실험하여 코드 작동을 더 잘 이해할 수 있습니다.
Python에서 연결 목록을 사용한 대기열 구현
우리는 이미 Python의 연결 목록에 대한 다양한 작업에 대해 논의했습니다. Python에서 대기열 구현을 위해 연결 목록 작업을 사용할 수도 있습니다.
먼저 data와 next라는 두 가지 속성이 있는 노드를 정의합니다.
암호:
class Node:
def __init__(self, data):
self.data = data
self.next = None
어디:
data속성은 대기열의 요소를 저장하는 데 사용됩니다.next속성은 대기열의 현재 요소 앞에 있는 요소를 가리키는 데 사용됩니다.
Node를 정의한 후 Queue 클래스를 정의합니다. 여기서 front 및 rear 속성이 있습니다.
front 속성은 큐의 연결 목록에서 front 요소를 포함하는 노드를 가리킵니다. 마찬가지로 rear 속성은 큐를 포함하는 연결 목록에서 rear 요소를 포함하는 노드를 가리킵니다.
대기열이 비어 있으므로 front 및 rear 속성은 None으로 초기화됩니다.
암호:
class Queue:
def __init__(self):
self.front = None
self.rear = None
Queue 클래스가 초기화되면 None 값과 함께 front 및 rear 속성만 포함됩니다.
Python에서 대기열이 비어 있는지 확인
대기열이 비어 있는지 확인하기 위해 front 및 rear 속성이 None인지 확인할 수 있습니다. 그렇다면 대기열이 비어 있다고 말할 수 있습니다.
이 작업에 대한 isEmpty() 메서드를 정의합니다. 대기열에서 호출될 때 isEmpty() 메서드는 대기열이 비어 있으면 True를 반환합니다. 그렇지 않으면 False를 반환합니다.
암호:
def isEmpty(self):
if self.front is None:
return True
return False
Python에서 연결된 목록을 사용하여 대기열에 넣기 작업
대기열에 넣기 작업을 수행하기 위해 먼저 대기열이 비어 있는지 확인합니다. 그렇다면 새 요소가 있는 노드를 front 및 rear 속성 모두에 할당합니다.
그렇지 않으면 rear 노드의 다음 노드에 새 요소를 추가합니다. 그런 다음 새 노드를 후면 노드로 만듭니다.
이러한 방식으로 새 요소가 대기열에 추가됩니다.
암호:
def enQueue(self, data):
newNode = Node(data)
if self.isEmpty():
self.front = newNode
self.rear = newNode
else:
self.rear.next = newNode
Python에서 연결된 목록을 사용하여 대기열에서 빼기 작업
대기열에서 빼기 작업을 위해 먼저 대기열이 비어 있는지 확인합니다. 그렇다면 언더플로가 발생했다고 말하고 어떤 요소도 제거할 수 없습니다.
그렇지 않으면 먼저 front 노드의 임시 변수에 데이터를 저장합니다.
그런 다음 front 노드의 next 노드를 새로운 front 노드로 만듭니다. 그런 다음 del 문을 사용하여 임시 변수에 저장된 프런트 노드를 삭제합니다.
이런 식으로 이전 프런트 노드는 대기열에서 삭제됩니다. 마지막으로 임시 노드에 저장된 값을 반환합니다.
암호:
def deQueue(self):
if self.isEmpty():
print("Queue is empty. Cannot remove element.")
else:
element = self.front
nextFront = self.front.next
self.front = nextFront
value = element.data
del element
return value
Python에서 대기열 길이 찾기
- 대기열의 길이를 찾기 위해 먼저 변수 개수를
0으로 초기화합니다. - 그런 다음
while루프를 사용하여front노드에서 대기열 순회를 시작합니다. 다음 노드로 이동할 때count를1씩 증가시킵니다. - 대기열의 끝, 즉
None에 도달하면while루프를 종료합니다. - 마지막으로 대기열의 길이를 나타내는
count값을 반환합니다.
암호:
def length(self):
count = 0
if self.front is None:
return count
else:
temp = self.front
while temp is not None:
count += 1
temp = temp.next
return count
연결 목록을 사용하여 모든 대기열 방법을 구현했습니다. 이제 더 나은 방식으로 작업을 이해하기 위해 작업을 실행해 보겠습니다.
전체 코드:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def isEmpty(self):
if self.front is None:
return True
return False
def enQueue(self, data):
newNode = Node(data)
if self.isEmpty():
self.front = newNode
self.rear = newNode
else:
self.rear.next = newNode
def deQueue(self):
if self.isEmpty():
print("Queue is empty. Cannot remove element.")
else:
element = self.front
nextFront = self.front.next
self.front = nextFront
value = element.data
del element
return value
def length(self):
count = 0
if self.front is None:
return count
else:
temp = self.front
while temp is not None:
count += 1
temp = temp.next
return count
myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()
출력:
Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.
Python에서 컬렉션 모듈을 사용한 대기열 구현
파이썬에서 큐 구현을 위해 collections 모듈을 사용할 수도 있습니다.
Collections 모듈은 Python에서 큐와 스택을 구현하기 위해 deque(이중 큐) 클래스를 제공합니다. 아래 import 문을 사용하여 프로그램에서 deque 클래스를 가져올 수 있습니다.
from collections import deque
대기열을 구현하기 위해 Queue 클래스를 생성합니다. 아래와 같이 클래스 내에 deque 객체를 생성합니다.
암호:
class Queue:
def __init__(self):
self.data = deque()
Queue 클래스가 인스턴스화되면 대기열의 요소를 저장하기 위해 빈 deque 객체가 생성됩니다.
Python에서 대기열 길이 확인
대기열의 길이를 확인하기 위해 length() 메서드를 정의합니다. length() 메서드 내에서 len() 함수를 사용하여 deque 개체의 길이를 계산합니다.
len() 함수는 deque 객체를 입력으로 사용하고 deque 길이를 반환합니다. 아래와 같이 len() 함수의 값을 대기열의 길이로 반환합니다.
암호:
def length(self):
return len(self.data)
Python에서 대기열이 비어 있는지 확인
대기열의 길이가 0인 경우 대기열이 비어 있다고 합니다. 아래와 같이 isEmpty() 메서드를 정의할 수 있습니다.
암호:
def isEmpty(self):
if self.length() == 0:
return True
return False
Python에서 요소를 큐에 넣기
요소를 대기열에 추가하기 위해 enQueue() 메서드를 정의합니다. enQueue() 메서드는 새 요소를 입력 인수로 사용합니다.
enQueue() 메서드 내에서 append() 메서드를 사용하여 deque 개체에 요소를 추가합니다. append() 메서드는 deque 개체에서 호출될 때 새 요소를 입력 인수로 사용하여 deque 개체에 추가합니다.
암호:
def enQueue(self, x):
self.data.append(x)
Python에서 대기열 제거 작업
대기열에서 요소를 제거하기 위해 deQueue() 메서드를 정의합니다. deQueue() 메서드 내에서 대기열의 deque 개체에서 popleft() 메서드를 호출합니다.
popleft() 메서드는 deque 개체에서 호출될 때 deque의 앞 요소를 제거합니다. 또한 대기열에서 제거된 요소를 반환합니다.
또한 return 문을 사용하여 deQueue() 메서드에서 popleft() 메서드가 반환한 값을 반환합니다.
암호:
def deQueue(self):
if self.isEmpty():
print("Queue is empty. Cannot remove element.")
else:
return self.data.popleft()
이제 컬렉션 모듈을 사용하여 파이썬에서 큐 구현을 위한 모든 메서드를 구현했습니다. 전체 실행을 관찰합시다.
전체 코드:
from collections import deque
class Queue:
def __init__(self):
self.data = deque()
def length(self):
return len(self.data)
def isEmpty(self):
if self.length() == 0:
return True
return False
def enQueue(self, x):
self.data.append(x)
def deQueue(self):
if self.isEmpty():
print("Queue is empty. Cannot remove element.")
else:
return self.data.popleft()
myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()
출력:
Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.
파이썬에서 가장 효율적인 큐 구현
이 기사에서는 Python에서 큐를 구현하는 세 가지 접근 방식에 대해 설명했습니다.
여기에서 논의된 모든 접근 방식 중에서 목록을 사용하여 대기열 요소를 저장하는 것이 최악입니다. 이 접근 방식에서는 요소가 목록에서 삭제되지 않습니다.
따라서 프로그램에서 사용하지 않는 것이 좋습니다. Python 초보자이고 연결 목록에 대해 전혀 모르는 경우에만 사용하십시오.
외부 모듈을 사용할 수 없는 경우 시간 및 메모리 효율적이므로 연결 목록을 사용하는 Python 대기열 구현을 사용할 수 있습니다. 그러나 deque를 사용하는 접근 방식보다 느립니다.
Python의 가장 효율적인 대기열 구현을 위해 deque 모듈 접근 방식을 사용해야 합니다. 모듈의 소스 코드가 C로 작성되고 구현이 이중 연결 목록을 사용하여 deque 개체를 구현하기 때문에 시간과 메모리 측면에서 가장 효율적입니다.
이 기사가 Python의 대기열 구현을 이해하는 데 도움이 되었기를 바랍니다. 더 유익한 기사를 계속 지켜봐주십시오.
Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.
GitHub