[자료구조] 05. 스택

스택은 한 쪽 끝에서만 항목을 저장하거나 삭제하는 자료구조이다.

일반적으로 저장하는 연산을 push, 삭제하는 연산을 pop 이라고 한다.

항상 가장 위(끝)에서 연산들이 수행되므로, 해당 항목을 가리키고 있는 레퍼런스가 필요하다.

스택 자료구조의 예를 들자면, 웹브라우저에서 뒤로 가기, 각종 편집기에서의 Ctrl + Z 를 생각해 볼 수 있다.

배열과 연결리스트로 다 구현할 수 있지만, 크기의 문제에 있어서 리스트 기반의 구현이 더 자유롭다.

 

아래는 스택 클래스를 연결리스트로 구현한 코드이다.

노드의 경우, 리스트에서 구현해놓았던 노드들을 재사용하였다.

private int size;
private Node<E> top;

public Stack()
{
	size = 0;			// 생성자에서는 각종 변수들을 초기화
	top = null;
}

public E top()		// 스택의 가장 위에(끝에) 있는 원소를 확인
{
	if(empty()) throw new EmptyStackException();
	return top.getItem();
}

public void push(E item)		// 스택에 원소 하나 삽입
{
	top = new Node<E>(item, top);	// 기존의 top 을 가리키는 노드를 만들어서 top 으로 설정
	size++;
}

public E pop()				// 스택의 top 을 제거 후 반환
{
	if(empty()) throw new EmptyStackException();
	E ret = top.getItem();
	top = top.getNext();		// 기존에 top 이 가리키던 다음 원소를 top 으로 설정
	size--;
	
	return ret;
}

public int size()
{
	return size;
}

public boolean empty()
{
	return size == 0;
}

 

스택 자료구조의 대표적인 응용에는 여러가지가 있다.

괄호 짝 맞추기, 팰린드롬 검사, 후위/중위 표기법 등등 다양하게 사용된다.

뿐만 아니라 미로 찾기, 트리 방문, DFS 깊이우선탐색 등을 수행하는데 기본이 되는 자료구조이다.

자바에서 메써드를 호출할 때에도 함수 스택이라는 자료구조를 바탕으로 처리를 하기 때문에, cs의 기본 중 기본이라고 할 수 있다.

 

수행시간

스택은 배열로 구현하든 리스트로 구현하든 상관없이 push 와 pop 이 O(1) 이다.

어차피 가장 위에 있는 원소만 조절하는데, 여기에 직접적으로 접근할 수 있기 때문이다.

배열로 구현한 경우에 스택의 크기를 확대/축소 시킬 경우엔 새로운 공간을 잡아 원소들을 전부 복사해야 하기 떄문에 O(N) 이다.

하지만 상각분석에 따르면 평균 수행시간은 O(1) 이라고 한다.