Stack은 선입선출(Last-In-First-Out)구조로 먼저 들어온 데이터가 top의 위치하여 먼저 나간다. 삽입, 삭제는 O(1)의 가능하며 탐색은 O(N)의 시간이 소요된다. 함수 호출, 시스템 콜등에 stack이 사용된다.
Queue는 선입후출(First-In-FirstOut)구조로 먼저 들어온 데이터가 먼저 나간다. 마찬가지로 삽입, 삭제는 O(1)만의 가능하며 탐색은 O(N)의 시간이 소요된다. Queue는 BFS, 순서대로 처리해야 되는 상황등에 자주 사용된다.
이 둘의 자료구조는 링크드리스트로 구현 될 수 있다.
메인 큐와 서브 큐, 두개의 큐를 만든다. 데이터가 입력 될 시, 메인 큐에 데이터들을 모두 서브 큐로 옮기고, 입력 데이터를 메인 큐에 저장 후 다시 서브큐에 데이터들을 메인 큐로 옮긴다.
1,2,3 가 순서대로 들어온다고 생각해보자.
public class Queue {
private Stack inBox = new Stack();
private Stack outBox = new Stack();
public void enQueue(Object item) {
inBox.add(item);
}
public Object deQueue() {
if (outBox.isEmpty()) {
while(!inBox.isEmpty()) {
outBox.push(inBox.pop());
}
}
return outBox.pop();
}
public static void main(String[] args) {
Queue queue = new Queue(); queue.enQueue("A"); queue.enQueue("B"); queue.enQueue("C");
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
}
}
링크드리스트의 총 노드수를 저장하는 cnt 변수를 만들고, 이 변수의 1/2이 될 때까지 노드를 탐색한다.
두개의 포인터를 사용한다. 하나는 노드를 하나씩 이동하고, 다른 하나는 노드를 두개 씩 이동한다. 두개 씩 이동하는 노드가 끝에 도달했을 때 다른 노드가 가르키고 있는 노드가 가운데 노드가 된다.
책 - 코딩인터뷰 완전분석
출처: https://creatordev.tistory.com/83
https://doublesprogramming.tistory.com/229