스택(Stack)

  • 선형 구조중 하나로 Last In First Out(LIFO)의 특징을 갖음.
  • 입력(push)과 출력(pop)이 한쪽(top)에서만 일어남

  • Top 포인터 : 가장 위에 있는 자료를 가르키는 포인터, 삽입&삭제시 이용 (Top 포인터는 스택이 비어있을 때 = -1, 다 차있을 때 = n-1)

  • 스택이 꽉차면 더이상 삽입할 수 없음 -> OverFlow

  • 스택이 비게되면 더이상 삭제할 수 없음 -> UnderFlow

  • 검색시 : O(n)
  • 삽입, 삭제시 : O(1)

큐(Queue)

  • 선형 구조중 하나로 First In First Out(FIFO)의 특징을 갖음.

  • 한쪽[rear]에서는 입력(Enqueue), 한쪽[front]에서는 출력(Dequeue)이 일어남

  • Front 포인터 : 가장 먼저 삽입된 자료를 가리키는 포인터, 삭제시 이용

  • Rear 포인터 : 가장 마지막에 삽입된 자료를 가리키는 포인터, 삽입시 이용

  • 검색시 : O(n)
  • 삽입, 삭제시 : O(1)

데크(Deque)

  • 스택 + 큐
  • 선형 구조중 하나로 First In First Out(FIFO)의 특징을 갖음.
  • 양쪽으로 입력과 출력이 일어남.

  • 다만, 한쪽에서만 입력 혹은 출력이 일어나게 제한할 수 있음. (한쪽만 입력 + 양쪽으로 출력 : scroll / 한쪽만 출력 + 양쪽으로 입력 : shelf)

  • 이중 연결리스트로 구현