[java] stack 구현

자바에서 스택을 구현하려면 직접 구현하는 방법과 Stack 클래스를 사용하는 방법 두 가지가 있다.

Stack 클래스를 사용하기 이전 직접 이해하고 구현할 줄도 알아야 하기 때문에

두 가지 방법 다 정리해 보려고 한다.

 

1. 직접 구현하기

  1-1 배열로 구현

        * search와 empty는 자바에서 지원해 주므로 여기서는 push, pop, peek만 구현한다.

public class Stack{	
    int top;
    int size;
    int[] stack;
    
    public Stack(int size){
    	this.size = size;
        stack = new int[size];
        top = -1;
    }
    
    public void push(int item){
    	stack[++top] = item;
    }
    
    public void pop(){
    	int pop = stack[top];
        stack[top--] =0;
    }
    
    public void peek(){
    	return stack[top]
    }
 
}

 

1-2 LinkedList로 구현

   LinkedList 로 구현하면 스택의 크기가 고정되어 있지 않다는 장점이 있다.

  우선 LinkedList에서 사용할 Node 클래스가 필요하므로 이를 구현한다.    

//연결리스트로 사용할 노드 클래스
public class Node{
	private Object data;
    private Node node;
    
    public Node(Object data){
    	this.data = data;
        this.node = null;
    }
    
    //노드 연결 메소드
    public void link(Node next){
    	this.node = next;
    }
    
    //노드의 데이터를 가져오는 메소드
    public Object getData(){
    	return this.data;
    }
    
    //연결된 노드를 가져오는 메소드
    public Node getNextNode(){
    	return this.node;
    }
    
}

 

노드 클래스를 구현한 후 LinkedList로 Stack을 구현한다.

public class Stack{
	private Node top;	//마지막 노드
    
    public stack(){
    	top = null;
    }
	
    public boolean empty(){
    	return (top == null);
    }
    
    public void push(Object item){
    	Node newNode = new Node(item);   //새로운 노드를 생성하여 마지막 노드와 연결
        newNode.linkNode(top);           
        top = newNode;                 //새로운 노드를 마지막 노드로 변경
    }
    
    public Object peek(){
    	return top.getData();
    }
	
    public bject pop(){
    	if(!empty()){
            Object item = peek();
            top = top.getNextNode(); 
            return item;
        }else{
            return -1 			// 데이터가 없을 경우
        }
    	
    }
}

 

 

2. Stack 클래스

자바에서는 기본적으로 stack 클래스를 지원한다. 우선 java.util.Stack;으로 패키지를 import 한다.

Stack<Element> stack = new Stack<>();

 

지원하는 메소드는 다음과 같다.

push(i) : 요소 i를 스택에 넣는다.

pop() : 가장 최근에 들어간 값을 제거한다.

peek() : 가장 최근에 들어간 값을 출력한다.

empty() : 스택이 비었으면 true, 값이 있으면 false를 출력한다.

search(i) : 요소 i의 인덱스를 출력한다. 요소가 없다면 -1을 출력한다.