00. 배열 | 큐 | 스택

📌 배열 (Array)

정의

데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구상한 데이터 구조

 

배열이 왜 필요할까 ?

- 같은 종류의 데이터를 효율적으로 관리하기 위해 사용

- 같은 종류의 데이터를 순차적으로 저장 (인덱스가 존재)

- 문자열과 같은 경우 순차적으로 저장되어 있어야 효율적으로 관리 될 수 있다

- 인덱스를 통해서 연결된 데이터의 일부분을 바로 접근할 수 있다

 

장점

빠른 접근 가능
: 배열의 첫번째 위치만 알면 인덱스를 통해 몇번째 만큼 떨어진 곳으로 바로 접근 가능

 

단점

추가 / 삭제가 쉽지 않다
  삭제하는 경우 필요없는 공간을 가지고 있어야 한다

미리 최대의 길이를 지정해야 한다
  고정된 길이 <-> 가변적

`JAVA` 라는 문자열을 저장하기 위해 미리 4정도의 크기를 갖는 배열을 생성해놓아야 한다

 

배열은 추가가 되지 않기 때문에 새로운 배열을 만든 후 기존 배열값을 넣어준 뒤 값을 새로 넣어주어야 한다

// 배열을 잘라내는 Arrays 클래스가 존재한다 (기존 배열의 필요한 부분을 잘라 새로운 배열을 만드는 원리)
Arrays.copyOfRange(배열, 시작 인덱스, 종료 인덱스)

 

---

📌 큐 (Queue)

정의

- 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조

- 예시) 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일

- FIFO (First In First Out) 구조

- 스택과 반대되는 구조이다 ( 스택은 FILO 구조 )

 

사용되는 용어

- Enqueue : 큐에 데이터를 넣는 기능

- Dequeue : 큐에 데이터를 꺼내는 기능

 

종류

- Queue : 가장 일반적인 큐 자료구조

- Lifo Queue : 나중에 입력된 데이터가 먼저 출력되는 구조 (스택구조와 같음 FILO)

- Priority Queue : 데이터 마다 우선순위를 넣어서 우선순위가 높은 순으로 데이터 출력

 

어디에 많이 쓰일까 ?

- 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용됨 (운영체제 참고)
  > 큐의 경우에는 장단점보다는 특별히 언급되는 장단점이 없음

- 큐의 활용 예로 프로세스 스케줄링 방식을 함께 이해해두는 것이 좋다

Queue 구조

---

📌 스택 (Stack)

정의

- 데이터를 제한적으로 접근할 수 있는 구조
   - 한 쪽 끝에서만 자료를 넣거나 빼낼 수 있는 구조

- 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조

- LIFO 구조

- 대표적인 스택의 활용으로 컴퓨터 내부의 프로세스 구조의 함수 동작 방식이다

Stack 구조

주요 기능

- push : 데이터를 스택에 넣기

- pop : 데이터를 스택에서 꺼내기

 

스택구조와 프로세스 스택

- 스택구조는 프로세스 실행 구조의 가장 기본적으로 사용된다

- 함수 호출 시 실행 구조를 스택과 비교해서 이해필요

- 참고) 프로그램이 실행되는 상태를 프로세스 라고 한다

function recursive(num) {
  if (num < 0) console.log('ended')
  else {
    console.log(num)
    recursive(num-1)
    console.log('returned num')
  }
}

recursive(4)

 

장점

구조가 단순해서 구현이 쉽다
(구조가 단순하기 때문에 일반적으로) 데이터 저장/읽기 속도가 빠르다
   - 일반적으로 그렇지 구현 로직을 다르게 하면 빠르지 않을 수 도 있다

 

단점

데이터 최대 갯수를 미리 정해야 한다
  - 재귀함수 사용할 수 있는 크기는 다 정해져있어서 특정 크기를 넘어가면 에러가 발생한다
  - 구현을 다르게 하면 최대 갯수를 지정할 필요는 없기도 함

(최대 갯수를 미리 정해야 하기 때문에) 저장 공간의 낭비가 발생할 수 있다
  - 최대 갯수만큼 함수를 모두 작성하지 않기 때문
  - 1000번의 크기 함수를 만들어놨지만, 해당 재귀함수는 2번만 끝나는 경우 998개의 저장공간 낭비가 발생

 

- 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열구조를 활용해서 구현하는 것이 일반적임

이 경우 위에서 배열의 특징때문에 위에서 열거한 단점을 갖고 있는 것
(배열은 크기를 지정해야하고 가변적으로 크기를 늘리기 어렵기 때문)