스택을 간단하게 알아보자

스택의 사용 사례

• 재귀 알고리즘
• 웹브라우저 뒤로가기
• 실행취소
• 괄호검사
• 후위표기법
• dfs(깊이우선탐색)

 

 

배열

    static int[] stack;
    static int size = 0;

    static void push(int item){
        stack[size++] = item;
    }
    
    static int pop(){
        if(size==0)
            return -1;
        int res = stack[size-1];
        stack[size-1] = 0;
        size--;
        return res;
    }
    
    static int size(){
        return size;
    }
    
    static int empty(){
        if(size==0)
            return 1;
        return 0;
    }
    
    static int top(){
        if(size==0)
            return -1;
        return stack[size-1];
    }

 

 

연결리스트

import java.util.EmptyStackException;
 
public class MyStack {
    private Node top;
 
    public MyStack() {
        this.top = null;
    }
 
    public class Node {
        private String data;
        private Node nextNode;
 
        public Node(String data) {
            this.data = data;
            this.nextNode = null;
        }
    }
 
    public String push(String data) {
        Node node = new Node(data);
        node.nextNode = top;
        top = node;
    
        return data;
    }
 
    public String pop() {
        String data = peek();
        
        top = top.nextNode;        
        return data;
    }
 
    public String peek() {
        if (top == null)
            throw new EmptyStackException();
        return top.data;
    }
 
    public boolean empty() {
        return top == null;
    }
 
    public int search(Object o) {
        int index = 1;
        Node tempTop = top;
        
        while (tempTop != null) {
            if (tempTop.data.equals(o))
                return index;                
            tempTop = tempTop.nextNode;
            
            index++;
        }
        return -1;
    }
}