Do it 자료구조와 함께 배우는 알고리즘 입문 - 스택과 큐

1. 스택

데이터를 일시적으로 쌓아 놓는 자료구조, 후입선출 LIFO(Last In First Out)이다.
가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

• push : 스택에 데이터를 넣는 작업
• pop : 스택에서 데이터를 꺼내는 작업이다.
• top : push와 pop이 이루어지는 곳

스택 포인터 ptr : 스택에 쌓여 있는 데이터 수를 나타내는 필드이다.

- 푸시 메서드 push

스택에 데이터를 푸시한다. 스택이 가득 차서 푸시할 수 없는 경우 예외를 내보낸다.

public int push(int x) throws OverflowIntStackException {
	if (ptr >= capacity) // 스택이 가득 찬 상태
    	throw new OverflowIntStackException();
    return stk[ptr++]=x; // 비어있으니 ptr++한다. 
}

- 팝 메서드 pop

public int pop() throws EmptyIntStackException {
	if(ptr <= 0)
    	throw new EmptyInStackException();
    return stk[--ptr];
}

- 피크 메서드 peek

스택이 비어있지 않으면 stk[ptr-1]의 값을 반환한다.

public int peek() throws EmptyIntStackException {
	if(ptr <= 0) //스택이 0이면 예외처리를 한다.
    	throw new EmptyIntStackException();
    return stk[ptr-1]; 
}

- 모든 요소를 삭제하는 메서드 clear

public void clear() {
	ptr=0;
}

- 검색 메서드

public int indexOf(int x) {
	for(int i=ptr-1; i>=0; i--) //꼭대기 쪽부터 선형검색 한다.
    	if(stk[i]==x)
        	return i; // 검색 성공
        return -1; // 검색 실패
}

// 스택 용량 반환
public int getCapacity() {
	return capacity
}
        

2. 큐

스택과 마찬가지로 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 (FIFO : First In First Out)점이 스택과 다르다.

• 인큐 (en-queue)
  큐에 데이터를 넣는 작업
  시간복잡도 : O(1)

// 큐에 데이터를 인큐 
public int enque(int x) throws OverflowIntQueueException {
	if(num >= capacity)
    	throw new OverflowIntQueueException(); // 큐가 가득 참
    que[rear++]=x;
    num++;
    if (rear == capacity)
    	rear =0;
    return x;
}

• 디큐 (de-queue)
  데이터를 꺼내는 작업
  시간복잡도 : O(n)

public int deque() throws EmptyIntQueueException {
	if(num <=0 )
    	throw new EmptyIntQueueException(); // 큐가 비어 있다.
    int x=que[front++];
    num--;
    if(front == capacity)
    	front=0;
    return x;
}

• front : 데이터가 나오는 쪽
• rear : 데이터를 넣는 쪽

링 버퍼로 큐 만들기

배열의 맨 뒤가 맨 앞과 연결되었다고 보는 자료구조이다.
어떤 요소가 맨 앞의 요소이고 어떤 요소가 맨 뒤의 요소인지 식별하기 위한 변수

• front : 논리적인 맨 앞 요소의 인덱스
• rear : 맨 뒤 요소 하나 뒤의 인덱스를 저장하는 필드이다. (다음 요소를 인큐할 위치의 인덱스)

프런트 값과 리어값을 업데이트 하면서 인큐, 디큐를 수행한다 O(1)이다.

public class IntArrayQueue {
    private int[] que;
    private int capacity; // 큐의 용량
    private int front; // 맨 앞의 요소 커서
    private int rear; // 맨 뒤의 요소
    private int num; // 현재 데이터 개수

    // 큐가 비어 있다.
    public class EmptyIntQueueException extends  RuntimeException {
        public EmptyIntQueueException() {

        }
    }

    // 실행 시 예외 -> 큐가 가득 찬다.
    public class OverflowIntQueueException extends  RuntimeException {
        public OverflowIntQueueException(){

        }
    }

    // 생성자를 만들어 준다.
    public IntArrayQueue(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen; //만큼 큐의 용량을 넣어준다.
        try {
            que = new int[capacity]; //큐의 본체 배열을 생성한다.
        }catch (OutOfMemoryError e){ //배열을 생성할 수 없다.
            capacity = 0;
        }

    }
}

값이 가득 찼을 때 num값과 capacity값은 같다.
front = rear값이 같을 경우에도 큐의 상태가 비어 있는지, 아닌지 구분할 수 있다.
매개변수 maxlen도 capacity용량과 같은 값을 넣어준다.

• OverflowIntQueueException
  큐가 가득 차서 in-queue할 수 없을 경우 = num >= capacity

queue생성

public int queue(int x) throws OverflowIntQueueException {
        if (num>=capacity)
            throw new OverflowIntQueueException(); // 큐가 가득 찼기 떄문에 OverflowIntQueueException을 실행
        // in-queue 하기
        que[rear++] = x;
        num++; // 현재 데이터의 개수를 더한다.
        if (rear == capacity) // 용량이 꽉 찼을 경우 rear배열의 첫 인덱스인 0으로 변경한다.
            rear = 0;
        return x; // x값을
    }

deque

public int deque() throws EmptyIntQueueException {
        // 큐가 비어있을 경우 -> 디큐를 할 수 없다.
        if (num <= 0)
            throw new EmptyIntQueueException();
        // rear를 앞당기기 떄문에 front가 증가된다.
        int x = que[front++];
        num--;
        // 예외처리
        if (front == capacity)
            front = 0;
        return x;
    }

peek

  public int peek() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();
        return que[front];
    }