쓰이는 자료구조 - Array, Stack, Queue

쓰이는 자료구조 - Array, Stack, Queue

 

모든 학문이 그렇듯, CS(Computer Science)역시 base가 잘 잡혀있어야 그를 기반으로 응용해나갈 수 있다. 백엔드 개발을 예로 들어볼까. 유저(클라이언트)를 대상으로 어떤 서비스를 제공하는 시스템을 개발하고 싶다. 그러기 위해선, 시스템을 구축하기 위한 Framework 기술을 알아야하고, 이를 배포 및 운영할 수 있는 Server 지식도 알아야하며, 데이터 관리를 위한 기술도 알아야한다. 그 중에서 가장 중요한 내용은 뭘까. 우리의 목표는 고객을 대상으로 "서비스"를 제공하는 것이라 했는데, 앞서 말했던 정보들은 서비스를 제공하기 위한 "수단"으로써 필요한 내용들이다. 본질은 "서비스"이다. 이 서비스를 비지니스 로직에 따라 처리될 수 있도록 구현하는 능력. 이는 자료구조 및 알고리즘에서부터 시작한다. 이 지식이 탄탄해야 더 나아가 성능적인 측면에서도 효율적인 개발을 할 수 있다. 시간에 쫓기며 개발을 하다보면 성능 적인 측면은 간과하고 넘어가는 케이스가 종종 있는데, 그러다 문득 중요한 것을 잊고 개발하고 있다는 생각이 들었다. 그렇게 시작한 포스팅이 바로 "쓰이는" 시리즈이다.

 

---

 

1. Queue

 

1-1. Queue, 도대체 뭔데?

- 가장 먼저 넣은 데이터를 가장 먼저 꺼내어 쓸 수 있는 데이터 구조(FIFO)

- 어떤 시간 적인 흐름에 따라 순차적으로 데이터를 처리해야할 때(대표적으로는 시뮬레이션) 사용되는 자료구조

 

1-2. Queue, 어떻게 쓰는데?

- Queue, PriorityQueue 라이브러리 활용

- Priority Queue: 각각의 데이터마다 우선순위를 부여해서, 우선순위가 높은 순으로 데이터를 추출하는 방식(FIFO가 아님)

여기서 우선순위란  '정렬한 가능한 값의 크기'를 의미하므로 PriorityQueue의 type은 반드시 Comparable 인터페이스를 구현한 객체여야한다.

 

// int형 Queue생성
Queue<Integer> queue = new LinkedList<>();

// enqueue(데이터 추가)
queue.add(i);

// dequeue(데이터 추출)
queue.poll();

// 제일 위에 있는 데이터 확인
queue.peek();

// 사이즈 확인
queue.size();

// 초기화
queue.clear();


// int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

// Comparable인터페이스를 구현한 객체형 priorityQueue 선언
public class Person implements Comparable<Person>{
	public int code;
	public int cnt;
    public Person(int code, int cnt) {
    	this.code = code; this.cnt = cnt;
    }
    @Override
    public int compareTo(Person o) {
    	// TODO Auto-generated method stub
        if(o.cnt > this.cnt) return 1;
        else if(o.cnt < this.cnt) return -1;
        else {
          if(o.code < this.code) return 1;
          else return -1;
   		}
	}
}
PriorityQueue<Person> priorityQueue = new PriorityQueue<>();

 

1-3. Queue, 어디에 쓰일까?

- 운영체제: 멀티 태스킹을 위한 스케줄링 방식 구현

- 시뮬레이션

 

실제 문제를 해결한 사례를 보고 싶은 경우, [코딩테스트준비 - 큐] 를 클릭해주길 바란다.

 

---

2. Stack

 

2-1. Stack, 도대체 뭔데?

- 가장 마지막에 넣은 데이터를 가장 먼저 꺼내어 쓸 수 있는 데이터 구조(LIFO)

- 장점: 데이터 저장/읽기 속도가 빠르다.

- 단점: 데이터 최대 갯수가 미리 정해져있다. 따라서 저장 공간의 낭비가 발생할 수 있다.

 

2-2. Stack, 어떻게 쓰는데?

- Stack 라이브러리 활용

// int형 Stack생성
Stack<Integer> stack = new Stack<>();

// push(데이터 추가)
stack.push(i);

// pop(데이터 추출)
stack.pop();

// 제일 위에 있는 데이터 확인
stack.top();

// 사이즈 확인
stack.size();

// 복제
stack.clone();

 

2-3. Stack, 어디에 쓰일까?

- 컴퓨터 내부 프로세스 구조의 함수 동작 방식

  (1번 함수 호출 -> 2번 함수 호출 -> 2번 함수 리턴 -> 1번 함수 리턴)

 

실제 문제를 해결한 사례를 보고 싶은 경우, [코딩테스트준비 - 스택] 을 클릭해주길 바란다.