자바로 짜는 Stack

10 April 2018

Algorithm

복습도 할겸 Stack을 Java로 다시 짜보았다. Stack은 후입선출(Last in First out) 구조의 특징을 가지고 있는데 비유를 하자면 닭꼬치를 예로 들 수 있겠다. 닭꼬치는 꼬치에 꾀어 있기 때문에 가장 마지막에 들어간 고기부터 빼내어 먹을 수밖에 없다. 생뚱맞은 비유지만 요즘 잘 쓰지않는 CD 보관케이스 이런것보단 쉽게 이해가 가지 않을까 싶다.

이전에는 C언어를 사용하여 코딩하였기 때문에 구조체를 만들어서 Node간 주소를 연결해줬는데 Java는 어떻게 해서 객체들을 이어야하나 라는 생각이 들었다. 처음 든 생각은 ArrayList를 쓰는거였는데 뭐랄까 치트쓰는것 같기도 하고 List 자체가 Stack 다음으로 심화되는 과정인데 미리 땡겨쓰는게 연습에 의미가 없기도 했다. 그리하여 결국 사용한건 객체끼리 서로를 참조하는 것이다. C언어에서 메모리로 참조했던것처럼 원리는 같다.

Stack

발로 그려본 Node 관계도

public class Node
{
	private Object object;	//Data
	private Node prev;	//Previous Node
	public Node(Object object, Node prev)
	{
		super();
		this.object = object;
		this.prev = prev;
	}
	public Object getObject()
	{
		return object;
	}
	public void setObject(Object object)
	{
		this.object = object;
	}
	public Node getPrev()
	{
		return prev;
	}
	public void setPrev(Node prev)
	{
		this.prev = prev;
	}
	@Override
	public String toString()
	{
		return "Node [object=" + object + ", prev=" + prev + "]";
	}
}

어떤 값이든 들어갈 수 있도록 Data 부분에는 Object로 선언해놓았고 이전 Node를 참조하였으니 Garage Collection이 강제로 일어나지 않는 이상은 문제없이 동작할것이다. 이제 실질적으로 이 VO를 사용한 Stack을 짜야한다.

public class Stack
{
	private int count;
	private Node lastNode;

	/**
	 * Default Constructor
	 * Intilalize parameters
	 */
	public Stack()
	{
		this.lastNode = null;
		this.count = 0;
	}
	/**
   * if stack didn't have any nodes
   */
	public boolean isEmpty()
	{
		return lastNode == null;
	}

  /**
   * return stack's size
   */
	public int size()
	{
		return count;
	}

  /**
   * push node in last position of stack
   */
	public void push(Object object)
	{
		System.out.println("push : "+object.toString());
		Node newNode = new Node(object, lastNode);
		lastNode = newNode;
		count++;
	}

  /**
   * pop node in last position of stack
   */
	public Node pop()
	{
		if(isEmpty()) throw new NoSuchElementException("Stack is underflow");
		Node popNode = lastNode;
		lastNode = lastNode.getPrev();
		count--;
		System.out.println("pop : "+popNode.getObject().toString());
		return popNode;
	}

  /**
   * peek node in last position of stack (pop without remove)
   */
	public Node peek()
	{
		System.out.println("lastNode : "+lastNode.getObject().toString());
		if(isEmpty()) throw new NoSuchElementException("Stack is underflow");
		return lastNode;
	}
}

이 Stack에서 하는 일은 다음과 같다

  • isEmpty() : 가장 마지막에 들어간 Node가 Null 값인지 조회하여 TRUE/FALSE 값을 반환한다
  • size() : Stack의 크기를 정수형으로 반환한다
  • push(Object object) : Stack의 가장 마지막 열에 새로운 Node를 추가한다
  • pop() : 가장 마지막에 들어간 Node의 Data를 배출한다, Data가 없을 경우 underflow 예외 발생
  • peek() : 가장 마지막에 들어간 Node의 Data를 읽어온다, Data가 없을 경우 underflow 예외 발생

결과

public class Main
{
	public static void main(String[] args)
	{
		Stack stack = new Stack();
		stack.push("A");
		stack.push("B");
		stack.push("C");
		stack.push("D");
		stack.push("E");
		stack.pop();
		stack.pop();
		stack.push("F");
		stack.push("G");
		System.out.println("count : "+stack.size());
		stack.pop();
		stack.pop();
		stack.pop();
		stack.pop();
		stack.pop();
		stack.pop();
	}
}

push : A
push : B
push : C
push : D
push : E
pop : E
pop : D
push : F
push : G
count : 5
pop : G
pop : F
pop : C
pop : B
pop : A
Exception in thread "main" java.util.NoSuchElementException: Stack is underflow
	at github.bobos.stack.Stack.pop(Stack.java:40)
	at github.bobos.stack.Main.main(Main.java:25)