[ 개념 ] 22. 스택(Stack)

> 스택(STACK)이란?

---

스택의 개념

스택(stack)이란 쌓아 올린다는 것을 의미한다.

따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

스택의 특징

스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.

top에는 가장 위에있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.

스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.

스택에서 top을 통해 삽입하는 연산을 push, top을 통한 삭제하는 연산을 pop이라고 한다.

따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.

이러한 스택의 구조를 후입 선출(LIFO, Last-In-First-Out) 구조라고 한다.

비어있는 스택에서 원소를 추출하려고 할 때는 stack underflow라고 하며, 스택이 넘치는 경우에는 stack overflow라고 한다.(

그 유명한 사이트 *"stack overflow"*의 이름이 여기서 유래된 것이다.

)

스택의 활용 예시

스탭의 특징인 후입선출(LIFO)를 활용하여 여러 분야에서 활용 가능하다.

• 웹 브라우저 방문기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소(undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)

Stack Class

Stack 클래스는 List 컬렉션 클래스의 Vector클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공한다.

스택메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출(LIFO)의 시멘틱을 따르는 자료구조이다.

Stack 클래스는 스택 메모리 구조를 표현하기 위해, Vector 클래스의 메소드를 5개만 상속받아 사용한다.

메소드	설명
boolean empty()	해당 스택이 비어 있으면 true를, 비어 있지 않으면 false 반환
E peek()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환
E pop()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 요소를 스택에서 제거
E push(E item)	해당 스택의 제일 상단에 전달된 요소를 삽입함
int search(Object O)	해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환 이 때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함

더욱 복잡하고 빠른 스택을 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque클래스를 사용하면 된다.

Deque<Integer> st = new ArrayDeque<Integer>();

- 구현

import java.util.*;
public class Stack{

    public static void main(String[] args){
        Stack<Integer> st = new Stack<Integer>();        // 스택의 생성
        //Deque<Integer> st = new ArrayDeque<Integer>();

        // push() 메소드를 이용한 요소의 저장
        st.push(4);
        st.push(2);
        st.push(3);
        st.push(1);

        // peek() 메소드를 이용한 요소의 반환
        System.out.println(st.peek());
        System.out.println(st);

        // pop() 메소드를 이용한 요소의 반환 및 제거
        System.out.println(st.pop());
        System.out.println(st);

        // search() 메소드를 이용한 요소의 위치 검색
        System.out.println(st.search(4));
        System.out.println(st.search(3));
    }
}

# 실행결과
1
[4, 2, 3, 1]
1
[4, 2, 3]
3
1