특징

• 스택은 가장 늦게 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out)형태의 자료구조이다.
• 데이터 한 쪽 에서만 자료를 넣고 뺄 수 있다.

연산

1. push()

push() 연산은 스택에 데이터를 push, 즉 삽입하는 연산이다.

현재 스택의 가장 최근의 들어온 데이터(가장 상단에 위치한 데이터)를 top이 가리키게 된다.
push 연산을 하게 될 경우 현재 top이 가리키는 데이터 위에 데이터를 추가한 뒤, 추가된 데이터를 top이 가리킨다.

2. pop()

pop() 연산은 스택에 데이터를 pop, 즉 꺼내는 연산이다.

현재 스택에서 top이 가리키고 있는 데이터를 꺼낸 후, 현재 스택에서 최상단에 위치한 데이터를 top이 가리키게 된다.
만일 꺼낼 데이터가 없을 경우에는 pop 연산이 실행되지 않는다.

3. peek()

peek() 연산은 현재 top이 가리키고 있는 데이터를 확인하는 연산이다.
이때 pop()과의 다른 점이라면, pop연산은 데이터를 stack에서 꺼내서 읽는다면 peek 연산은 데이터를 꺼내지 않고 값만 읽는 것이다.

4. isEmpty()

isEmpty() 연산은 현재 stack이 비어있는지 확인하는 연산이다.
stack이 비어있다면 true, 비어있지 않다면 false를 반환한다.

시간복잡도

연산	복잡도
Insertion	O(1)
Deletion	O(1)
Selection	O(n)

O(1)이라는 표현에서 1은 constant 즉, 상수 시간을 말한다.

삽입 연산의 경우, 데이터의 개수에 상관없이 맨 위에 데이터를 삽입하는 연산만 진행하므로 O(1)이다.

삭제 연산도 삽입연산과 마찬가지로 맨 위에 있는 데이터를 꺼내는 연산만 진행하므로 O(1)이다.

검색 연산의 경우는 현재 stack에 존재하는 모든 데이터를 찾는 것이므로 데이터가 n개라면 n개를 순회해야 하기 때문에 O(n)이다.

장단점

장점

• 데이터의 삽입과 삭제가 빠르다.
• 구현이 쉽다.

단점

• 맨 위의 원소만 접근 가능하다.
• 탐색을 하려면 원소를 하나하나 꺼내서 옮겨가면서 해야한다.

사용 사례

• 재귀 알고리즘
• 역순 문자열 만들기
• 시스템 스택

예제코드

Java

Stack

자바에서는 기본적으로 Stack 객체를 제공해준다.

import java.util.Stack;

public class StackExample {

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
       
        stack.push(5);
        stack.push(4);
        stack.push(3);
        stack.push(2);
        stack.push(1);
       
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
       
        System.out.println("---------------");
       
        stack.push(5);
        stack.push(4);
        stack.push(3);
       
        System.out.println(stack.size());
        System.out.println(stack.peek());
        System.out.println(stack.size());
       
    }
}

배열

Stack 객체를 사용하지 않고 배열로 구현한다면 다음과 같이 구현할 수 있다.

import java.util.NoSuchElementException;
 
public class Stack_arr <E> {
    private E a[];
    private int top;
    
    public Stack_arr() {
        a = (E[]) new Object[1];
        top = -1;
    }
    //동적인 배열을 만들기 위해 resize()함수를 만든다.
    public void resize(int length) {
        E b[] = (E[]) new Object[length];
        for(int i=0; i<top+1; i++) b[i] = a[i];
        a = b;
    }
    
    public void push(E item) {
        if(top+1 == a.length) resize(2*a.length);
        a[++top] = item;
    }
    
    public E pop() {
        if(isEmpty()) throw new NoSuchElementException();
        if(top == a.length/4) resize(a.length/2);
        E pop = a[top];
        a[top] = null;
        top = top-1;
        return pop;
    }
    
    public E peek() {
        if(isEmpty()) throw new NoSuchElementException();
        return a[top];
    }
    //배열에서는 맨 뒤가 top이 된다.
    public void show() {
        for(int i=0; i<=top; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.print("\t<--top");
        System.out.println();
    }
    
    public boolean isEmpty() {
        return top==-1;
    }
    
    public int getSize() {
        return top+1;
    }
}

Kotlin

코틀린은 따로 Stack 객체가 존재하지 않는다.
그래서 Kotlin에서는 MutableList와 ArrayList로 대신 Stack을 구현할 수 있다.

MutableList

fun main() {
    var mutableList = mutableListOf<Int>()

    mutableList.add(1)
    mutableList.add(2)
    mutableList.add(3)

    mutableList.removeAt(mutableList.size-1)

    print(mutableList[mutableList.size-1])

    println(mutableList.isEmpty())
    println(mutableList.isNotEmpty())

    println(mutableList.size)
}

ArrayList

fun main() {
    var arrayList = arrayListOf<Int>()

    arrayList.add(1)
    arrayList.add(2)
    arrayList.add(3)

    arrayList.removeAt(arrayList.size-1)

    print(arrayList[arrayList.size-1])

    println(arrayList.isEmpty())
    println(arrayList.isNotEmpty())

    println(arrayList.size)
}