📖 Stack 1

📌 Stack

✅ 스택의 특성

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

• 스택에 저장된 자료는 선형 구조를 갖는다.

  • 선형 구조 : 자료 간의 관계가 1대1의 관계를 갖는다.
  • 비선형 구조 : 자료 간의 관계가 1대N의 관계를 갖는다. (트리)

• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다. (한쪽에서만 가능)

• 마지막에 삽입한 자료를 가장 먼저 꺼낸다.

  • 후입선출(LIFO, Last-In-First-Out)이라고 부른다.

✅ 스택의 구현

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

• 자료구조 : 자료를 선형으로 저장할 저장소

  • 저장소 자체를 스택이라 부르기도 한다.
  • 스택에서 마지막 삽입된 원소의 위치를 top이라고 부른다.

• 연산

  • 삽입 : 저장소에 자료를 저장한다. 보통 push라고 부른다.
  • 삭제 : 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다. 보통 pop이라고 부른다.
  • 스택이 공백인지 아닌지 확인하는 연산 : isEmpty
  • 스택의 top에 있는 item(원소)를 반환하는 연산 : peek (확인)

✅ 스택의 삽입 / 삭제 과정

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

• push : O(1)

• pop : O(1)

• peek : O(1)

모두 상수 연산

✅ 스택 구현 고려 사항

• 1차원 배열을 사용하여 구현

  • 구현이 용이
  • 스택의 크기를 변경하기 어렵다.

• 저장소를 동적으로 할당하여 스택을 구현하는 방법

  • 동적 연결리스트를 이용
  • 구현이 복잡
  • 메모리 효율성이 좋다.

✅ 스택 응용 1 : 괄호 검사

• 괄호 종류 : 소괄호, 중괄호, 대괄호

• 조건

  • 왼쪽 괄호 개수와 오른쪽 괄호 개수가 같아야함
  • 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함
  • 괄호 사이에는 포함 관계만 존재

• 개요

  • 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후 오른쪽 괄호와 짝이 맞는지 검사
  • 이 때 스택이 비어있으면 조건에 위배, 괄호의 짝이 안맞아도 위배
  • 마지막 괄호까지 조사한 후에도 스택에 괄호가 남아잇으면 조건 위배

✅ 스택 응용 2 : Function Call

• 프로그램에서 함수 호출과 복귀에 따른 수행 순서 관리
  • 가장 마지막에 호출된 함수가 가장 먼저 실행 완료하고 복귀하는 후입선출 구조
  • 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입
  • 함수 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어 있던 복귀주소를 확인하고 복귀
  • 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택에 됨.

✅ 함수 호출과 복귀에 따른 전체 프로그램의 수행 순서

✅ 스택 응용 3 : 실행 취소

• 현재 작업에 대해 실행 취소 / 실행 취소의 취소 같은 작업