[알고리즘] 스택(Stack)의 삽입/제거/검색(C언어)

스택(Stack)의 삽입/제거/검색(C언어)

C언어로 자료구조 스택의 삽입, 제거, 검색의 예를 코드로 보겠습니다. 

스택(Stack)의 개념을 파악하고 싶다면 아래 글을 먼저 읽어주세요. 

 

스택이란? 글 보러가기 

 

 

■ 스택의 삽입

 

최대 8개의 요소가 들어갈 수 있는 스택입니다. 

값을 삽입할 때 배열에서 사용하는 insert를 스택에서 push로 사용합니다.

C 언어로 구현한 코드를 보겠습니다.

 

enum { MAX_NUMS = 8};

int s_nums[MAX_NUMS]; // 8개 요소를 넣을 수 있는 배열 생성
size_t s_num_count = 0; // 데이터를 넣을 자리(인덱스)

void push (int n){
    assert(s_num_count < MAX_NUMS);
    s_nums[s_num_count++] = n; // 배열에 n을 대입하고, s_num_count은 1증가함
}

 

push(10)를 하면 스택 0자리에 10이 들어갑니다. 다음 데이터를 넣을 자리를 가리키는 s_num_count가 1 증가합니다. 

그 다음 push(20)을 하면 s_nums[1] 자리에 20이 들어갑니다. 

 

시간 복잡도 O(1) 입니다.

 

그림에서는 좌우로 수가 쌓이도록 그렸는데 스택을 배열처럼 생각하면 이해하기 좋을 것 같아 이렇게 만들었습니다. 

 

 

 

---

■ 스택의 제거

 

is_empty를 통해 스택이 비어있는지 아닌지 확인합니다. 

값을 제거할 때 배열에서 사용하는 remove를 스택에서 pop로 사용합니다.

영어에서 콜라 뚜껑을 딸 때 pop이라고 합니다.

'pop'하면 위에 있는 것을 뺀다하고 연상하면 기억하기 좋겠네요. 

시간 복잡도는 O(1) 입니다.

 

enum { TRUE = 1, FALSE = 0};
enum { MAX_NUMS = 8};

int s_nums[MAX_NUMS]; // 8개 요소를 넣을 수 있는 배열 생성
size_t s_num_count = 0; // 데이터를 넣을 자리(인덱스)

int is_empty(void){
    return (s_num_count == 0);
}
int pop (void){
    assert(is_empty() == FALSE);
    return s_nums[--s_num_count];
}

 

 

 

---

■ 스택의 검색

 

스택은 출구가 하나만 있는 형태입니다.

또한 스택이 지원하는 연산은 push와 pop 밖에 없기 때문에 스택의 중간에 접근할 수 없습니다.

 

그럼 어떻게 검색을 할 수 있을까요?

기본 원리는 요소를 다 제거했다가 다시 원상 복구해야 합니다. 

즉, 하나씩 다 빼가면서 찾습니다.

마치 각티슈 안에서 특정 휴지를 찾으려면 위에서부터 하나씩 뽑아야 하는 경우처럼 말이죠.

 

 

그럼 다음 스택에서 30을 찾는 다고 가정할 때 어떤 식으로 검색이 이뤄지는지 보겠습니다. 

데이터가 들어있는 스택에서 위에부터 하나씩 꺼냅니다. 50, 40, 30 순이 되겠지요.

그렇게 pop한 데이터는 다른 메모리에(다른 스택에 하기도 합니다) 50, 40, 30 순으로 넣어둡니다.

그러다 원하는 값 30을 찾으면 원하는 기능을 처리하고 다시 기존 스택을 원상복구합니다.

30, 40, 50 순으로 들어갑니다. 

 

시간 복잡도 O(n) 입니다. 

사실 제거에  O(n) + 복구  O(n)이 필요해서  O(2n) 이지만 그냥  O(n)이라고 말함

빅오표기법은 '정도'를 나타내기 때문입니다. 

 

빅오표기법란?  글 보러가기  

 

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------