자료구조 - Stack

Stack

---

stack 자료구조

• 후입선출 알고리즘으로 나중에 들어온 데이터를 먼저 반환한다. 
• 시간 복잡도
  1. insert: O(1)
  2. delete: O(1)
  3. search: O(n)

 

구현 with JAVA

public class Stack {
    private int top;
    private int size;
    private int[] arr;
 
    //생성자
    public stack(int size) {
        top = -1;
        this.size = size;
        arr = new int[size];
    }
 
    public boolean inEmpty() {
        return top == -1;
    }
 
    public boolean isFull() {
        return top == size - 1;
    }
 
    //스택에 item insert
    public void push(int item) {
        if(isFull()) return; //스택에 정보를 저장하기 전에 꽉 찼는지 검사
        arr[++top] = item;
    }
 
    //top 조회
    public void peek() {
        if(isEmpty()) return; //스택의 정보를 조회하기 전에 데이터가 있는지 검사
    }
 
    //top 반환(조회 후 삭제)
    public void pop() {
        if(isEmpty()) return; // 데이터가 있는지 검사
        return arr[top--];
    }
 
    //top으로부터 item의 위치를 반환
    public int serach(int item) {
        if(isEmpty()) return -1;
        for(int i = 0; i <= top; i++) {
            if(item == arr[i]) return top - i - 1;
        }
        return -1; //못 찾았을 경우
     }
}

 

reference