Array, Queue, ArrayDeque

Stack

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
System.out.println(stack.peek());
System.out.println(stack.pop());

• Stack에서 넣는 값은 push()

• Stack에서 빼서 보는 것은 peek()

• Stack에서 빼는 것은 pop()

• FILO

Queue

Queue<Integer> queue = new Queue<>();
queue.add(10);
queue.add(20);
System.out.println(queue.peek());
System.out.println(queue.poll()); // queue는 poll로 빼낸다. FIFO

• Stack에서 넣는 값은 add()

• Stack에서 빼서 보는 것은 peek()

• Stack에서 빼는 것은 poll()

• FIFO

contains, remove 등 O(N) API 사용 주의

for (int i = 0; i < MAX; i++){
    if (stack.contains(MAX)) {
    }
}

for (int i = 0; i < MAX; i++){
    if (queue.remove(MAX)) {
    }
}

• contains(), remove() 할 때마다 완전탐색

• Stack, Queue, ArraydEque, ArrayList 등의 자료구조에서 contains(), remove() 가급적 사용 X

• MAX = 100000 일 때

  • Stack: 7.016초

  • Queue: 8.48초

• HashMap의 containsKey는 일반적으로 O(1) 이라 괜찮다.

  • MAX = 100000 일 때: 0.011초

ArrayDeque as Stack

ArrayDeque<Integer> arrayDequeStack = new ArrayDeque<>();
arrayDequeStack.addLast(10);
arrayDequeStack.addLast(20);
System.out.println(arrayDequeStack.peekLast());
System.out.println(arrayDequeStack.pollLast());

• Stack 이 ArrayDeque보다 미세하게 빠르다 (SingleThread에서)

ArrayDeque as Queue

ArrayDeque<Integer> arrayDequeQueue = new ArrayDeque<>();
arrayDequeQueue.addLast(10);
arrayDequeQueue.addLast(20);
System.out.println(arrayDequeQueue.peekFirst());
System.out.println(arrayDequeQueue.pollFirst());