Java로 자료구조 이해하기 3편(Stack과 Queue)

Stack과 Queue란?

Stack(Class)

• LIFO(Last In First Out) 구조
• 마지막에 저장한 것을 제일 먼저 꺼낸다.
• Array 기반

Queue(Interface)

• FIFO(First In First Out) 구조
• 제일 먼저 저장한 것을 제일 먼저 꺼낸다.
• LinkedList 기반
  -> Interface이기 때문에 LinkedList가 Queue를 구현

이게 끝 입니다.

왜 그런지 알아 보도록 하겠습니다.

Stack은 밑이 막혀있고 위만 뚫려 있는 구조 입니다. 우리가 일반적으로 알고 있는 상자와 같습니다.
책을 넣으면 마지막에 넣은 책 부터 뺄 수가 있죠? 정확히 그와 같은 구조 입니다.
그렇기 때문에 마지막에 저장한 것을 제일 먼저 꺼낸다 는 특징이 있습니다.

반대로 Queue 는 위 아래 모두 뚫려있습니다. 수도관과 동일한데 위에서 먼저 들어간게 그대로 아래로 가장 먼저 나옵니다.
절대 위에 있는게 아래로 먼저 나올 수 없죠? 그렇다고 위에 있는걸 위로 꺼내는 일도 없구요.
딱 그런 구조이기 때문에 제일 먼저 저장한 것을 제일 먼저 꺼낸다 라는 특징이 있습니다.

Stack 을 한 번 옆으로 눕혀보면, 배열과 동일 합니다. 배열은 마지막에 있는 것을 추가/삭제 할 때 빨랐죠?
이런 특징은 Stack과 동일하며, Stack은 배열의 이러한 장점을 이용해 구현 되어 있습니다.
Stakc은 배열 기반 입니다.

Queue 는 배열로 따지면, 가장 앞에 있는 요소를 삭제하는 것인데...
이러면 후 작업이 앞으로 다 당겨줘야 합니다. 굉장히 비효율적이죠.
그래서 이런 배열의 단점을 커버한 것이 LinkedList 입니다. LinkedList는 Link만 변경 해주면 되기 때문에
뒤에 있는 요소들을 당길 필요가 없습니다. 그래서 LinkedList는 Queue를 구현 하였습니다.

그래서 어디서 사용하지??

저는 개발하면서 Stack, Queue를 아직까지는 써 본 적이 없습니다. 하지만 많이 쓰인다고 하네요.
간단하게 예만 들겠습니다.

Stack

• 열린 괄호, 닫힌 괄호 등 수식 계산
  아래 코드 참고

Queue

• 최근 사용한 5개 문서 같은 것들.

최근 사용한 문서가 5개를 초과하면 가장 먼저 열었던 문서(가장 먼저 저장된 요소)를 삭제하면 되기 때문에 Queue를 사용하면 간편하게 할 수 있습니다.