[Java] 스택과 큐

Do it! 자료구조와 함께 배우는 알고리즘 입문 읽고 정리

 

4-1 스택

스택이란?

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

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

- 스택에 데이터를 넣는 작업을 푸시라 하고, 꺼내는 작업을 팝이라고 한다.

 

스택 만들기

publi class IntStack {
	private int max; // 스택 용량
    private int ptr; // 스택 포인터
    private intp[ stk; // 스택 본체

	// 실행 시 예외: 스택이 비어있을 때
    public class EmptyIntStackException extents RuntimeExcetption {
    	public EmptyIntStackException(){}
    }
    
    // 실행 시 예외: 스택이 다 찼을 때
    public class OverflowIntStackException extends RuntimeException {
    	public OverflowIntStackException() {}
    }
    
    // 생성자
    public IntStack(int capacity) {
    	ptr = 0;
        max = capacity;
        try {
        	stk = new int[max]; // 스택 본체용 배열 생성
        } catch (OutofMemoryError e) {
        	max = 0;
        }
    }
    
    // 스택에 x를 푸시
    public int push(int x) throws OverflowIntStackException {
    	if (ptr >= max) throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }
	
    // 스택에서 데이터를 팝(가장 위의 데이터를 뺀다.)
    public int pop() throws EmptyIntStackException {
    	if (ptr <= 0) throw new EmptyIntStackException();
        return stk[--ptr];
    }
    
    // 스택에서 데이터를 피크(확인)
    public int peek() throws EmptyIntStackException {
    	if (ptr <= 0) throw new EmptyIntStackException();
        return stk[ptr-1];
    }
    
    // 스택에서 x를 찾아 인덱스를 반환(없으면 -1을 반환)
    public int indexOf(int x) {
    	for (int i = ptr -1; i >= 0; i--) {
        	if (stk[i] == x) return i; // 성공
        	return -1; // 실패
        }
    }
    
    // 스택 비움
    public void clear() {
    	ptr = 0;
    }
    
    // 스택의 용량 반환
    public int capacity() {
    	return max;
    }
	
    // 스택에 쌓여 있는 데이터 수 반환
    public int size() {
    	return ptr;
    }
    
    // 스택 비어있는지 확인
    public boolean isEmpty() {
    	return ptr <= 0;
    }
    
    // 스택이 가득 찼는지 확인
    public boolean isFull() {
		return ptr >= max;
    }
    
    // 스택의 모든 데이터를 가장 아래부터 위까지 출력
	public void dump() {
		if (ptr <= 0) System.out.println("스택 비어있음");
       	else {
        	for (int = 0; i < ptr; i++) {
           		System.out.print(stk[i] + " ");
           	}
            System.out.println();
        }
    }
}

 

4-2 큐

큐란?

- 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조

- 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out)

- 큐에 데이터를 넣는 작업을 인큐, 데이터를 꺼내는 작업을 디큐라고 한다.

- 큐에서 데이터를 꺼내는 쪽을 프론트, 데이터를 넣는 쪽을 리어라고 한다.

 

배열로 큐 만들기

스택과 마찬가지로 큐는 배열을 이용해서 만들 수 있다.

public class IntAryQueue {
	// 실행할 때 예외：큐가 비어 있음
	public class EmptyIntAryQueueException extends RuntimeException {
		public EmptyIntAryQueueException() {
		}
	}

	// 실행할 때 예외：큐가 가득 참
	public class OverflowIntAryQueueException extends RuntimeException {
		public OverflowIntAryQueueException() {
		}
	}

	private int max; // 큐의 용량
	private int num; // 현재의 데이터 수
	private int[] que; // 큐의 본체

	// 생성자
	public IntAryQueue_04_04(int capacity) {
	      num = 0;
	      max = capacity;
	      try {
	         que = new int[max];         // 큐 본체용 배열을 생성
	      } catch (OutOfMemoryError e) {   // 생성할 수 없습니다.
	         max = 0;
	      }
	   }

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

	// 큐에서 데이터를 디큐
	public int deque() throws EmptyIntAryQueueException {
		if (num <= 0)
			throw new EmptyIntAryQueueException(); // 큐가 비어 있음
		int x = que[0];
		for (int i = 0; i < num - 1; i++)
			que[i] = que[i + 1];
		num--;
		return x;
	}

	// 큐에서 데이터를 피크(머리 데이터를 살펴봄)
	public int peek() throws EmptyIntAryQueueException {
		if (num <= 0)
			throw new EmptyIntAryQueueException(); // 큐가 비어 있음
		return que[num - 1];
	}

	// 큐에서 x를 검색하여 index(찾지 못하면 -1)를 반환
	public int indexOf(int x) {
		for (int i = 0; i < num; i++)
			if (que[i] == x) // 검색성공
				return i;
		return -1; // 검색실패
	}

	// 큐를 비움
	public void clear() {
		num = 0;
	}

	// 큐의 용량을 반환
	public int capacity() {
		return max;
	}

	// 큐에 쌓인 데이터 수를 반환
	public int size() {
		return num;
	}

	// 큐가 비어 있는가?
	public boolean isEmpty() {
		return num <= 0;
	}

	// 큐가 가득 찼는가?
	public boolean isFull() {
		return num >= max;
	}

	// 큐 안의 데이터를 머리→꼬리의 차례로 출력함
	public void dump() {
		if (num <= 0)
			System.out.println("큐가 비었습니다.");
		else {
			for (int i = 0; i < num; i++)
				System.out.print(que[i] + " ");
			System.out.println();
		}
	}
}