5. 자료구조

Array

• 특징: 순차적으로 데이터를 저장하고 index를 사용해 특정 요소를 찾고 조작이 가능, 크기가 고정적, 초기화 시 메모리에 할당되어 속도가 빠름
• 단점: 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤 모든 요소들이 한 칸씩 뒤로 밀거나 당겨줘야 한다. 삽입/삭제가 느리다.
• 장점: 새롭게 추가되거나 삭제되지 않고 순서대로 저장되어야 하는 데이터에 적합, 검색이 빠르다.

Stack

• Last In First Out
• 지역변수와 매개변수 데이터 값이 저장되는 영역으로 메소드 호출 시 메모리에 할당되며 종료되면 메모리에서 해제

public class Stack {
	private static int MAX_STACK_SIZE = 10;
    private int top;
    private int[] data = new int[MAX_STACK_SIZE];
    
    public Stack() {
    	top = -1;
    }
    
    public void push(int data_) throws Exception {
    	if (isFull()) {
     		throw new Exception("스택이 가득 찼습니다.");   
        }
        data[++top] = data_;
    }
    
    public int pop() throws Exception {
    	if (isEmpty()) {
        	throw new Exception("스택이 비었습니다.");
        }
        return data[top--];
    }
    
    public int peek() throws Exception {
    	if (isEmpty()) {
        	throw new Exception("스택이 비었습니다.");
        }
        return data[top];
    }
    
    public boolean isEmpty() {
    	return top == -1;
    }
    
    public boolean isFull() {
    	return top == MAX_STACK_SIZE - 1;
    }
    
    public int size() {
    	return top + 1;
    }

Queue

• First In First Out
• 메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인지의 순서를 결정

Hash Table

• key, value 형태로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다.
• 각 key 값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있게 되어 평균 O(1) 시간 복잡도로 데이터를 조회한다.
• 병렬 처리를 할 때 Thread-safe 하고 Null 값을 허용하지 않는다.