[Data Structure] Stack 스택, array 로 구현하기 (java)

Stack

LIFO (Last In First Out : 후입선출) 형태를 갖는 자료구조.

임시로 자료를 저장하고 꺼내서 사용하는 임시 버퍼와 같다.

java 메모리구조에서 new 연산자로 생성된 인스턴스 등이 Stack 으로 관리된다.

 

일상생활에서 Stack과 가장 밀접한 예로 장독대를 들 수 있다.

김치를 넣고 꺼낼 때 가장 나중에 넣은 김치를 가장 먼저 꺼내야 하는 구조이므로 Stack과 같다.

 

[java.util.Stack 의 기본적인 사용예]

package algo_datastructure.stack;
 
import java.util.Stack;
 
public class BasicUsageOfStack {
    public static void main(String[] args) {
 
        Stack<Integer> s = new Stack<>();
        s.add(1);
        s.add(2);
        s.add(3);
 
        System.out.println(s.peek());
 
        while(!s.isEmpty()) {
            System.out.println(s.pop());;
        }
        
    }
}
 

add로 stack에 값을 넣는다. (push와 같음)

peek으로 stack 내에서 가장 위에 위치한 데이터를 꺼낸다.(데이터는 그대로 둔다)

pop으로 stack 내에서 가장 위에 위치한 데이터를 꺼낸다.(데이터를 꺼내고 지운다)

 

 

[Array로 구현한 Stack]

package algo_datastructure.stack.stackbyarray;
 
public class Stack {
    private int[] array = new int[100];
    private int lastIdx = 0;
    
    public Stack () {
    }
    
    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }
    
    public int pop() {
        lastIdx--;
        int top = array[lastIdx];
        array[lastIdx] = 0;
        
        return top;
    }
    
    public int peek() {
        return array[lastIdx-1];
    }
    
    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}
 

[사용]

package algo_datastructure.stack.stackbyarray;
 
public class Main {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.add(1);
        s.add(2);
        s.add(3);
        System.out.println(s.peek());
        while(!s.isEmpty()) {
            System.out.println(s.pop());
        }
    }
}