Stack - Created as Array

* 스택은 배열 혹은 링크드 리스트 두개다 작성이 가능하다.

* Java Stack API를 확인해보니 배열기반으로 작성되어있음

* 그래서 나도 한번 배열로 작성해 보았다

* 이번 테스트는 Main에서 진행

Stack 클래스

package algo.stack;

public class MyStack<E> {

	private int top;
	private int initialCapacity;
	private int capacity;
	private Object[] arr;

	public MyStack() {
		
		top = -1;
		initialCapacity = 1;
		capacity = initialCapacity;
		arr = new Object[initialCapacity];
		
	}

	public E push(E item){
		
		if(isFull())
			reAllocate();
		
		top++;
		
		arr[top] = item;
		
		return (E)item;
	}

	private void reAllocate() {
		
		Object[] newArr = new Object[capacity * 2];
		for (int i = 0; i < arr.length; i++) {
			newArr[i] = arr[i]; 
		}
		arr = newArr;
		capacity = capacity * 2;
	}

	public E pop() {

		if (isEmpty())
			return null;

		Object item = arr[top];
		arr[top] = null;
		top--;

		return (E)item;
	}
	
	public E peek() {
		
		if(isEmpty())
			return null;
		
		return (E)arr[top];
		
	}
	
	private boolean isFull() {
		return top == capacity - 1;
	}
	
	public boolean isEmpty() {
		return top == -1;
	}

	@Override
	public String toString() {
		
		StringBuilder builder = new StringBuilder();
		builder.append("Current Capacity : " + capacity);
		builder.append("\tCurrent Top : " + top);
		builder.append(", ");
		builder.append("[");
		for (int i = 0; i < arr.length; i++) {
			if(i == arr.length - 1)
				builder.append(arr[i]);
			else
				builder.append(arr[i] + ",");
				
		}
		builder.append("]");
		
		return builder.toString();
	}
	
}

테스트

import algo.stack.MyStack;

public class Main {

	public static void main(String[] args) {
		
		MyStack<String> stack = new MyStack<>();
		
		System.out.println(" * PUSH : " + stack.push("01"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("02"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("03"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("04"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("05"));
		System.out.println(stack);
		System.out.println(" * PEEK : " + stack.peek());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		
		System.out.println(" * PUSH : " + stack.push("06"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("07"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("08"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("09"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("10"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("11"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("12"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("13"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("14"));
		System.out.println(stack);
		
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		
	}
}

결과

 * PUSH : 01
Current Capacity : 1	Current Top : 0, [01]
 * PUSH : 02
Current Capacity : 2	Current Top : 1, [01,02]
 * PUSH : 03
Current Capacity : 4	Current Top : 2, [01,02,03,null]
 * PUSH : 04
Current Capacity : 4	Current Top : 3, [01,02,03,04]
 * PUSH : 05
Current Capacity : 8	Current Top : 4, [01,02,03,04,05,null,null,null]
 * PEEK : 05
Current Capacity : 8	Current Top : 4, [01,02,03,04,05,null,null,null]
 * POP : 05
Current Capacity : 8	Current Top : 3, [01,02,03,04,null,null,null,null]
 * POP : 04
Current Capacity : 8	Current Top : 2, [01,02,03,null,null,null,null,null]
 * POP : 03
Current Capacity : 8	Current Top : 1, [01,02,null,null,null,null,null,null]
 * PUSH : 06
Current Capacity : 8	Current Top : 2, [01,02,06,null,null,null,null,null]
 * PUSH : 07
Current Capacity : 8	Current Top : 3, [01,02,06,07,null,null,null,null]
 * PUSH : 08
Current Capacity : 8	Current Top : 4, [01,02,06,07,08,null,null,null]
 * PUSH : 09
Current Capacity : 8	Current Top : 5, [01,02,06,07,08,09,null,null]
 * PUSH : 10
Current Capacity : 8	Current Top : 6, [01,02,06,07,08,09,10,null]
 * PUSH : 11
Current Capacity : 8	Current Top : 7, [01,02,06,07,08,09,10,11]
 * PUSH : 12
Current Capacity : 16	Current Top : 8, [01,02,06,07,08,09,10,11,12,null,null,null,null,null,null,null]
 * PUSH : 13
Current Capacity : 16	Current Top : 9, [01,02,06,07,08,09,10,11,12,13,null,null,null,null,null,null]
 * PUSH : 14
Current Capacity : 16	Current Top : 10, [01,02,06,07,08,09,10,11,12,13,14,null,null,null,null,null]
 * POP : 14
Current Capacity : 16	Current Top : 9, [01,02,06,07,08,09,10,11,12,13,null,null,null,null,null,null]
 * POP : 13
Current Capacity : 16	Current Top : 8, [01,02,06,07,08,09,10,11,12,null,null,null,null,null,null,null]
 * POP : 12
Current Capacity : 16	Current Top : 7, [01,02,06,07,08,09,10,11,null,null,null,null,null,null,null,null]