20230708 [자료구조] 스택(stack)

스택(stack)이란?

제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다.

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조로 되어 있다.

• 푸쉬(push) : 자료를 넣는 것
• 팝(pop) : 넣어둔 자료를 꺼내는 것
  이때 꺼내지는 자료는 가장 최근에 push한 자료부터 나오게 된다. (후입선출 구조)

후입 선출(後入先出) 또는 LIFO(last in, first out)

컴퓨터 과학에서 어떠한 종류의 데이터 구조에 저장되어 있는 항목들이 처리되는 것을 말한다. LIFO 구조화 선형 목록에서, LIFO 요소는 맨 위의 항목만 추가하거나 제거할 수 있다.

스택에서, 마지막에 추가된 맨 위의 항목은 처음 끄집어 낼 수 있다. 그러므로 스택은 LIFO 구조이다.

스택 연산

S를 스택, x를 데이터 요소(element)라고 하자.

• S.top(): 스택의 가장 윗 데이터를 반환한다. 만약 스택이 비었다면 이 연산은 정의불가 상태이다.
• S.pop(): 스택의 가장 윗 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.
• S.push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터 x를 넣는다.
• S.empty(): 스택이 비었다면 1을 반환하고,그렇지 않다면 0을 반환한다.