[자료구조] 03. 스택(Stack)

스택(Stack)

스택은 데이터를 제한적으로 접근할 수 있는 자료구조이다. 앞선 글에서 설명한 큐는 FIFO 방식을 사용하는 자료구조이다. 스택은 LIFO(Last-In, First-Out) 방식을 사용하는 자료구조이다. 즉, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 자료구조라고 할 수 있다.

이 자료구조가 활용되는 대표적인 예시로는 우리가 지금 사용하고 있는 Java의 JVM이다. JVM에는 메서드 호출 시, 스택 메모리에 메서드가 담기는데 이 때 스택 자료구조가 활용된다. 예를 들어 A메서드 안에서 B메서드를 호출한다고 가정해보자.

그럼 A메서드가 스택 영역에 할당되고, 그 다음 B메서드를 호출하는 부분에서 B메서드가 할당될 것이다. 당연하게도 메서드의 흐름상 B메서드가 먼저 동작이 끝날테니 B메서드가 먼저 메모리에서 제거되어야 한다. 이 내용이 바로 LIFO 방식을 말한다.

위의 이미지에서 push, pop이라는 용어가 나오는데 설명하자면 아래와 같다.

• push : 스택에 값을 넣는 기능
• pop : 스택에서 값을 꺼내는 기능

 

push

push는 값을 넣는 기능이다. 큐는 양쪽에서 데이터의 추가, 삭제가 일어난다고 하면, 스택은 한쪽에서 데이터의 추가, 삭제가 일어난다.

위의 그림처럼 1이라는 값을 스택에 push한다고 하면 맨 윗 부분을 통해서 값이 추가된다. 이를 자바 코드로 표현해보도록 하자.

자바에서는 컬렉션 프레임워크에 스택 자료구조를 제공하고 있다.

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

stack.push(1);

위와 같이 자바에서 제공하는 스택 자료구조에 push 메서드를 사용하면 위의 그림과 같이 동작된다.

 

 

pop

pop은 값을 빼는 기능이다. 삭제 역시 맨 윗부분에서 삭제가 일어난다.

pop 역시 자바에서 메서드를 지원하고 있기 때문에 아래의 코드로 사용한다.

stack.pop();

//pop한 값을 사용하고 싶다면
int temp = stack.pop();

System.out.println(temp);

 

스택은 맨 윗부분에서 추가, 삭제가 이루어지기 때문에 추가, 삭제는 O(1)의 시간복잡도를 갖는다. 하지만 검색은 결국 값을 모두 순회하여 찾아야하기 때문에 O(n)의 시간복잡도를 갖는다.

---

시간복잡도

• 추가, 삭제 : O(1)
• 검색 : O(n)