[C언어] Array Stack 배열 스택 구현

스택이란 ?

• 리스트와 같이 선형 (Sequential) 구조
  • 자료를 순차적으로 저장한다.
• 리스트와 다르게 LIFO(후입 선출)
  • 자료의 추가와 제거가 TOP에서 이루어 진다.

스택에 필요한 주요 Operations

• Pop - 스택의 Top에 있는 자료를 제거한 후 반환한다.
• Push - 스택의 Top에 자료를 추가한다.
• Peek - 스택의 Top에 있는 자료를 반환한다. (제거 x)
• isEmpty - 스택이 비어있는지 확인한다.

배열 스택의 장점

• 속도가 빠르다
  • 더 빨리 노드에 접근할 수 있다.

배열 스택의 단점

• 미리 저장할 데이터의 개수를 예측하고 여유롭게 스택의 크기를 지정해야한다.
  • 나중에 데이터를 추가하기 위해서이다. 만약 데이터의 개수만큼 배열의 크기가 정해지면 나중에 새로운 데이터를 추가할 수 없게된다.
  • 따라서 메모리를 낭비하게될 수 있다.

배열 스택은 어떻게 동작할까?

• 배열 스택의 데이터는 노드에 저장된다.
  • 노드에 자료를 저장하여 여러 개의 자료를 저장할 수 있다.

노드의 구조

• 가장 먼저 삽입된 데이터가 가장 오래된 데이터가 된다.
• 새로운 데이터를 삽입할때 그 데이터는 Top 이 된다.
• 데이터를 제거할때 Top 에 있는 데이터가 제거되며 새로운 Top이 정해진다.

 

스택이 작동하는 방식

 

새로운 데이터를 삽입 할때

• 새로운 데이터를 삽입하면 그 데이터가 Top이 되기 때문에 Top의 위치 인덱스가 1만큼 증가한다.
• 배열이 가득차 있는지 아닌지 확인해야 한다.

 

 

기존 데이터를 제거할때

• 데이터를 제거할때 Top 에 있는 데이터가 제거되며 기존 데이터의 아래에 있던 노드가 Top이 된다.
  • 따라서 Top의 위치 인덱스는 1만큼 감소해야 한다.
• 제거할 수 있는 자료가 있는지 확인해야 한다.

 

Implementation 구현

Github