[Algorithm] Queue (큐)
[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의
알고리즘을 배우며, 실무에서는 알고리즘이 어떻게 활용되는지 알아봅니다., [임베딩 영상] 알고리즘의 개요와 실습 환경 구축 알고리즘은 문제를 해결하는 절차입니다.입력, 출력, 유한성, 명
www.inflearn.com
동빈 나님의 15번째 강의에 대한 리뷰다.
Queue는 Stack과 달리 First In First Out, FIFO를 따른다.
front 는 head, first 등 으로 back은 tail, rear, last 등 다른 이름으로 불릴 때도 있다.
** C++
#include <iostream>
#include <queue>
using namespace std;
int main(void) {
queue<int> q;
q.push(7);
q.push(5);
q.push(4);
q.pop();
q.push(6);
q.pop();
while (!q.empty()) {
cout << q.front() << ' '; // 가장 앞에 있는 값 출력
q.pop();
}
return 0;
}
** Javascript
javascript 의 pop 은 queue의 pop 와는 기능이 다르다. push는 같다.
FIFO 하려면 javascript 에서는 pop()이 아닌 shift()를 해줘야 한다.
그래서 위 C++소스를 javascript 로 변환해준다면
function main() {
let q = [];
q.push(7);
q.push(5);
q.push(4);
q.shift();
q.push(6);
q.shift();
while (q.length) {
console.log(q.shift());
}
}
이렇게 된다.
Queue 가 없는 javascript 에 queue 기능을 하는 메소드를 만들어야 한다면
간단하게 push, shift를 이용하는 방법이 있다.
function Queue() {
this.queue = [];
}
Queue.prototype.enqueue = function (element) {
this.queue.push(element);
};
Queue.prototype.dequeue = function () {
return this.queue.shift();
};
Queue.prototype.isEmpty = function () {
return this.queue.length === 0;
};
Queue.prototype.peek = function () {
return this.queue[0];
// 혹은 return !this.isEmpty() ? this.queue[0] : undefined;
};
Queue.prototype.length = function() {
return this.queue.length;
}
위 소스보다 더 완전한 Queue를 구현하고 싶다면 아래와 같은 소스도 있다.
출처: https://stackoverflow.com/questions/1590247/how-do-you-implement-a-stack-and-a-queue-in-javascript
How do you implement a Stack and a Queue in JavaScript?
What is the best way to implement a Stack and a Queue in JavaScript? I'm looking to do the shunting-yard algorithm and I'm going to need these data-structures.
stackoverflow.com
function Queue() {
this.head = null;
this.tail = null;
}
Queue.prototype.enqueue = function(data) {
var newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
Queue.prototype.dequeue = function() {
var newNode;
if (this.head !== null) {
newNode = this.head.data;
this.head = this.head.next;
}
return newNode;
}
Queue.prototype.print = function() {
var curr = this.head;
while (curr) {
console.log(curr.data);
curr = curr.next;
}
}
** Java
강의에서 나온 C++ 소스를 Java로 변환하면 아래와 같다.
import java.util.*;
public class Main
{
public static void main(String[] args) {
Queue<Integer> qu = new LinkedList<Integer>(); // 큐의 생성
qu.offer(7);
qu.offer(5);
qu.offer(4);
qu.poll();
qu.offer(6);
qu.poll();
while(qu.size() != 0) {
System.out.printf("%d ", qu.poll());
}
}
}
Java에서 Stack은 클래스이나 Queue는 인터페이스로 제공된다.
Queue 한테는 자식이 넷이 있다.
1. Deque<E>
2. BlockingDeque<E>
3. BlockingQueue<E>
4. TransferQueue<E>
특히 Deque 인터페이스를 구현한 LinkedList 클래스가 큐 메모리 구조를 구현하는 데 가장 많이 사용된다고 한다.
import java.util.*;
public class Main
{
public static void main(String[] args) {
Queue<String> qu = new LinkedList<String>(); // 큐의 생성
LinkedList<String> LLqu = new LinkedList<String>(); // 큐의 생성
// 더욱 복잡하고 빠른 큐를 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용
// Deque<String> qu = new ArrayDeque<String>();
// add() 메소드를 이용한 요소의 저장
qu.add("넷");
qu.add("둘");
qu.add("셋");
qu.add("하나");
// peek() 메소드를 이용한 요소의 반환
System.out.println(qu.peek()); // 넷
System.out.println(qu); // [넷, 둘, 셋, 하나]
// poll() 메소드를 이용한 요소의 반환 및 제거
System.out.println(qu.poll()); // 넷
System.out.println(qu); // [둘, 셋, 하나]
// remove() 메소드를 이용한 요소의 제거
qu.remove("하나");
System.out.println(qu); // [둘, 셋]
}
}
| 메소드 | 설명 |
| boolean add(E e) | 큐의 맨 뒤에 전달된 요소를 삽입함. 삽입 성공하면 true를 반환하고, 여유 공간이 없어 삽입 실패하면 IllegalStateException 발생 |
| E element() | 삭제 없이 큐의 맨 앞 (제일 먼저 저장된) 요소 리턴 비어있으면 NoSuchElementException 발생 |
| boolean offer(E e) | 큐의 맨 뒤에 요소를 삽입함 삽입 성공하면 true 반환하고 실패하면 false 반환 |
| E peek() | 큐의 맨 앞 (제일 먼저 저장된) 요소를 리턴 만약 큐가 비어있으면 null 리턴 |
| E poll() | 큐의 맨 앞 (제일 먼저 저장된) 요소를 리턴하고, 해당 요소를 큐에서 삭제함. 만약 큐가 비어있으면 null 리턴 |
| E remove() | 큐의 맨 앞 (제일 먼저 저장된) 요소를 제거 |
add 와 offer 가 헷갈려서 더 찾아봤다.
| 예외 발생 | 값 리턴 | |
| 추가 (enqueue) | add(E e) | offer(E e) (여유 공간 없으면 false) |
| 삭제 (dequeue) | remove() | poll() (큐 비어있으면 null) |
| 검사 (peek) | element() | peek() (큐 비어있으면 null) |
참고: https://goodteacher.tistory.com/112
** Python
강의에 나온 C++ 소스를 Python 으로 바꾸면 아래와 같다.
from collections import deque
que = deque()
que.append(7)
que.append(5)
que.append(4)
que.popleft()
que.append(6)
que.popleft()
print(que)
Python에서 Stack과 마찬가지로 Queue 도 기본 list 구조로 간단하게 만들 수 있다.
# 리스트를 이용하여 큐 구현
class Queue:
def __init__(self):
self.queue = []
def length(self):
return len(self.queue)
def empty(self) -> bool:
return len(self.queue) == 0
def push(self, item):
self.queue.append(item)
def pop(self):
if not self.empty():
return self.queue.pop(0)
else:
print("IndexError: list index out of range")
exit()
def peek(self):
if not self.empty():
return self.queue[0]
else:
print("IndexError: list index out of range")
exit()
def print(self):
print(self.queue)
위와 같이 append 와 pop(0) 을 이용하는 방법도 있는데
# 리스트를 이용하여 큐 구현
class Queue:
def __init__(self):
self.queue = []
def length(self):
return len(self.queue)
def empty(self) -> bool:
return len(self.queue) == 0
def push(self, item):
self.queue.insert(0, item)
def pop(self):
if not self.empty():
return self.queue.pop()
else:
print("IndexError: list index out of range")
exit()
def peek(self):
if not self.empty():
return self.queue[0]
else:
print("IndexError: list index out of range")
exit()
def print(self):
print(self.queue)
insert 를 이용하면 pop에 인덱스를 넣지 않고 사용할 수 있다.
a ---( enque, insert(0, a) )---> [ a, b, c, d ] ---( deque, pop() )---> d
list 인데도 FIFO가 명확하게 보이는 소스다.
하지만 list 를 이용한 Queue 구조는 연산 시간복잡도가 O(N)이어서 많은 수의 데이터를 처리하기엔 비효율적이라고 한다.
list 자료 구조의 .append(n) 함수를 사용하면 뒤에 데이터를 추가 할 수 있고,
.pop(0) 함수를 이용하면 맨 앞의 데이터를 제거할 수 있기 때문에 큐 자료구조를 사용하는 효과가 난다.
그러나 성능적으로 문제가 있는데, 파이썬의 list 자료 구조는 무작위 접근에 최적화된 자료 구조이기 때문이다.
pop(0) 연산의 시간 복잡도는 O(N)이어서 N이 커질 수록 연산이 매우 느려진다. 그래서 큐 자료구조를 사용하려고 한다면 list 자료 구조는 비추!
출처: https://velog.io/@sossont/Python-Queue-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B8%B0
그래서 사용하는 것이 Collections 모듈의 deque
deque는 double-ended queue의 약자다.
from collections import deque
que = deque()
que.append(1)
que.append(2)
que.append(3)
que.append(4)
print(que)
que.popleft()
que.appendleft(1)
print(que)
deque의 경우 popleft(), appendleft(e) 메소드가 추가적으로 존재한다.
deque는 방향성을 갖고 있는 클래스여서 데이터를 양방향으로 추가 및 제거가 가능하다.
popleft() 는 가장 맨 왼쪽, 맨 앞에 값을 꺼낸 뒤 제거 해주고
appendleft(e)는 가장 맨 왼쪽, 맨 앞에 값을 삽입할 수 있게 해준다.
appendleft(e) 와 popleft() 을 이용할 수 있는 deque 는 데이터 추가/삭제로는 O(1) 의 시간복잡도를 가진다.
그러나 linked list 구조이기 때문에 데이터 접근의 시간 복잡도는 O(N)이다.
Python 에는 사실 Queue 클래스도 있다. 하지만 deque와 같은 방향성이 없다.
말 그대로 Queue 의 기능만 한다. 하지만 이 때문에 오히려 알아보기는 쉽다.
시간복잡도는 deque와 마찬가지로 데이터 추가, 삭제 부분에서는 O(1)의 시간복잡도, 접근은 O(N)의 시간복잡도를 가진다.
from queue import Queue
que = Queue()
que.put(5)
que.put(4)
que.put(3)
que.get()
que.get()
그런데 이것저것 써보니 queue 가 비어있을 때 get을 하면 java 처럼 NoSuchElementException 같은 것은 없고 timeout 되는 것 같다.
print 도 되고 python 내장함수랑 이름이 비슷한 deque를 훨씬 더 많이 사용하는 이유가 있는 것 같다.
deque : https://docs.python.org/3.8/library/collections.html#collections.deque
Queue : https://docs.python.org/3/library/queue.html