[자료구조]스택(stack)의 개념과 구현(Java)

stack이란 자료구조에 대해 알아보겠습니다.

 

스택(Stack)은 컴퓨터 과학에서 중요한 개념 중 하나입니다. 위에 테니스 공 통에 테니스 볼을 넣는 거와 같이 한쪽 끝에서 입력과 출력이 이루어지고 마지막에 들어간 공이 먼저 꺼낼 수 밖에 없는 것처럼(Last In First Out) 스택이란 자료구조도 동일하게 작동하는 자료구조 입니다.

 

스택이란?

• 삽입과 삭제 연산이 한쪽 끝에서 이루어지는 자료구조
• LIFO (Last In First Out)

 

스택을 구현할 수 있는 방법?

1. 배열→ 구현이 쉬우나 정적인 크기라 제한이 있음
2. 리스트 ( 연결리스트 )  → 구현이 배열에 비해 어려우나 자료구조의 크기가 동적이다는 장점이 있음

이 글에서는 배열로 구현한 예만 보여드립니다. 연결리스트 구현이 그렇게 어려운 것 아니므로 배열 구현을 보고 직접 구현해보시는 걸 추천합니다.

 

스택 기초 연산 함수

empty: 스택이 비어 있는지 검사

full: 스택이 가득 차있는지 검사

push: 스택에서 데이터를 삽입

pop: 스택에서 데이터를 삭제

 

 

스택  응용

• 함수호출, 미로 게임, 백 트래킹, 수식 계산 등, 재귀함수

 

배열 스택의 자료구조

• top 인덱스: 자료의 삽입과 삭제가 이루어지는 인덱스 변수

top 인덱스는 stack 배열의 마지막에 입력된 데이터를 가리키는 인덱스입니다.

• 자료 삽입(push): top++, 자료 삭제(pop): top—

삽입되거나 삭제되면 top이 제일 나중에 입력된 data를 가리키게 해야 합니다.

 

배열 스택 구현

public class Stack<E> {
    private E[] stack;
    private int top;
    private int size;

    public Stack(){
        this(10);
    }
    public Stack(int size){
        this.size = size;
        top = -1; //top의 초기값
        stack = (E[])new Object[size]; 
    }
    public boolean empty(){ 
        return top == -1; // stack이 비어있으면 true 아니면 false
    }
    public boolean full(){
        return top == size; // stack 이 가득차 있으면 ture 아니면 false
    }
    public void push(E data){ //삽입
        if (this.full()){
            return;
        }
        else{
            this.top++;
            this.stack[top] = data;
            return;
        }
    }
    public E pop(){ //삭제
        if (this.empty()){
            return null;
        }
        else{
            E temp = this.stack[top];
            top--;
            return temp;
        }
    }

}

 

 

수행시간

 1. 삽입(push) 함수 : O(1) 

 2. 삭제(pop) 함수 : O(1)

 

<이미지 참고>

- Applications of Stack in Data Structure - javatpoint

-