Java의 Stack과 Queue 들여다보기

✅ Stack

Stack은 저장 순서와 접근 순서가 반대되는 자료구조입니다.
처음 삽입한 데이터일수록 접근 순서가 멀어지고, 가장 최근 삽입한 데이터의 접근 순서가 더 빠릅니다.
이것을 줄여서 후입선출이라고 이야기합니다.
Java에서의 Stack은 Vector를 상속받고, 부모 클래스 Vector에 선언된 Object 배열 객체에 데이터를 저장합니다.

(1) 추가 (push)
저장되는 데이터가 많아지면, 배열 특성상 미리 크기가 정해져있기 때문에 저장 공간이 부족해질 수 있습니다.
따라서 새로운 데이터가 추가될 때 배열의 크기가 충분한지 확인한 후, 저장할 공간이 부족하면 기존 배열 크기의 두 배 사이즈의 공간을 할당하고 기존에 선언되어 있던 배열의 데이터를 복사합니다.
Stack의 후입선출 특성으로 인하여, Stack에서 실제 데이터를 가지고 있는 내부 배열의 가장 마지막에 새로운 데이터를 저장합니다.
Stack의 최대 크기는 Integer의 최댓값(2^31 -1)에서 8을 뺀 MAX_ARRAY_VALUE를 상수를 따로 가지고 있습니다.
JVM 구현체에 따라 다르지만, 배열 객체에 8사이즈의 헤더가 포함되는 경우가 있어서 해당 값 만큼 차이가 있습니다.

(2) 삭제 (pop)
Stack의 후입선출 특성으로 인하여, Stack에서 실제 데이터를 가지고 있는 내부 배열의 가장 마지막에 새로운 데이터를 삭제합니다.
메소드 pop()는 내부적으로 Vector의 특정 위치의 요소를 삭제하고, 빈 공간을 남기지 않기 위해 삭제한 인덱스 뒷 쪽의 데이터를 공간없이 앞으로 당기는 작업을 합니다.
하지만, Stack은 배열의 가장 뒷쪽에서만 데이터 추가, 삭제가 이루어지기 때문에 배열이 복사되지 않고, 마지막 인덱스의 메모리 해제만 이루어집니다.

(3) 접근(peek)
가장 최근 삽입한 데이터에 접근합니다.

(4) 검색 (search)
데이터가 저장된 배열의 마지막 인덱스부터 0까지 검색한다. 배열에 중복되는 참조값이 있다면, 처음 발견하는, 가장 최근에 삽입한 위치를 리턴합니다.

▶ Stack과 Vector의 관계
둘 다 순차적인 요소를 다루기 위한 자료구조 - Stack의 메소드는 내부적으로 Vector의 메소드를 사용하고 있습니다.
Vector의 배열에 기반한 자료구조를 사용하기 위하여 상속받습니다. (배열의 크기가 부족하면 늘리거나 데이터의 위치를 찾는 메소드가 Vector에서 상속받는 기능)
Stack은 스레드 논세이프, Vector는 스레드 세이프
또한 Vector는 Stack처럼 가장 최신 데이터만 접근하는 것이 아닌 더 범용적인 메소드를 구현하고 있습니다.

✅ Queue

Queue는 저장순서와 접근순서가 동일한 자료구조입니다.
빨대의 앞과 뒤를 정하고, 뒤로 작은 구슬 하나를 흘려보내면 반대쪽인 앞에서 해당 구슬을 꺼낼 수 있습니다.
이처럼 뒤로 삽입한 순서대로 앞쪽에서 접근할 수 있습니다. 이것을 선입선출이라고 이야기합니다.
Java에서 Queue는 Queue 인터페이스에서 선언되어 있는 메소드를 LinkedList의 구현체를 사용합니다.
(구현체가 배열이었다면 앞 인덱스에서 삭제되는 경우 앞으로 당겨주어야 했을 것이고, 빈 공간으로 남겨놓는 문제가 생겼을 것입니다.)

괄호는 (예외, 값 리턴) 순서
(1) 추가(add, offer)
LinkedList는 다음 노드의 주소를 참조하는 방식으로 연결되어 있습니다.
새로운 데이터를 삽입하는 경우, 가장 마지막 순서에 있던 노드에서 새로 생성한 노드를 참조하도록 합니다.

(2) 삭제(remove, poll)
선입선출이기 때문에 접근과 삭제 모두 큐의 첫번째 데이터를 사용합니다. 내부적으로 첫번째 노드를 가르키고 있던 참조값을 두번째 노드로 옮기고, 삭제할 첫번째 노드가 가지고 있던 데이터와 다음 노드 참조를 삭제하여 Queue에서 사라집니다.

(3) 접근(element, peek)
선입선출이기 때문에 큐의 첫번째 데이터에 접근합니다.

* Java에서 Stack은 Vector 클래스를 상속받는 자식 클래스이고, Queue는 인터페이스이다.