Queue1

• [파이썬(Python)] 큐(Queue) 줄을 설 때 온 사람 순으로 차례 대로 들어가는 것 처럼 데이터가 입력된 순서대로 출력되는 선입선출(First In First Out)형이다. 배열이나 연결 리스트를 이용해서 구현한다. 다음과 같은 용어가 큐에 관련하여 사용된다. 인큐(enqueue): 큐에 데이터를 추가하는 작업 디큐(dequeue): 큐에서 데이터를 꺼내는 작업 프런트(front): 데이터를 꺼내는 쪽 리어(rear): 데이터를 넣는 쪽 큐 구현 방법 배열로 구현하기 인큐할 때는 맨 끝의 데이터 다음 원소에 새로운 데이터를 저장하면 되므로, 이때의 복잡도는 O(1)이다. 그러나, 디큐를 위해서는 맨 첫 번째 원소를 꺼내고 나머지 원소를 하나씩 앞쪽으로 당겨야 한다. 복잡도는 O(n)이다. 좀 더 효율적인 방법이 필요하다. 링 버퍼로 .. Data Structure 2023. 2. 15.