Stack

stack

• 나중에 들어간 것이 먼저 나오는 구조

• 선입후출, LIFO, last in first out

• 입구와 출구가 동일한 형태로 스택을 시각화

  • 예) 박스쌓기, 접시쌓기 등

• 예시

  • 그래프의 깊이 우선 탐색(DFS)에서 사용한다.

  • 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때, 스택 메모리의 영역에서 한다.

  • 컴퓨터 사칙연산 계산에서 후위표기법

  • 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰인다.

  • 백트래킹, 인터넷 사용기록 보관

  • 브라우저의 뒤로가기

  • 실행취소

  • 재귀함수

  • 역순문자열 - 문자열 거꾸로 뒤집기

• 장단점

  • top 를 통해 접근해서 데이터 접근, 삽입, 삭제가 빠르다.

  • top 위치 이외의 데이터에 접근할 수 없다. 그래서 탐색에는 모든 요소를 꺼내서 진행해야한다.

• 시간 복잡도

  • 삽입과 삭제 : O(1)

  • 탐색 : O(n)

• 구현

  • java.util.Stack import 하면 바로 사용 가능함

• 지원 매소드

  • push : 삽입

  • peek : 최상단 원소 출력

  • isEmpty, empty : 스택이 비어있다면 true, 아니면 false

  • pop : 삭제

예시

package practice.algorithm.stackqueue;

import java.util.Stack;

public class StackPractice {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();

        stack.push("h");
        stack.push("e");
        stack.push("l");
        stack.push("l");
        stack.push("o");
        System.out.println("stack = " + stack);

        System.out.println("stack.empty() = " + stack.empty());

        System.out.println("stack.peek() = " + stack.peek());
        System.out.println("stack = " + stack);

        System.out.println("stack.pop() = " + stack.pop());
        System.out.println("stack.pop() = " + stack.pop());
        System.out.println("stack = " + stack);

        while(!stack.empty()) {
            System.out.println("stack.pop() = " + stack.pop());
        }
        System.out.println("stack = " + stack);
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
    }
    
    /*
    stack = [h, e, l, l, o]
    stack.empty() = false
    stack.peek() = o
    stack = [h, e, l, l, o]
    stack.pop() = o
    stack.pop() = l
    stack = [h, e, l]
    stack.pop() = l
    stack.pop() = e
    stack.pop() = h
    stack = []
    stack.isEmpty() = true
    */
}