[Java] 스택(Stack) 배열로 구현하기

1. Stack이란?

스택

• 마지막에 들어온 데이터가 가장 먼저 나간다. 즉, 후입선출(LIFO) 방식이다.
• 맨 위의 원소에만 접근이 가능하다. 
• 가상 메모리의 스택 영역에서 이와 같은 자료 구조를 이용한다.

2. Stack 구현하기

구현할 내용은 아래와 같다.

• push(E x) - 원소 x를 스택에 입력한다.
• pop() - 스택 맨 위의 원소를 삭제한다.
• top() - 스택 맨 위의 원소 값을 리턴한다.
• isEmpty() - 스택이 비었는지 여부를 리턴한다.
• popAll() - 스택의 내부 데이터를 모두 삭제한다.
• printAll() - 스택의 내부의 모든 데이터를 출력한다.

** 원래 스택에서는 맨 위의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.

 

1) 인터페이스

public interface StackInterface<E> {

	public void push (E x);
	
	public void pop();
	
	public E top();
	
	public boolean isEmpty();
	
	public void popAll();
	
	public void printAll();
	
}

 

2) 클래스

- 필드 영역

//필드 영역
	private E stack[];
	private int topIndex;
	private static final int DEFAULT_CAPACITY = 64;

• stack - 원소를 입력 받을 배열 리스트이다.
• topIndex - 스택의 맨 윗 원소의 인덱스를 저장한다.
• DEFAULT_CAPACITY - 스택 생성 시 용량을 따로 선언하지 않을 경우 설정할 기본 용량이다.

- 생성자 영역

//생성자 영역
	public ArrayStack() {
		stack = (E[]) new Object[DEFAULT_CAPACITY];
		topIndex = -1;
	}
	
	public ArrayStack(int n) {
		stack = (E[]) new Object[n];
		topIndex = -1;
	}

• 생성 시 입력 값으로 정수를 받으면 해당 정수 크기의 스택을, 그렇지 않으면 DEFAULT_CAPACITY 크기의 스택을 생성한다.

-메서드 영역

<push 메서드 구현>

//메서드 영역
	@Override
	public void push(E x) {
		if (isFull()) {
			System.out.println("ERROR");
		} else {
			topIndex++;
			stack[topIndex]=x;
		}
	}

• 만약 stack에 남은 공간이 없는데 push를 시도하면 에러를 출력한다.
• 그렇지 않으면 topIndex를 늘려준 뒤 해당 인덱스에 입력받은 데이터를 입력한다.

<pop 메서드 구현>

@Override
	public void pop() {
		if (isEmpty()) {
			System.out.println("ERROR");
		} else {
		stack[topIndex]=null;
		topIndex--;
		}
	}

• 만약 stack이 비어 있는데 pop을 시도하면 에러를 출력한다.
• 그렇지 않다면 현재 topIndex를 null로 바꾼 후 topIndex를 1 감소시킨다.
• ** 사실 add시 해당 인덱스를 덮어 쓸 것이기 때문에 topIndex만 1 감소시키고 null 처리는 해주지 않아도 된다.

<top 메서드 구현>

@Override
	public E top() {
		if (isEmpty()) {
			return null;
		} else {
		return stack[topIndex];
		}
	}

• 만약 스택이 비어있는데 top을 시도하면 null 값을 반환한다.
• 그렇지 않다면 stack의 topIndex값을 반환한다.

<isEmpty&isFull 메서드 구현>

@Override
	public boolean isEmpty() {
		return (topIndex<0);
	}

//isFull메서드는 인터페이스를 오버라이딩 한 것이 아님에 주의!
	public boolean isFull() {
		return (topIndex==stack.length-1);
	}

• isEmpty - topIndex가 음수이면 true, 아니면 false.
• isFull - topIndex와 스택의 크기를 비교하여 스택이 다 찼는지를 판별.

<popAll 메서드 구현>

@Override
	public void popAll() {
		stack = (E[]) new Object[stack.length];
		topIndex=-1;
	}

• stack을 기존 길이의 빈 배열 리스트로 덮어쓴다.
• topIndex를 초기화한다.

<printAll 메서드 구현>

@Override
	public void printAll() {
		
		for (int i=0; i<=topIndex; i++) {
			System.out.print(stack[i]+" ");
		}
		
	}

• for문이 전체 스택의 인덱스를 순회하며 해당 인덱스의 값들을 프린트한다.

- 전체 코드

public class ArrayStack<E> implements StackInterface<E> {
	
	//필드 영역
	private E stack[];
	private int topIndex;
	private static final int DEFAULT_CAPACITY = 64;
	
	//생성자 영역
	public ArrayStack() {
		stack = (E[]) new Object[DEFAULT_CAPACITY];
		topIndex = -1;
	}
	
	public ArrayStack(int n) {
		stack = (E[]) new Object[n];
		topIndex = -1;
	}
	
	//메서드 영역
	@Override
	public void push(E x) {
		if (isFull()) {
			System.out.println("ERROR");
		} else {
			topIndex++;
			stack[topIndex]=x;
		}
	}

	@Override
	public void pop() {
		if (isEmpty()) {
			System.out.println("ERROR");
		} else {
		stack[topIndex]=null; //안해도 됨.
		topIndex--;
		}
	}

	@Override
	public E top() {
		if (isEmpty()) {
			return null;
		} else {
		return stack[topIndex];
		}
	}

	@Override
	public boolean isEmpty() {
		return (topIndex<0);
	}

	public boolean isFull() {
		return (topIndex==stack.length-1);
	}

	@Override
	public void popAll() {
		stack = (E[]) new Object[stack.length];
		topIndex=-1;
	}

	@Override
	public void printAll() {
		
		for (int i=0; i<=topIndex; i++) {
			System.out.print(stack[i]+" ");
		}
		
	}

}

3) 결과 확인하기

<코드>

public class Test {
	public static void main(String[] args) {

	ArrayStack<Integer> stack = new ArrayStack<>();
	
	stack.push(100);
	
	stack.push(200);
	
	stack.push(300);
	
	stack.push(400);
	
	System.out.println(stack.top());
	
	stack.printAll();
	System.out.println();
	
	
	
	for (int i=0; i<5; i++) {
		stack.pop();
	}
	
	stack.printAll();
	
	//스택에서 pop을 5번 수행한 뒤 출력합니다. - 원소가 4개인데 5번 pop하였으므로 에러가 발생하고, 스택이 비어있으므로 내용물은 출력되지 않음.
	
	System.out.println(stack.isEmpty());
	
	// 스택이 비었는지 여부를 출력합니다.
	
	stack.push(100);
	stack.printAll();
	System.out.println();
	
	//stack에 100을 입력하고 출력합니다.
	
	stack.popAll();
	stack.printAll();
	
	//stack에 - stack을 popAll 했으므로 내용물이 출력되지 않음.
	
	}
}

<결과>

정상적으로 출력된다.