스택(Stack)

스택(Stack)

자료구조를 공부하면 제일 먼저 만나게 되는 스택(Stack) 게임을 좋아하는 사람들은 이미 스택에 대한 기본적인 느낌은 무엇인지 느낄 수 있을 것이다. 그렇다 스택은 바로 중첩 이라는 의미로 쌓이다라는 의미를 가지고 있는 말이다. 그렇다면 이러한 스택의 특성은 무엇인지 생각해보자. 

 

상자안에 있는 책들이 들어 있다고 보자 해당 박스안에 있는 제일 아래있는 책을 꺼내려면 어떻게 해야 하는가? 당연히 하나씩 꺼내서 빼야한다. 스택은 이렇게 맨마지막에 들어간 것을 제일 먼저 빼게 되는데 이것을 후입선출 멋진말로는 "Last In Fist Out ; LIFO "이라고 한다. 

 

종종 다른 곳에서는 선입후출 "First In Last Out;FILO" 라고도 하는데 스택의 기본적인 특성은 같은 것이니 헷갈리지 말자. 

 

https://kr.123rf.com/photo_52313446_%ED%9D%B0%EC%83%89-%EB%B0%B0%EA%B2%BD%EC%97%90-%EC%97%B4%EB%A0%A4-%EA%B3%A8-%ED%8C%90%EC%A7%80-%EC%83%81%EC%9E%90-%EC%95%88%EC%97%90-%EC%82%BD%ED%99%94%EA%B0%80-%ED%91%9C%EC%A7%80-%EC%8B%AC%EB%A6%AC%ED%95%99%EC%97%90-%EC%B1%85-.html

이러한 스택(Stack) 자료구조는 어디에 사용 되는 것일까? 제일 간단하게 생각하면 입력된 데이터를 역순으로 출력 또는 처리 되어져야 할 때 가장 많이 사용이된다. 그리고 함수 콜 스택의 기본 자료구조이자 수식 계산 및 인터럽트 처리에 사용이 된다.

 

인터럽트 처리
갑작스럽게 발생한 일을 처리하는 과정. 
ex ) 길가다가 돈을 발견 하면 가던 길을 멈추고, 다시 돈을 줍고 난후, 원래 가던 길로 가는 것과 같은 원리. 

 

콜스택 
스택에 있는 함수가 다른 함수를 호출 하게 되면 자신을 먼저 처리 하는 것이 아닌 호출한 함수를 먼저 처리하고 이후 자신이 처리되는 것이 스택 구조와 같다.

---

스택 용어

스택에서 사용되는 용어는 총4가지가 대표적이다. (push, pop, top, bottom) 각 용어에 대해서 하나씩 정리해보고자 한다. 

• push : 스택의 가장 마지막 위치에 데이터를 추가하는 것.

• pop : 스택의 가장 마직막 위치에서 데이터를 꺼내는 것.

• bottom : 스택에 가장 먼저 쌓인 데이터
• top : 스택에 가장 나중에 쌓인 데이터 

 

---

시간 복잡도 

• Insertion O(1)
• Deletion O(1)
• Search O(n)

---

자바에서 지원하는 스택 클래스 및 함수

• 스택 초기화 방법 및 인스턴스화 방법
  • new 연산자를 통한 인스턴스화 가능.  
  • 지네릭스를 사용하면 타입을 제한하여 사용이 가능함. (타입 다운 캐스팅 작업을 하지 않아도 됨)

Stack stack = new Stack();
Stack<Integer> stack = new Stack();

• .push() : Stack에 데이터를 쌓는 것을 말함.

stack.push(1);

• .pop() : Stack의 Top에 있는 값을 꺼내는 것. (한번 하면 소멸이 되고 꺼내자 마자 바로 출력이 가능함.

System.out.println(stack.pop()); // pop 되는 값만 바로 출력가능

• .peek() : Stack의 Top에 있는 값을 보여줌. (pop과 달리 stack 내에서 사라지지 않음.)

System.out.println(stack.peek()); // 스택에 가장 마지막에 들어간 값을 출력.

• .contains() : 매개변수의 값이 stack에 존재하는지 확인 가능함.(boolean 값으로 반환이 됨.)

System.out.println(stack.contains(1)); // 스택에 해당 값이 들어 있는지 확인가능

• .size() : 스택의 현재 사이즈를 확인이 가능함. (데이터가 얼마나 들었는 가에 따라 달라짐)

System.out.println(stack.size()); // 스택의 사이즈를 확인이 가능함.

• .empty() : 스택이 현재 비어있는지 확인 가능함. (boolean 값으로 반환이 됨)

System.out.println(stack.empty()); // 스택이 비어있는지 확인이 가능함.

• .clear() : Stack에 있는 모든 값들 초기화 시킴.
  • 초기화가 된 이후에 pop() 을 수행하게 되면 EmptyStackException이 발생이 됨. 

stack.clear(); // 스택에 있는 값들을 비울 수 있음.
stack.pop(); // 비워져 있는 스택에서 팝을 하게 되면 EmptyStackException 이 발생함.