[Java-자료구조] Stack 사용과 구현

Stack

• 선형 자료구조
• 한 쪽 끝에서 자료를 넣고 뺄 수 있는 LIFO구조의 자료구조
• 사용 분야: 함수 호출 순서의 제어, 인터럽트 처리, 수식 계산, 재귀적 문제를 동적 프로그래밍 방식으로 해결 

Stack

멤버변수: top(현재 위치)

 

Stack 사용법

import java.util.Stack;

자바는 java.util.Stack Class를 통해 Stack을 제공하고 있다.

 

Stack 선언

Stack<Integer> s = new Stack();

Stack의 경우 생성자가 하나뿐이다.

 

Stack 메서드

데이터 삽입

stack.push(E element); // element를 stack의 top에 추가

 

데이터 삭제

stack.pop(); // 스택의 제일 위에 있는 element를 반환하고 스택에서 제거

 

데이터 검색

stack.empty();  // 스택이 비어있는지 여부 반환
stack.peek(); // top에 있는 element 반환
stack.search(Object O); // 해당 Object가 있는 1-based position을 반환

 이것들 외에도 일반적으로 Stack이 java.util.Vector를 상속받고 있기 때문에 Vector에 있는 add나 clear와 같은 것들도 모두 다 사용이 가능합니다.

 

Stack 시간복잡도

동작	시간복잡도 Big O
Insertion	O(1)
Deletion	O(1)
Search	O(N)

탐색시 모든 데이터를 꺼내가며 진행해야 함.

---

Stack 장단점

장점

• 구조가 단순하여 구현이 쉬움
• 데이터의 저장과 읽기 속도가 빠름
• 참조 지역성 반영 가능

단점

• 배열로 구현하는 경우 데이터의 최대 개수를 정해놓아야 하며 확보해둔 만큼 저장공간의 낭비가 발생가능함
• 데이터의 탐색이 어려움

 

---

구현

stack 인터페이스

/**
 * 자바 Stack Interface<br>
 * Stack은 Array, ArrayList, DoublyLinkedList에 의해 각각 구현합니다.
 *
 * @param <E> the type of elements in this Stack
 */

public interface Stack<E>  {

    /**
     * 리스트가 비어있는지 여부를 반환합니다.
     *
     * @return 리스트에 요소가 없는 경우 {@code false} 요소가 있는 경우 {@code true}
     */
    boolean empty();

    /**
     * top에 위치한 요소를 반환합니다.
     *
     * @return   top에 위치한 요소를 반환하고 없다면 -1을 반환
     */
    E peek();

    /**
     * 리스트가 비어있는지 여부를 반환합니다.
     *
     * @return   top에 위치한 요소를 삭제하고 반환하며 없다면 -1을 반환
     */
    E pop();

    /**
     * 스택의 top부분에 element를 추가합니다.
     *
     * @param element top부분에 넣을 요소
     * @return 리스트에 요소가 없는 경우 {@code false} 요소가 있는 경우 {@code true}
     */
    E push(E element);

    /**
     * 특정 요소의 위치(1-based)를 반환합니다.
     *
     * @param element 찾을 요소
     * @return 찾는 요소의 index를 반환하며 없다면 null을 반환
     */
    int search(E element);
}

Array를 이용한 구현

public class ArrayStack<E> implements Stack<E> {
    private int top;
    static final int MAX_SIZE = 100;
    private E[] stack;

    ArrayStack(){
        top= -1;
        stack = (E[])new Object[MAX_SIZE];
    }

    @Override
    public boolean empty(){
        return top==-1;
    }

    public boolean isFull(){
        return top==MAX_SIZE-1;
    }

    @Override
    public E push(E element){
        E result;
        if(this.isFull()){
            throw new IndexOutOfBoundsException();
        }else{
            top++;
            stack[top] = element;
            result = element;
        }
        return result;
    }

    @Override
    public int search(E element) {
        int index = -1;
        for(int i=0;i<=top;i++){
            if(element.equals(stack[i])){
                index = i;
                break;
            }
        }
        return index + 1;
    }

    @Override
    public E pop(){
        E data = null;
        if(this.empty()) {
            throw new IndexOutOfBoundsException();
        }else{
            data = stack[top];
            stack[top]=null;
            top--;
        }
        return data;
    }

    public int capacity(){
        return MAX_SIZE;
    }

    public int size() {
        return top + 1;
    }

    @Override
    public E peek(){
        E data = null;
        if(empty()){
            throw new IndexOutOfBoundsException();
        }else{
            data = stack[top];
        }
        return data;
    }

    public void clear() {
        int tmp = top;
        for (int i = 0; i <= tmp; i++) {
            stack[i] = null;
            top -= 1;
        }
    }
}

LinkedList를 이용한 구현

public class LinkedListStack<T> extends DoublyLinkedList<T> implements Stack<T> {
    private int top;

    LinkedListStack(){
        super();
        top = -1;
    }

    @Override
    public T push(T element){
        top++;
        this.add(element);
        return element;
    }

    public T pop(){
        T data = null;
        if(this.isEmpty()){
            throw new IndexOutOfBoundsException();
        }else{
            data = this.getLast();
            this.removeLast();
            top--;
        }
        return data;
    }

    @Override
    public int search(T element) {
        int index = this.indexOf(element) + 1;
        return index;
    }

    public int size(){
        return top + 1;
    }

    @Override
    public boolean empty(){
        return top == -1;
    }

    public T peek(){
        return this.getLast();
    }

    public void clear(){
        super.clear();
        top = -1;
    }

}

DoublyLinkedList가 필요하신 경우 이 글을 참조해주세요.

2022.01.16 - [JAVA/자료구조] - [Java-자료구조] LinkedList 사용과 구현

---

알고리즘 사용 사례 with Stack

• 재귀 알고리즘
• 수식 괄호 검사 알고리즘
• DFS 알고리즘
• 문자열 역순 출력, 후위 연산법