Stack이란 무엇인가?

Stack이란?

정의 : 스택은 컴퓨터의 기본 자료구조 중 하나로 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

---

Stack의 특징

• 특징
  • 가장 최근에 들어온 자료가 가장 먼저 나가게 되는 LIFO(Last-In First-Out) 형태를 갖는다.
  • 스택의 입출력은 맨 위에서만 일어나기 때문에 스택의 중간에서는 데이터를 삭제하는 것이 불가능 하다.
  • 스택 용어 
    • 스택이 입출력이 이루어지는 부분을 스택 상단(Stack top)
    • 스택 바닥 부분을 스택 하단(Stack bottom) 
    • 스택에 저장되는 데이터를 요소(Element) 
    • 스택에 요소가 하나도 없을 때 공백 스택(Empty stack) 
    • 스택에 요소를 삽입하는 연산을 Push()연산
    • 스택에 요소를 삭제 연산을 Pop()연산

• 장점

  • 구조가 단순해 구현이 쉽다

  • 데이터 저장/읽기 속도가 빠르다

    
    
• 단점

  • TOP 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능하다.
    ⇒ 탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.
    

  • 데이터 최대 갯수를 미리 정해야한다
    ⇒ 예를 들어 재귀함수의 최대 호출 수가 지정되어 있다.
    

  • 미리 최대 갯수를 정하여 저장공간의 낭비가 발생할 수 있다.

    
    

---

Stack은 왜 사용하는가

• C/C++의 main() 함수안에서 사용되는 지역변수와 함수들은 모두 스택의 자료구조에 의하여 관리된다.

• 스택을 활용하면 "재귀함수"를 필요로하는 소스코드에 "재귀함수"를 사용하지 않고 반복문을 통해 구현할 수 있다.

• 웹 브라우저의 방문기록에서 스택을 활용하여 "뒤로가기"를 구현할 수 있다.

• 프로그램의 실행취소(Undo)에서 활용된다.

---

Java의 Stack 사용

• 스택의 선언

    // 스택 선언
            import java.util.Stack; 
            Stack<Integer> stack = new Stack<>(); 
            Stack<String> stack = new Stack<>(); 

• 스택의 주요 메소드

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

---

Stack의 시간복잡도

push		  : O(1) // 요소 삽입
pop   		  : O(1) // 요소 첫번째 요소 삭제 및 반환
peek		  : O(1) // 요소의 첫번째 요소 반환
search		  : O(n) // 요소의 인덱스 위치 반환 (인덱스 번호는 1부터 시작)