자주 등장하는 네 가지의 자료 구조(Stack, Queue, Tree, Graph)

박두팔이·2023년 12월 26일

Graph queue stack tree

자바

목록 보기

26/26

자료구조의 정의

데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것

자료구조를 배워야 하는 이유?

대부분의 자료 구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다. 따라서 많은 자료 구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료 구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.

Stack

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다.

쌓인 접시들을 예시로 들면 이해하기 쉬움
접시들이 쌓여있을 때 가장 나중에 맨 위의 접시가 가장 먼저 나가게 됨.
FILO(First In Last Out, 후입선출)
하나의 입출력 방향을 가지고 있기 때문
Stack에 데이터를 넣는 것: Push / 꺼내는 것: Pop
데이터는 하나씩 넣고, 하나씩 뺄 수 있다. 한번에 여러개 넣거나 뺄 수❌

예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다.

Stack<Integer> stack = new Stack<>(); //Integer형 스택 선언

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 스택이 빌 때까지 데이터를 전부 빼냅니다.

stack.pop();
stack.pop();
stack.pop();
stack.pop();

---------------------------
4, 3, 2, 1
---------------------------

제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.

예3) 스택이 비어 있는지 확인할 때는 empty 연산을 사용합니다.

stack.empty(); // true 반환

Stack 장점?

후입선출의 구조를 가지기 때문에 저장된 데이터를 가져오는 속도가 매우 빠르다.
자바에서는 스택을 기본 자료 구조로 제공하기 때문에, 별도의 라이브러리나 모듈을 설치할 필요가 없다.

Stack 단점?

데이터 저장시 크기 제한이 없다.
- 메모리 사용량이 불필요하게 증가할 수 있음
- 스택의 크기를 미리 정해놓거나, 동적으로 코기를 조절하는 방법을 사용하면 됨

JAVA에서 제공하는 Stack 특징?

1. Stack클래스는 Vector클래스를 상속받아 구현되어 있다. 따라서 크기를 동적으로 조정하지 않는다.
- Vector클래스는 내부적으로 배열을 사용하여 구현되어 있다.
- 지정된 크기만큼 배열이 할당된 후, 데이터의 개수가 배열의 크기를 초과하면 새로운 배열을 할당한다.
- 이후, 기존 데이터를 새로운 배열로 복사하는 작업을 수행한다.
- 따라서 크기가 자주 변하는 스택에서는 다른 자료 구조를 사용하는 것이 더 효율적이다.

Vector 클래스의 생성자 코드

public Vector(Collection<? extends E> c) {
  Object[] a = c.toArray();
  elementCount = a.length;
  if (c.getClass() == ArrayList.class) {
    elementData = a;
  } else {
      elementData = Arrays.copyOf(a, elementCount, Object[].class);
  }
}

2. Java에서 제공하는 Stack클래스는 Vector클래스를 상속받아 구현되어 있어, 중간에서 데이터를 삽입, 삭제가 가능하다.
- Vector클래스의 모든 메서드를 상속받기에 당연히 Stack클래스는 상속받은 메서드 중 일부를 오버라이딩하여 구현이 가능하다.
- 스택의 의도된 동작을 방해할 수 있기 때문에 주의가 필요하다.

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

stack.get(1);            // 특정 인덱스 원소 찾기
stack.set(1, 1);         // 특정 인덱스에 원소 넣기
stack.remove(1);         // 특정 인덱스 원소를 삭제

주로사용되는 곳, 브라우저에서 뒤로 가기, 앞으로 가기 버튼을 사용할 때.

Queue

Queue는 줄을 서서 기다리다라는 뜻을 가지고 있다.

1. 선입선출의 구조를 가지고 있다.

Queue는 두개의 입출력 구조를 가지고 있다. 따라서 처음 삽입된 데이터가 먼저 삭제되고, 마지막에 삽입된 데이터가 가장 나중에 삭제된다. 따라서 처리할 작업을 순서대로 처리할 수 있다.
- 예를 들어, 프린터에서 인쇄 요청이 들어온 순서대로 처리해야 하는 경우
- 은행에서 대기 중인 고객 순서를 결정하는 경우
- 채팅 시스템에서 메시지를 보내는 순서를 결정하는 경우
  등에 Queue 자료 구조가 적용될 수 있다.
데이터는 하나씩 넣고 뺄 수 있다. 한꺼번에 여러 개를 넣거나 뺄 수 없다.

예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언

queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.add(3);     // queue에 값 3 추가
queue.add(4);     // queue에 값 4 추가

						   queue.add(데이터)
출력 방향 <---------------------------< 입력 방향
				     1 <- 2 <- 3 <- 4
				<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.

queue.poll();       // queue에 첫번째 값을 반환하고 제거
queue.poll();
queue.poll();
queue.poll();

						   queue.poll()
출력 방향 <---------------------------< 입력 방향

				<---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.

2. Queue는 중간원소를 삭제하는 연산이 없어서 속도가 빠르다.

Queue의 삽입과 삭제는 각각 Queue의 끝단에서 이루어지기 때문에, 중간에 있는 원소를 삭제하는 연산이 없다.
배열의 경우, 중간에 있는 원소를 삭제하려면 삭제한 원소 이후의 모든 원소를 한 칸씩 앞으로 이동시켜야 한다. 이 때문에 중간의 원소를 삭제한다면, 이후의 배열을 복사하고 다시 순회하며 데이터를 삽입하는 과정을 거쳐야한다.
반면, Queue에서는 삽입 연산은 Queue의 끝단에서 새로운 원소를 추가하는 것으로 끝나며, 삭제 연산은 Queue의 첫 번째 원소를 삭제하는 것으로 끝난다.
따라서, Queue에서의 삽입과 삭제 연산은 단 한 번의 실행만으로 처리할 수 있다.

3. 자바에서는 큐를 기본 자료구조로 제공하기 때문에, 별도의 라이브러리나 모듈을 설치할 필요가 없다.

3.1 queue.offer()

Queue 인터페이스에서 정의된 메서드로써 큐에 공간이 충분하지 않아서 요소를 추가할 수 없는 경우, 예외를 발생시키지 않고 false를 반환

Queue<Integer> queue = new LinkedList<>();
boolean result = queue.offer(1); // 실패하면 false 반환

3.2 add()

add() 메서드는 Collection 인터페이스에서 상속받은 메서드로, 큐에 요소를 추가한다.
그러나, 큐에 공간이 충분하지 않아서 요소를 추가할 수 없는 경우 IllegalStateException을 발생시킨다.

Queue<Integer> queue = new LinkedList<>();
queue.add(1); // IllegalStateException 발생 가능

3.3 poll()

queue.poll(); // 큐에서 가장 처음에 들어온 데이터를 제거

보통은 큐에 요소를 추가할 때 offer() 메서드를 사용하는 편이 좋다. add() 메서드는 예외를 발생시키므로, 예외 처리를 위한 추가적인 코드를 작성해야 합니다. offer() 메서드는 예외 없이 실패 시에도 처리가 가능하므로 더 유연하게 사용할 수 있다.

Queue 자료구조 단점

1. Queue는 중간에 있는 데이터를 조회하거나 수정하는 연산에는 적합하지 않다.

자료 구조의 가장 앞에서 데이터를 꺼내는 연산과 가장 뒤에서 데이터를 추가하는 연산만 가능하기 때문이다.

2. 크기 제한이 없어서 메모리의 낭비가 발생할 수 있다. (Java에서 제공하는 Queue 인터페이스의 경우)

Queue 인터페이스는 크기 제한이 없는 큐를 구현할 수 있도록 설계되어 있다.
따라서, 메모리 낭비의 가능성을 높인다.
크기 제한이 있는 큐를 구현할 때는, 이를 직접 구현하거나 기존의 Queue 인터페이스를 상속받아 크기 제한을 추가한 클래스를 구현하는 것이 좋다.

3. iterator() 메서드가 지원되지 않는다. (Java에서 제공하는 Queue 인터페이스의 경우)

큐의 데이터를 순회할 때는, peek() 메서드와 poll() 메서드를 사용하여 각각의 데이터를 차례대로 가져와야한다.

4. remove(Object o) 메서드의 동작이 불명확하다. (Java에서 제공하는 Queue 인터페이스의 경우)

Queue 인터페이스에서 제공하는 remove(Object o) 메서드는 해당 객체를 큐에서 삭제한다.
그러나 이 메서드는 큐가 중복된 객체를 허용하는 경우, 어떤 객체가 삭제되는지 명확하지 않다.
따라서 이 메서드를 사용할 때는 주의해야 합니다. 대신 poll() 메서드를 사용하여 원하는 객체를 삭제할 수 있다.

박두팔이

기억을 위한 기록 :>

이전 포스트