스택(Stack)이란
스택이란, LIFO(Last-In-First-Out), 후입선출(가장 뒤에 들어온 것이 가장 먼저 나가는 구조)의 방식을 따라 데이터를 쌓는 자료구조이다. 스택을 활용한 예들은 다음과 같다.
- 키보드 입력을 하다 백스페이스 키를 누르면 최근에 입력한 글자를 지움
- 한글, 워드, 파워포인트, 엑셀 등의 모든 편집기는 최근에 한 작업순의로 취소하는 기능이 있음
스택의 개념과 원리
스택은 맨 위의 원소만 접근 가능하다. 이 맨 위의 원소를 탑(top)이라고 하며, 새 원소를 삽입할 경우에는 탑 위에 바로 저장한 후, 새 원소가 탑이 된다. 반대로 원소를 삭제할 때는 무조건 탑에 있는 원소를 삭제한 후 바로 아래의 원소가 탑이 된다. 추가적으로 내용을 알려달라고 요청하면 맨 위에 있는 것을 알려주기도 한다. 다음 그림이 스택에서 행해지는 작업을 그림으로 나타낸 것이다.
일반적인 가상 메모리 구조에도 스택은 활용된다. 이 구조에는 정적 영역과 동적 영역이 존재하는데, 정적 영역에는 프로그램 수행 코드와 프로그램이 끝날 때까지 존재하는 데이터(전역 변수 및 정적 변수 등)이 존재한다. 동적 영역에는 프로그램 수행 중 할당받는 메모리(heap)와 함수가 다른 함수를 호출할 때의 정보를 저장하는 스택 영역이 있다.
또한 위의 그림은 함수 호출 시 스택이 어떤 식으로 활용되는지 보여준다. 수행을 마친 함수가 스택 영역에서 지워지면 다시 자신을 호출했던 함수의 정보가 스택의 맨 위에 존재하게 되는 구조가 프로그램이 수행되는 경로를 효율적으로 따라갈 수 있게 해준다.
배열을 이용한 스택
배열을 이용한 스택 객체는 다음과 같이 stack[]과 topInedx 필드, 그리고 5개의 메서드로 구성된다. 여기서의 topIndex 변수는 스택에서 맨 위쪽 원소의 자리를 가리키는 배열 인덱스를 저장하는 변수이다.
이제 배열 스택의 작업을 하나씩 알아보자.
- 원소 삽입
스택에 새 원소를 삽입할 때는 탑 바로 윗자리에 원소를 저장 후 탑 인덱스를 1 증가시킨다. 이를 그림 및 알고리즘으로 처리하면 다음과 같다.
- 원소 삭제
스택의 원소를 삭제할 때는 무조건 탑의 원소를 삭제한 후 탑 인덱스를 1 감소시킨다. 탑 인덱스가 감소하게 되면 탑의 원소를 물리적으로 삭제하지 않아도 탑 인덱스가 내려가서 관심대상에서 제외된다.
연결 리스트를 이용한 스택
연결 리스트 스택을 사용한다면 스택을 연결 리스트로 구성하고 연결 리스트의 어느 쪽을 탑으로 삼을 것인지를 결정해줘야 한다. 연결 리스트를 활용한 스택의 구조는 다음과 같다. 메서드 5개는 배열을 이용한 스택과 동일하다.
연결 리스트에서도 원소 삽입 및 삭제 작업을 알아보도록 하자.
-
원소 삽입
스택에 새 원소를 삽입할 때 이므로 역시 새 원소를 무조건 맨 위에 놓고, 맨 앞에 새 노드를 삽입하고 스택 탑 레퍼런스를 새 노드로 바꾸어준다. 배열 스택과 다른 점은 배열 스택에서는 스택이 꽉 차 있으면 삽입이 불가능했는데, 연결 리스트 스택에서는 노드를 만들어 붙이기 때문에 삽입을 못하는 경우는 없다.
-
원소 삭제
스택에서 원소를 삭제할 때는 무조건 탑 원소를 삭제한다.
스택 응용
문자열 뒤집기 작업을 스택으로 할 수 있다. 입력 문자열이 끝날 때까지 push()를 통해 스택에 차례로 저장하고, 스택이 빌 때까지 pop()을 통해 하나씩 빼면서 출력 스트링 뒤에 붙여주는 작업을 하면 된다.
이미지 출처: [쉽게 배우는 자료구조 with 자바] - 문병로
