스택과 큐

데이터를 일시적으로 저장하기 위해 사용하는 자료구조

스택 (Stack)

데이터의 입출력 순서는 후입선출(LIFO, Last In First Out)이다.

푸시(Push) : 데이터를 넣는 작업
팝(Pop) : 데이터를 꺼내는 작업

코드 예시

// 실행 시 예외 - 스택이 비어 있음
public class EmptyStackException extends RuntimeException {
	public EmptyStackException(){ }
}

// 실행 시 예외 - 스택이 가득 참
public class OverflowStackException extends RuntimeException {
	public OverflowStackException () { }
}

// 스택에 x를 푸시(Push)
// ptr (포인터) : 스택에 쌓여 있는 데이터 요소의 개수
// capacity : 스택에 쌓을 수 있는 데이터 요소의 최대 개수
public int push(int x) throws OverflowStackException {
	if(ptr >= capacity) 
    	throw new OverflowStackException();
    return stack[ptr++] = x;
}

// 스택에서 데이터를 팝(Pop)
public int pop( ) throws EmptyStackException {
	if(ptr < 1 )
    	throw new EmptyStackException();
    return stack[--ptr];
}

큐 (Queue)

데이터의 입출력 순서는 선입선출(FIFO, First In First Out)이다.

인큐(Enqueue) : 큐에 데이터를 넣는 작업
디큐(Dequeue) : 큐에 데이터를 꺼내는 작업

프런트(Front) : 데이터를 꺼내는 쪽
리어(Rear) : 데이터를 넣는 쪽

인큐는 배열의 리어에 데이터를 단순히 넣기 때문에 적은 비용으로 구현할 수 있어 O(1)이지만, 디큐는 배열의 프런트에 있는 데이터를 꺼낸 뒤, 뒤에 있는 모든 요소들을 모두 앞으로 옮겨야하기 때문에 효율이 떨어지는 O(n) 복잡도를 갖게 된다.

private int ptr; // 데이터 요소의 개수
private int[] queue;
private int rear; 
prvate int front;
private int capacity;

public int enquequ(int x) throws OverflowQueueException{
	if(ptr >= capacity)
    	throw new OverflowQueueException();
    queue[rear++] = x;
    return x;
}

public int dequequ() throws EmptyQueueException{
	if(ptr < 1)
    	throw new EmptyQueueException();
    int x = queue[0];
    for(int i = 0; i < ptr - 1; i++)
    	queue[i] = queue[i+1];
    ptr--;
    return x;
}

//--- 큐에서 데이터를 피크(맨앞 데이터를 들여다봄 ) ---*/
public int peek() throws EmptyQueueException {
	if (ptr < 1)
      throw new EmptyQueueException();  // 큐가 비어 있음
    return queue[ptr - 1];
}

링 버퍼 (Ring Buffer)

위와 같은 일반적인 큐는 요소를 이동시키는 비용이 발생하게 된다.
이런 단점을 없애주는게 링 버퍼다.

배열의 처음이 끝과 연결되어 있는 구조로 처리의 복잡도는 O(1)이다.

private int front; // 첫번째 요소
private int rear; // 마지막 요소
private int ptr; // 현재 요소 개수
private int[] queue;

// 생성자
public Queue(int capacity) {
	// 맨 처음 배열이 비어있을 때는 프런트와 리어가 0으로 같다.
	ptr = front = rear = 0;
    try {
    	queue = new int[capacity];
    } catch (OutOfMemoryError e){
    	capacity = 0;
    }
}

public int enqueue(int x) throws OverflowQueueException {
	if(x >= capacity)
    	throw new OverflowQueueException();
    queue[rear++] = x;
    ptr++;
    if(rear == capacity)
    	rear = 0;
    return x;
}

public int dequeue() throws EmptyQueueException {
	if(ptr < 1)
    	throw new EmptyQueueException();
    int x = queue[front++];
    if(front == max)
    	front = 0;
    return x;
}

public int peek() throws EmptyQueueException {
	if(ptr < 1)
    	throw new EmptyQueueException();
    return queue[front];
}

// 큐 안의 모든 데이터를 삭제
public void clear(){
	ptr = front = rear = 0;
}

// 큐 안의 모든 데이터 출력 - rear 순으로
public void dump() {
	if(ptr < 1)
    	System.out.println("큐가 비어있습니다);
    else{
    	for(int i = 0; i < ptr; i++)
        	System.out.print(queue[(i + front) % capacity] + " ");
        System.out.println();
    }
}

링 버퍼는 '오래된 데이터를 버리는' 용도로 사용할 수 있다.
예를 들면 배열에 계속해서 새로운 데이터가 저장되서 오래된 데이터를 버려야 될 때 사용된다.

주의사항으로는 링 버퍼는 반드시 capacity보다 크면 안된다. 그렇게 되면 front가 rear보다 뒤에 배치되는 말도 안되는 구조가 되기 때문이다.