Basic Data Structure

• 포인터를 사용하는 단순한 자료구조를 통해 동적인 집합을 표현하는 방법에 대한 고찰
• Stack & Queue, Linked List, Tree
• 단순한 배열을 이용하여 구현해본다.

Stack & Queue

Stack

• 가장 최근에 삽입된 원소가 먼저 삭제되는 구조
• 후입선출(LIFO, last in first out)

Insert 연산 : Push
Delete 연산 : Pop

Stack의 메소드 구현 법

• Stack-Empty(S)

  if S.top == 0
      return TRUE
  else return FALSE

• Push(S, x)

  S.top = S.top + 1
  S[S.top] = x

• Pop(S)

  if Stack-Empty(S)
      error "스택 부족"
  else S.top = S.top - 1
      return S[S.top + 1]

이 세 가지 스택 연산은 수행시간이 각각 O(1)이다.

Queue

• 가장 오랜 시간 존재한 원소가 먼저 삭제되는 구조
• 선입선출(FIFO, first in first out)