이번에는 스택과 큐에 대해 학습할 예정이다.
2학년 때 이미 배웠던 주제라 큰 어려움은 없겠지만,
저번에 소개했던 제네릭 기법으로 코드를 작성해보는 것이 주된 목표이다.
스택: 데이터를 일시적으로 저장하기 위한 자료구조 (LIFO - Last In First Out)
후입선출의 특징을 가진다.
- push 스택에 넣는 작업 / pop 스택에서 꺼내는 작업
- top 푸시와 팝을 하는 곳 (꼭대기) / bottom 가장 아랫부분
보통 프로그램이 실행될 때 메서드의 호출과 실행은 스택을 이용한다.
시스템 프로그래밍 교과목에서도 프로시져에 관련한 것은 스택을 이용했던 부분이 있다.
void x(){...}
void y(){...}
void z(){
x();
y();
}
int main(){
z();
}
이런 메서드들이 있을 때
메소드들이 스택에서 push되거나 pop되는 과정이 일어난다. 실제로는 스택 프레임 이런 게 더 있지만,
이번에는 따로 다루지 않는다.
- 구현
- 생성자: 스택 본체의 개별 요소는 바닥부터 stk[0]. stk[1],...,stk[max-1]이 된다.
생성 시 스택은 비어있으므로 ptr은 0으로 한다. - push: 스택에 푸시하는 메서드 / 가득 찬 경우 OverflowIntStackException을 던진다.
부등호를 이용하여 스택 본체 배열의 상한과 하한을 벗어나서 접근하는 것을 막는다. - 저장하고 스택 포인터를 1 증가시킨다. 후위연산자 사용!
- pop: 스택의 top에서 제거하고 값을 반환하는 메서드 / 스택이 비어있는 경우 EmptyIntStackException을 던진다.
- 스택 포인터를 1 감소시키고 값을 반환한다. 전위연산자 사용!
- top / peek: 스택의 꼭대기에 있는 원소를 반환하는 메서드 / 비어있는 경우 예외 처리
- ptr-1 인덱스의 요소를 반환한다.
- indexOf: 스택 본체 배열에 x와 같은 값의 데이터가 포함되어 있는지, 있다면 어디에 있는지
조사하는 메서드입니다. - 꼭대기에서 바닥으로 / 인덱스가 큰 곳에서 작은 곳으로 검색을 수행한다. => 먼저 제거되는 데이터를 찾기 위해서
- 나머지: clear / capacity / size / IsEmpty / IsFull
- 생성자: 스택 본체의 개별 요소는 바닥부터 stk[0]. stk[1],...,stk[max-1]이 된다.
import java.util.Scanner;
public class IntStack {
private int max; //스택 용량
private int ptr; //스택 포인터
private int[] stk; //스택 본체
public class EmptyStackException extends RuntimeException{
public EmptyStackException(){}
}
public class OverflowException extends RuntimeException{
public OverflowException(){}
}
public IntStack(int capacity){
ptr = 0;
max = capacity;
try{
stk = new int[max];
}catch(OutOfMemoryError e){
max = 0;
}
}
public int push(int x) throws OverflowException{
if(ptr >= max){
throw new OverflowException();
}
return stk[ptr++] = x; //푸시한 값을 반환
}
public int pop() throws EmptyStackException {
if (ptr <= 0) {
throw new EmptyStackException();
}
return stk[--ptr];
}
public int peek() throws EmptyStackException{
if(ptr<=0){
throw new EmptyStackException();
}
return stk[ptr-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 i = 0; i<ptr;i++){
System.out.println(stk[i]+" ");
}
System.out.println();
}
}
}
class IntStackTester{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
IntStack s = new IntStack(64);
while(true){
System.out.println("현재 데이터 수 : " + s.size() + "/" + s.capacity());
System.out.print("1push 2pop 3peek " +
"4dump 0end : ");
int menu = sc. nextInt();
if(menu==0){
break;
}
int x;
switch(menu){
case 1:
System.out.print("데이터 : ");
x = sc.nextInt();
try{
s.push(x);
}catch(IntStack.OverflowException e){
System.out.println("스택이 가득 찼습니다.");
}
break;
case 2:
try{
x = s.pop();
System.out.println("팝한 데이터는 " + x +"입니다.");
}catch(IntStack.EmptyStackException e){
System.out.println("스택이 비어있습니다.");
}
break;
case 3:
try{
x = s.peek();
System.out.println("피크한 데이터는 "+x+"입니다.");
}catch(IntStack.EmptyStackException e){
System.out.println("스택이 비어있습니다.");
}
break;
case 4:
s.dump();
break;
}
}
}
}
IntStack을 이용하는 프로그램까지 작성해보니 전반적인 감이 잡힌다.
큐: 스택과 마찬가지로 데이터를 임시로 쌓아 놓은 자료구조, FIFO(First In First Out)
선입선출을 따른다.
- enqueue: 큐에 넣는 작업 / rear: 데이터를 넣는 쪽
- dequeue: 큐에서 데이터를 꺼내는 작업 / front: 데이터를 꺼내는 쪽, 인덱스가 0이다!
- 구현
- enqueue: rear의 다음 요소에 데이터를 저장, O(1)시간
- dequeue: 데이터를 꺼낸 후 두 번째 이후의 요소를 모두 맨 앞으로 옮긴다, O(n)시간
- 데이터를 꺼낼 때마다 이런 처리를 하면 효율이 떨어진다.
- 링 버퍼로 큐 만들기
- 배열 요소를 앞쪽으로 옮기지 않는 큐 구현
- 링 버퍼(ring buffer)라는 자료구조를 이용한다.
- front와 rear를 요소를 식별하기 위한 변수로 사용한다.
front: 맨 처음 요소의 인덱스
rear: 맨 끝 요소의 하나 뒤의 인덱스
이런 식으로 구현하면 변수 값만을 업데이트하여 enqueue와 dequeue를 수행하기 때문에
요소 이동 문제를 해결하고 시간을 O(1)에 수행할 수 있다.
- 커스텀 예외 처리
- 스택을 구현할 때도 작성했던 코드이다.
- 직접 IntQueue클래스에서만 사용하는 예외를 작성하여 분명하게 확인할 수 있게 한다.
큐가 비거나 꽉 채워져있을 때 직접 만든 예외를 던지는 것이다.
- num
- front와 rear로 큐가 꽉 찼는지 알 수 없다.
- 비어있는 경우 front = rear = 0 / front = rear인 경우도 있다.
- 따라서 num과 max값을 비교하여 큐의 사용 가능 유무를 확인한다.
- enqueue
- enque후에 rear가 max를 넘어 배열에 없는 값을 가리키게 되는 문제가 발생한다. (배열의 끝)
- 따라서, rear가 +1 되었을 때 max와 같아지는 것을 방지하도록 인큐를 구현해야 한다.
- max와 같아질 경우 rear를 배열의 처음 인덱스인 0으로 변경한다.
- dequeue
- enqueue와 마찬가지로 인덱스 초과 문제가 발생한다. (배열의 끝)
- front와 max가 같아질 경우 front를 배열의 처음 인덱스인 0으로 변경한다.
- indexOf
- 큐의 시작은 front이므로 front의 인덱스를 계산해야 한다.
- (i + front) % max 로 계산한다.
import java.util.Scanner;
public class IntQueue {
private int max;
private int front;
private int rear;
private int num;
private int[] que;
public class EmptyIntQueueException extends RuntimeException { //커스텀 예외 처리 작성
public EmptyIntQueueException() {}
}
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() {}
}
public IntQueue(int capacity){
num = front = rear = 0;
max = capacity;
try{
que = new int[max];
}catch(OutOfMemoryError e){
max = 0;
}
}
public int enque(int x) throws OverflowIntQueueException {
if(num >= max){
throw new OverflowIntQueueException();
}
que[rear++] = x;
num++;
if(rear == max){
rear = 0;
}
return x;
}
public int deque() throws EmptyIntQueueException {
if(num <= 0){
throw new EmptyIntQueueException();
}
int x = que[front++];
num--;
if(front == max){
front = 0;
}
return x;
}
public int peek() throws EmptyIntQueueException {
if(num <= 0){
throw new EmptyIntQueueException();
}
return que[front];
}
public int indexOf(int x){
for(int i = 0; i< num; i++){
int idx = (i + front) % max;
if(que[idx] == x){
return idx;
}
}
return -1;
}
public void clear(){
num = front = rear = 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 + front) % max] + " ");
}
System.out.println();
}
}
}
class IntQueueTestrer{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
IntQueue q = new IntQueue(64);
while(true){
System.out.println("현재 데이터 수 : " + q.size() + " / "
+ q.capacity());
System.out.print("(1)인큐 (2)디큐 (3)피크 " + "(4)덤프 (0)종료 : ");
int menu = sc.nextInt();
if(menu == 0){
break;
}
int x;
switch(menu){
case 1:
System.out.print("데이터 : ");
x = sc.nextInt();
try{
q.enque(x);
}catch(IntQueue.OverflowIntQueueException e){
System.out.println("큐가 가득 찼습니다.");
}
break;
case 2:
try{
x = q.deque();
System.out.println("디큐한 데이터는 " + x + "입니다.");
}catch (IntQueue.EmptyIntQueueException e){
System.out.println("큐가 비어있습니다.");
}
break;
case 3:
try{
x = q.peek();
System.out.println("피크한 데이터는 " + x +"입니다.");
}catch (IntQueue.EmptyIntQueueException e){
System.out.println("큐가 비어있습니다.");
}
break;
case 4:
q.dump();
break;
}
}
}
}
- 링 버퍼 활용
- "오래된 데이터를 버리는 용도"로 활용할 수 있다.
- 배열 a[cnt++ % capacity] 이런 식으로 인덱스를 조절하여 n개의 최신 데이터를 유지할 수 있다.
import java.util.Scanner;
class LastNElements{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
final int N = 10;
int [] a = new int[N];
int cnt = 0;
int retry;
System.out.println("정수를 입력하세요. ");
do{
System.out.printf("%d번째 정수 : ", cnt + 1);
a[cnt++ % N] = sc.nextInt();
System.out.printf("계속 할까요? (예.1 / 아니오.0) : ");
retry = sc.nextInt();
}while(retry == 1);
int i = cnt - N;
if(i < 0){
i = 0;
}
for( ; i < cnt; i++){
System.out.printf("%2d번째의 정수=%d\n", i+1, a[i % N]);
}
}
}
지금까지 스택과 큐에 관련된 내용들을 점검하고
구현상에 문제가 되는 부분들을 어떻게 처리하는지 학습했다.
연습문제로 변형된 스택이나 큐의 형태를 연습하고 제네릭 기법으로 작성하는 법을 공부할 계획이다.
다음 주 내용은 재귀 알고리즘이다!