스택(stack)

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다. 데이터는 후입선출로 이뤄진다는 점이 큐와의 차이점이라고 할 수 있다. 따라서 큐에서의 프론트/리어와 다르게 스택은 탑과 바텀으로 표현하는데, 이것은 후입선출 특징상 꼭대기(탑)에 가까운 데이터만 나가고 들어오기 때문이다. 흔히 '스택을 쌓는다'라는 말이 있는데, 쌓는다는 표현이 바로 정확하게 표현한다고 볼 수 있다. 바닥부터 쌓아올리는 형식을 생각하면, 자료를 넣을때도 뺄 때도 후입선출을 할 수 밖에 없기 때문이다.

 

스택에서 데이터를 넣는 작업을 푸시(push)라 하고, 데이터를 꺼내는 작업을 pop 이라고 한다. Java에서는 메서드를 호출하고 실행하는 것을 스택방식으로 처리한다. 스택 역시 데이터의 집합이기 때문에 배열로 구현할 수 있다.

 

public class IntStack {
	private int max;	// 스택 용량
	private int ptr;	// 스택 포인터
	private int[] stk;	// 스택 본체
	
	//실행 시 예외 : 스택이 비어있음
	public class EmptyIntStackException extends RuntimeException{
		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 i = 0; i < ptr; i++){
				System.out.print(stk[i] + " ");
			}
			System.out.println();
		}
	}
	
}

위 스택소스는 스택을 선언하고 스택에서 이용할 수 있는 주요 메서드를 구현한 것이다. 이를 통해 아래의 테스트코드로 스택의 기능을 확인할 수 있다.

 

class IntStackTester {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		IntStack s = new IntStack(64);		//최대 64개를 푸시할 수 있는 스택
		
		while (true){
			System.out.println("현재 데이터 수 :" + s.size() + " / "
											+ s.capacity());
			System.out.print("(1)푸시 (2)팝 (3)피크 (4)덤프 (0)종료 :");
			
			int menu = stdIn.nextInt();
			if(menu == 0) break;
			
			int x;
			switch(menu){
				case 1:			//푸시
					System.out.print("데이터 : ");
					x = stdIn.nextInt();
					try {
						s.push(x);
					} catch (IntStack.OverflowIntStackException e) {
						System.out.println("스택이 가득 찼습니다.");
					}
					break;
				
				case 2:			//팝
					try {
						x = s.pop();
						System.out.println("팝한 데이터는 " + x + "입니다.");
					} catch (IntStack.EmptyIntStackException e) {
						System.out.println("스택이 비어 있습니다.");
					}
					break;
				
				case 3:			//피크
					try{
						x = s.peek();
						System.out.println("피크한 데이터는 " + x + "입니다.");
					} catch(IntStack.EmptyIntStackException e){
						System.out.println("스택이 비어 있습니다.");
					}
					break;
					
				case 4:			//덤프
					s.dump();
					break;
			}
		}
	}
}

 

한 배열에 꼭 스택이 하나일 필요는 없다. 한 배열 안에 스택은 2개가 존재할 수도 있으며, 배열의 양 끝을 바닥으로 두고 가운데로 향하는 방향의 끝을 꼭대기(top)로 둔다면 스택은 두 꼭대기가 만나는 지점까지 데이터를 저장 할 수 있다. 아래 코드를 보면 좀 더 이해가 빠를 것이다.

 

public class IntStackX_04_03 {
	private int max; // 스택의 용량 (A・B의 합계)
	private int ptrA; // 스택 포인터 A
	private int ptrB; // 스택 포인터 B
	private int[] stk; // 스택 본체

	public enum AorB {
		StackA, StackB
	};

	// 실행할 때 예외：스택이 비어 있음
	public class EmptyIntStackX2Exception extends RuntimeException {
		public EmptyIntStackX2Exception() {
		}
	}

	// 실행할 때 예외：스택이 가득 참
	public class OverflowIntStackX2Exception extends RuntimeException {
		public OverflowIntStackX2Exception() {
		}
	}

	// 생성자
	public IntStackX_04_03(int capacity) {
		ptrA = 0;				//ptrA스택은 인덱스 0부터
		ptrB = capacity - 1;	//ptrB스택은 마지막 인덱스부터
		max = capacity;
		try {
			stk = new int[max]; // 스택 본체용 배열을 생성
		} catch (OutOfMemoryError e) { // 생성할 수 없습니다.
			max = 0;
		}
	}

	// 스택에 x를 푸시
	public int push(AorB sw, int x) throws OverflowIntStackX2Exception {
		if (ptrA >= ptrB + 1) // 스택이 가득 참
			throw new OverflowIntStackX2Exception();
		switch (sw) {
		case StackA:
			stk[ptrA++] = x;
			break;
		case StackB:
			stk[ptrB--] = x;
			break;
		}
		return x;
	}

	// 스택에서 데이터를 팝(꼭대기의 데이터를 꺼냄)
	public int pop(AorB sw) throws EmptyIntStackX2Exception {
		int x = 0;
		switch (sw) {
		case StackA:
			if (ptrA <= 0) // 스택 A가 비어 있음
				throw new EmptyIntStackX2Exception();
			x = stk[--ptrA];
			break;
		case StackB:
			if (ptrB >= max - 1) // 스택 B가 비어 있음
				throw new EmptyIntStackX2Exception();
			x = stk[++ptrB];
			break;
		}
		return x;
	}

	// 스택에서 데이터를 피크(꼭대기의 데이터를 살펴 봄)
	public int peek(AorB sw) throws EmptyIntStackX2Exception {
		int x = 0;
		switch (sw) {
		case StackA:
			if (ptrA <= 0) // 스택 A가 비어 있음
				throw new EmptyIntStackX2Exception();
			x = stk[ptrA - 1];
			break;
		case StackB:
			if (ptrB >= max - 1) // 스택 B가 비어 있음
				throw new EmptyIntStackX2Exception();
			x = stk[ptrB + 1];
			break;
		}
		return x;
	}

	// 스택에서 x를 검색하여 index(찾지 못하면 -1)를 반환
	public int indexOf(AorB sw, int x) {
		switch (sw) {
		case StackA:
			for (int i = ptrA - 1; i >= 0; i--) // 꼭대기쪽부터 선형 검색
				if (stk[i] == x)
					return i; // 검색성공
			break;
		case StackB:
			for (int i = ptrB + 1; i < max; i++) // 꼭대기쪽부터 선형 검색
				if (stk[i] == x)
					return i; // 검색성공
			break;
		}
		return -1; // 검색실패
	}

	// 스택을 비움
	public void clear(AorB sw) {
		switch (sw) {
		case StackA:
			ptrA = 0;
			break;
		case StackB:
			ptrB = max - 1;
			break;
		}
	}

	// 스택의 용량을 반환 (A와 B의 합계)
	public int capacity() {
		return max;
	}

	// 스택에 쌓여있는 데이터 수를 반환
	public int size(AorB sw) {
		switch (sw) {
		case StackA:
			return ptrA;
		case StackB:
			return max - ptrB - 1;
		}
		return 0;
	}

	// 스택이 비어 있는가?
	public boolean isEmpty(AorB sw) {
		switch (sw) {
		case StackA:
			return ptrA <= 0;
		case StackB:
			return ptrB >= max - 1;
		}
		return true;
	}

	// 스택이 가득 찼는가?
	public boolean isFull() {
		return ptrA >= ptrB + 1;
	}

	// 스택 안의 터이터를 바닥 → 꼭대기의 차례로 나타냄
	public void dump(AorB sw) {
		switch (sw) {
		case StackA:
			if (ptrA <= 0)
				System.out.println("스택이 비었습니다.");
			else {
				for (int i = 0; i < ptrA; i++)
					System.out.print(stk[i] + " ");
				System.out.println();
			}
			break;
		case StackB:
			if (ptrB >= max - 1)
				System.out.println("스택이 비었습니다.");
			else {
				for (int i = max - 1; i > ptrB; i--)
					System.out.print(stk[i] + " ");
				System.out.println();
			}
			break;
		}
	}
}

 

데이터를 푸시하고 팝 하는 순서를 바꾸기 위해 각 스택당 인덱스를 다르게 설정해 준 뒤, 각각의 메서드에서 조건만 맞춰준다면 하나의 배열을 공유하면서도 2개의 스택을 구현 할 수 있다.