코드 스테이츠 - 자료구조 1(Stack/ Queue)

자료 구조

자료 구조란?

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

 

데이터는 필요에 따라 데이터의 특징을 잘 파악(분석)하여 정리하고, 활용하는 것이 중요하다.

데이터를 정해진 규칙 없이 저장하거나, 하나의 구조로만 정리하고 활용하는 것보다 데이터를 체계적으로 정리하여 저장해 두는 것이, 데이터를 활용하는데 있어 훨씬 유리하다.

 

수많은 개발자들이 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 여러 방법을 연구했다.

자료구조의 종류와 구분

대부분의 자료 구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.

많은 자료 구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료 구조를 빠르고 정확하게 적용해 문제를 해결할 수 있다.

 

 

Stack

Stack이란?

Stack은 사전적으로 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다.

자료구조 Stack 도 사전적 의미 그대로 데이터(Data)를 순서대로 쌓는 자료구조이다.

 

예를 들어, 프링글스과자통을 생각하면 이해하기 쉽다.

감자칩이 들어가는 순서대로 쌓이게 되고 감자칩을 꺼내려고 한다면, 가장 늦게 들어갔던 감자칩이 가장 먼저 나오게 된다.

여기서 감자칩을 데이터라고 생각하면 이해하기 Stack 구조를 이해하기 쉽다.

Stack의 후입 선출 과정

 

Stack의 특징 

 

1. LIFO(Last In First Out)

Stack 자료 구조는 가장 먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조를 가지고있다.

Stack<Integer> stack = new Stack<>(); //Integer형 스택 선언
// 1, 2, 3, 4를 스택에 차례대로 넣습니다.
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

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

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

---------------------------
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.

// 스택이 비어 있는지 확인할 때는 empty 연산을 사용합니다.
stack.empty(); // true 반환

 

2. 데이터는 하나씩 넣고 뺄 수 있다.

Stack 자료 구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고 뺀다. 한번에 여러 개를 넣거나 뺄 수 없다.

 

3. 하나의 입출력 방향을 가지고 있다.

Stack 자료 구조는 데이터의 입출력 방향이 같다. 입출력 방향이 여러 곳 이라면, Stack 자료 구조라고 볼 수 없다.

 

 

Stack 자료 구조의 장점

 

1. 스택은 후입선출(LIFO) 구조를 가지기 때문에, 스택에 저장된 데이터를 가져오는 속도가 매우 빠르다.

후입선출(LIFO) 구조는 삽입과 삭제가 항상 스택의 맨 위에서 이루어지기 때문에, 데이터를 삽입하거나 삭제할 때, 다른 데이터의 위치를 변경할 필요가 없다. 따라서 모든 데이터를 순회할 필요가 없기 때문에 스택의 크기와는 상관없이 매우 빠르게 처리된다.

 

 

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

자바에서는 이미 Stack이 구현되어 있기 때문에 따로 구현할 필요가 없다. 자료 구조의 특징과 메서드를 활용할 수있다면, 구현된 Stack 클래스를 바로 사용할 수 있다.

Stack<Integer> stack = new Stack<>(); //Integer 타입을 요소로 가지는 스택 선언

stack.push(1); // 스택에 새로운 데이터를 추가할 때는 push 연산을 사용합니다.
---------------------------
stack -> [1]
---------------------------

stack.push(2); 
---------------------------
stack -> [1, 2]
---------------------------

stack.push(3); 
---------------------------
stack -> [1, 2, 3]
---------------------------

stack.pop(); // 스택에서 가장 위에 있는 데이터를 제거할 때는 pop 연산을 사용한다.
---------------------------
stack -> [1, 2]
---------------------------

stack.pop(); 
---------------------------
stack -> [1]
---------------------------

 

 

Stack 자료 구조의 단점

 

1. 크기 제한이 없다.

스택은 데이터를 저장할 때 크기가 제한되지 않기 때문에, 메모리 사용량이 불필요하게 증가할 수 있다.

이러한 문제는 스택의 크기를 미리정해놓거나, 동적으로 크기를 조절하는 방법 등으로 해결할 수 있다.

 

2. Stack 클래스는 Vector 클래스를 상속받아 구현되어 있어, 크기를 동적으로 조정하지 않는다.

    (Java에서 제공하는 Stack 클래스 한정)

Vector 클래스는 내부적으로 배열을 사용하여 구현되어 있다. 이 배열의 크기는 처음에 지정된 크기만큼만 할당되고, Stack에 저장되는 데이터 개수가 배열의 크기를 초과하면, 새로운 배열을 할당하고, 기존 데이터를 새로운 배열로 복사하는 작업을 수행한다. 

이러한 작업들은 성능에 영향을 미치기 때문에, 크기가 자주 변하는 Stack에서는 다른 자료 구조를 사용하는 것이 더 효율적일 수 있다.

 

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);
  }
}

 

3. Stack 클래스는 Vector 클래스를 상속받아 구현되어 있어, 중간에서 데이터를 삽입, 삭제를 할 수 있게 된다. 

    (Java에서 제공하는 Stack 클래스 한정)

Stack 클래스는 Vector 클래스를 상속받아 구현되어 있어, Vector 클래스의 모든 메서드를 상속받아 사용할 수 있다.

하지만, Stack 클래스에서는 Vector 클래스에서 상속받은 메서드 중에서 일부 메서드를 오버라이딩하여 구현하고 있다.

이러한 구현 방식은 스택의 의도된 동작을 방해할 수 있기 때문에, 해당 클래스를 사용할 때 주의가 필요하다.

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란?

Queue는 사전적 의미로 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다.

자료 구조의 Queue도 데이터(data)를 줄세워 기다리게 하는 자료구조이다.

 

예를 들어 맛집 대기줄을 생각하면 이해하기 쉽다.

맛집에서 밥을 먹기위해 손님들이 줄을 서게되면, 가장 먼저 온 손님이 가장먼저 입장하게 된다.

여기서 손님을 데이터라고 생각하면 이해하기 쉽다. Queue는 주로 데이터가 입력된 순서대로 처리할 때 사용된다.

 

 

Queue의 특징 

 

1. FIFO(First In First Out) / LILO(Last In Last Out)

Queue는 Stack과는 반대로 먼저 들어간 데이터가 먼저 나오게 되는 FIFO(First In First Out) 혹은

늦게 들어간 데이터가 늦게 나오게 되는 LILO(Last In Last Out)을 특징으로 가지고있다.

예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 자료 구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺀다. 한번에 여러 개를 넣거나 뺄 수 없다.

 

3. 두 개의 입출력 방향을 가진다.

Queue 자료 구조는 데이터의 입력, 출력 방향이 다르다. 만약 입출력 방향이 같다면 Queue 자료 구조라고 볼 수 없다.

 

 

Queue 자료 구조의 장점

 

1. 데이터를 먼저 넣은 순서대로 꺼내서 처리할 수 있다. 이러한 자료 구조의 특징으로 처리해야 할 작업이 여러 개 있을 경우, 효율적인 처리가 가능하다.

Queue는 선입선출(FIFO) 원칙을 따르기 때문에, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되고, 가장 나중에 삽입된 데이터는 가장 나중에 삭제된다. 이러한 구조로 인해, 처리해야 할 데이터나 작업을 차례대로 처리할 수 있다.

 

Queue의 가장 앞(front)에서는 가장 오래전에 삽입된 데이터가 위치하고, 가장 뒤(rear)에서는 가장 최근에 삽입된 데이터가 위치한다. 즉, Queue에 데이터를 삽입하는 순서와 삭제하는 순서가 동일하게 유지되어야 한다.

이러한 구조는 데이터 처리나 작업 처리에서 순서가 중요한 경우에 유용하다.

 

2. Queue는 삽입과 삭제가 각각 양 끝에서 이루어지며 원소를 삭제하는 연산이 없으므로, 다른 자료 구조에 비해 상대적으로 빠른 속도를 보인다.

Queue의 삽입과 삭제는 각각 Queue의 끝단에서 이루어지기 때문에, 중간에 있는 원소를 삭제하는 연산이 없다.

 

배열의 경우, 중간에 있는 원소를 삭제하려면 삭제한 원소 이후의 모든 원소를 한 칸씩 앞으로 이동시켜야 한다.

이 때문에 중간의 원소를 삭제한다면, 이후의 배열을 복사하고 다시 순회하며 데이터를 삽입하는 과정을 거쳐야 한다.

삭제한 원소 뒤에 새로운 원소를 삽입하려면 빈자리를 만들기 위해 이후의 원소들을 한 칸씩 뒤로 밀어야 하므로 삽입 연산에서도 전체 배열을 순회해야 한다.

 

반면, Queue에서는 삽입 연산은 Queue의 끝단에서 새로운 원소를 추가하는 것으로 끝나며, 삭제 연산은 Queue의 첫 번째 원소를 삭제하는 것으로 끝난다. 따라서, Queue에서의 삽입과 삭제 연산은 단 한 번의 실행만으로 처리할 수 있다

이러한 이유로 Queue는 삽입과 삭제가 빈번하게 일어나는 상황에서 상대적으로 빠른 속도를 보이며, 데이터나 작업을 차례대로 처리해야 하는 상황에서 효과적으로 사용될 수 있다.

 

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

자바에서는 이미 Queue 클래스가 구현되어 있기 때문에 따로 구현할 필요가 없다. 자료 구조의 특징과 메서드를 활용할 수있다면, 구현된 Queue 클래스를 바로 사용할 수 있다.

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

queue.offer(1); // 큐에 새로운 데이터를 추가할 때는 add 메서드를 사용합니다.
---------------------------
queue -> [1]
---------------------------
queue.offer(2); 
---------------------------
queue -> [1, 2]
---------------------------
queue.offer(3); 
---------------------------
queue -> [1, 2, 3]
---------------------------

queue.poll(); // 큐에서 가장 처음에 들어온 데이터를 제거할 때는 poll 메서드를 사용합니다.
---------------------------
queue -> [2, 3]
---------------------------
queue.poll(); 
---------------------------
queue -> [3]
---------------------------

 

 

Queue 자료 구조의 단점

 

1. Queue는 자료 구조의 가장 앞에서 데이터를 꺼내는 연산과 가장 뒤에서 데이터를 추가하는 연산만 가능하기 때문에, 중간에 있는 데이터를 조회하거나 수정하는 연산에는 적합하지 않다.

Queue는 데이터를 가장 먼저 추가한 위치에서부터 차례로 데이터를 처리하며, 가장 나중에 추가된 위치에서 새로운 데이터를 추가한다. 이러한 구조 때문에 Queue는 특정 위치의 데이터를 조회하거나 수정하는 연산에 적합하지 않다.

 

즉, Queue에서는 가장 앞에서 dequeue 연산(add)으로 데이터를 삭제하거나, 가장 뒤에서 enqueue 연산(poll)으로 데이터를 추가하는 것만 가능하다. Queue는 다른 위치의 데이터에 직접 접근하여 데이터를 변경하는 연산이 불가능하며, 중간에 있는 데이터를 조회하는 것도 불가능하다. 따라서 Queue는 데이터를 순차적으로 처리하는 데 적합한 자료 구조이다.

 

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

Queue 인터페이스는 크기 제한이 없는 큐를 구현할 수 있도록 설계되어 있다. 이는 메모리 낭비의 가능성을 높인다.

크기 제한이 있는 큐를 구현할 때는, 이를 직접 구현하거나 기존의 Queue 인터페이스를 상속받아 크기 제한을 추가한 클래스를 구현해야 한다.

 

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

Queue 인터페이스는 iterator() 메서드를 지원하지 않는다. Queue 인터페이스가 FIFO(First-In-First-Out) 구조를 갖기 때문이다. 따라서 큐의 데이터를 순회할 때는, peek() 메서드와 poll() 메서드를 사용하여 각각의 데이터를 차례대로 가져와야 한다.

 

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

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