[자료구조][JAVA] 스택(Stack)

자료구조 중 스택에 대해서 알아보자!!!

 

개념

💡스택이란??

톱(top)이라고 하는 한쪽 끝에서 모든 삽입(put이나 push라고 한다.)과 삭제(removal이나 pop이라고 한다.)가 일어나는 순서 리스트이다. 

 

특징

• 제일 마지막으로 삽입된 원소가 제일 먼저 삭제되기 때문에 후입선출(LIFO: Last-In-First-Out)리스트라고도 한다.
• 원소의 추가 O(1)
• 원소의 제거 O(1)
• 제일 상단의 원소 확인이 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다.

구조

class Stack{
    int size = 10000;
    int[] save;
    int pos = -1;
    public Stack(){
        save = new int[size];
    }
    public void push(int x){
        pos++;
        save[pos] = x;
    }
    public void pop(){
    	if(pos == -1){
        	return;
        }
        save[pos] = 0;
        pos--;
    }
    public int top(){
        return (save[pos]);
    }
    public boolean IsEmpty(){
        if(pos == -1){
            return true;
        }
        else
        {
            return false;
        }
    }
}

속성 

size : 스택의 허용 범위

save : 들어온 값을 저장하고 있는 위치

pos : 현재 가리키고 있는 Index

메소드

push() : 스택에 데이터를 삽입

pop() : 스택의 톱에 있는 원소를 삭제

top() : 스택의 톱에 있는 원소를 반환

IsEmpty() : 스택에 데이터가 있는지 없는지(있다면 false, 없다면 true)

 

자바를 통해서 다음과 같이 구현하는게 가능할 거 같다.

초기에 pos를 -1에 위치시키는 방법도 가능하지만 0에 위치시켜서 표현했다.

 

물론 자바에서는 Stack클래스를 이미 제공하고 있다!!

 

class Stack<E> extends Vector<E> {
    public Stack(){}
    public E push(E item) {
        addElement(item);
        return item;
    }
    public synchronized E pop() {
        E obj;
        int len = size();
        obj = peek();
        removeElementAt(len -1);
        return obj;
    }
    public synchronized E peek(){
        int len = size();

        if(len == 0)
            throw new EmptyStackException();
        return elementAt(len -1);
    }
    public boolean empty() {return size() == 0;}
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);
        if(i >= 0){
            return size() - i;
        }
        return -1;
    }
}

 

다음과 같은 형태로 

• push()
• pop()
• peek()
• empty() 

메소드를 제공하고 있는데 기본적인 틀은 비슷하지만 자바에서 제공해주고 있는 스택은 Vector를 상속하고 있는 부분에서 차이가 있다!

 

이런 형태로 상속과 구현을 받고 있다는 것도 알고 있으면 좋을 거 같다.