스택

• 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)이다.
• 스택에 데이터를 넣는 작업을 푸시라고 하고, 스택에서 데이터를 팝이라고 한다.
• 푸시와 팝을 하는 위치를 탑, 스택의 가장 아랫부분을 바텀이라 한다.
• 자바에서 메서드를 호출하고 실핼할 때 프로그램 내부에서는 스택을 사용한다.
  

큐

• 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조로, FIFO로 데이터가 입출력된다.
• 큐에 데이터를 넣는 작업을 인큐라 하고, 데이터를 꺼내는 작업을 디큐라고한다.
• 데이터를 꺼내는 쪽이 프런트, 넣는 쪽이 리어이다.
  

구현할 때 핵심

• 디큐를 프런트에서 데이터를 빼낸 후 나머지 요소를 맨 앞으로 옮기는 형태는 O(n)의 복잡도를 가지며 비효율적이다.
  
• 해당 자료구조를 링버퍼라고 하며, 배열의 처음과 끝을 연결하는 형태로 디큐를 효율적으로 구현할 수 있다. 복잡도는 O(n)이다.
• 링버퍼는 데이터를 추가하면 계속 회전하면서 데이터가 입력되기 때문에, 오래된 데이터를 새로운 데이터가 덮어쓰는 용도로 사용할 수 있다.