자료구조 Stack - 정의, 특성, 구현

Stack

---

스택(stack)의 특성

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
• 스택에 저장된자료는 선형 구조를 갖는다
  • 선형 구조: 자료 간의 관계가 1대1의 관계를 갖는다
  • 비선형 구조: 자료 간의 관계가 1대N의 관계를 갖는다 (예: 트리)
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출(LIFO, Last-In-First-Out)이라고 부른다.
  • 예를 들어 스택에 1, 2, 3 순으로 자료를 삽입한 후 꺼내면 역순으로 3, 2, 1 순으로 꺼낼 수 있다.

스택의 구현

스택을 프로그램에서 구현하기 위해서 필요한 자료구조와 연산

• 자료구조: 자료를 선형으로 저장할 저장소
  • C언어에서는 배열 사용
  • 저장소 자체를 스택이라 부르기도 한다
  • 스택에서 마지막 삽입된 원소의 위치를 top이라 부른다
• 연산
  • 삽입: 저장소에 자료를 저장한다. 보통 push라고 부른다
  • 삭제: 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다. 보통 pop이라고 부른다.
  • 스택이 공백인지 아닌지 확인하는 연산: isEmpty
  • 스택의 top에 있는 item(원소)을 반환하는 연산: peek

스택의 삽입/삭제 과정

• 빈 스택에 원소 A, B, C를 차례로 삽입 후 한번 삭제하는 연산 과정

스택 구현 고려사항

• 1차원 배열을 사용하여 구현할 경우 구현이 용이하다는 장점이 있지만 스택의 크기를 변경하기가 어렵다는 단점이 있다
• 이를 해결하기 위한 방법으로 저장소를 동적으로 할당하여 스택을 구현하는 방법이 있다. 동적 연결 리스트를 이용하여 구현하는 방법을 의미한다. 구현이 복잡하다는 단점이 있지만 메모리를 효율적으로 사용한다는 장점을 가진다.