자료구조의 기초인 스택에 대해 알아보겠습니다.

스택

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조입니다. 따라서 스택에서 자료를 뺄 때에는 가장 최근에 넣은 것을 먼저 빼는 LIFO (Last In First Out)를 따릅니다.

스택에 원소를 삽입하는 것을 push라고 하고, 원소를 삭제하는 것을 pop이라고 합니다. 이 두 연산은 검색이 따로 필요없으므로 $O(1)$의 시간 복잡도를 가집니다.

스택에서 데이터를 검색할 수 는 없습니다. 하지만 pop을 해도 스택에서 데이터가 없어지지 않는다는 가정하에 스택의 i 번째 위치의 값을 검색하는 프로그램이 있다고 합시다. 이 프로그램이 스택을 검색하는 방식은 직접 접근이 아닌 순차 접근입니다. 따라서 스택은 배열보다는 링크드리스트와 가깝습니다. 사실 스택은 삽입과 삭제를 첫 번째 요소에서만 하는 링크드리스트의 단순 변형입니다.

배열로도 스택을 구현할 수 있습니다. 단, 배열을 사용 할 때에는 스택의 맨 위 원소를 가리키는 top이라는 변수가 필요합니다.

스택의 연산

고정된 크기의 스택이라 가정합니다.

• push(item) : 스택에 item을 삽입
• pop() : 스택에서 top에 있는 데이터를 삭제하고 그 값을 리턴

아래의 연산은 꼭 필요한 것은 아니고 부수적인 연산입니다.

• top() : top이 가리키는 원소를 리턴
• isempty() : 스택에 원소가 없으면 true, 있으면 false 값 리턴
• isfull() : 스택에 원소가 꽉 찼으면 true, 그렇지 않으면 false를 리턴
• size() : 스택에 들어있는 원소의 개수를 리턴

스택의 활용

• 수식의 괄호 검사

• 재귀 알고리즘

• 컴퓨터

스택의 구현

링크드리스트 이용

배열 이용