[자료구조] 스택(Stack)

스택(Stack)이란

한쪽으로만 넣고 뺄 수 있는 LIFO(Last In First Out), 즉 후입선출 구조의 자료구조

Ex) 쌓여있는 접시들, 상자들

스택의 정의, 연산

• pop() : 스택에서 가장 위의 item을 제거. 
• push(item): 스택에서 가장 위에 item 하나 추가.
• peek(): 스택에서 가장 위의 item 반환
• isEmpty(): 스택이 비어있으면 true, 그렇지 않으면 false 반환

배열로 스택 구현

public class ArrayStack{
    private int top;
    private int size;
    private char array[];

    public ArrayStack(int size){
        this.top = -1;
        this.size=size;
        this.array=new char[this.size];
    }

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

    public void push(char item){
        if(isFull()){
            System.out.println("Stack is Full!");
        }else
            array[++top]=item;
    }

    public char pop(){
        if(isEmpty()){
            System.out.println("Stack is Empty!");
            return 0;
        }else
            return array[top--];
    }

    public char peek(){
        if (isEmpty()){
            System.out.println("Stack is Empty!"); 
        }else{
            return array[top];
        }return 0;
    }
}

연결리스트로 스택 구현

package Stack2;

import java.util.NoSuchElementException;

public class LinkedStack {
    private static class StackNode{
        private char data;
        private StackNode next;

        public StackNode(char data){
            this.data = data;
        }
    }
    private StackNode top;

    public char pop(){
        if(top == null)
            throw new NoSuchElementException();
        char item = top.data;
        top = top.next;

        return item;
    }

    public void push(char item){
        StackNode t = new StackNode(item);
        t.next= top;
        top = t;
    }

    public char peek(){
        if(top == null)
            throw new NoSuchElementException();
        return top.data;
    }

    public boolean isEmpty(){
        return top == null;
    }

}

활용예시

• 웹 브라우저 방문기록 (뒤로가기)
• 재귀 알고리즘
• 실행취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
• 후위표기법 계산