C언어 스택(STACK) 예제

스택(STACK) - 자료구조 

스택(stack)은 모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조(linear data structure)로서, 삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 한쪽 끝을 bottom이라 한다. 스택은 종종 pushdown stack이라고도 하는데, 스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, 가장 최근에 삽입된 원소를 의미하는 스택의 top으로부터 한 원소를 제거하는 것을 pop이라 한다. 이와 같은 스택 연상은 항상 스택의 top에서 발생하므로 top 포인터의 값을 1씩 증가 또는 감소시킴으로써 수행된다.

큐가 FIFO(first int first out)이고 스택은 FILO(first in last out)이다.

다음은 C언어로 크기가 5인 스택을 구현한 코드이다.

대충 설명을 하면 크기가 5인 스택을 만들고 (메모리 할당을 하고) 초기화를 하고 데이터를 삽입(PUSH)하고 데이터를 추출(POP)하는 것이다.

삽입 순서가 1 -> 2 -> 3 -> 4 -> 5 인 경우 출력 순서는 5 -> 4 -> 3 -> 2 -> 1 이다.

스택의 사용처는 가장 쉽게 볼 수 있는 곳이 여행 캐리어에 짐을 담았다가 푸는 행위이다. 여행 캐리어에 짐을 순서대로 담으면 나중에 꺼낼 때는 가장 마지막에 담은 것부터 꺼내게 되기 때문이다. 이 외에도 OS 내부적으로도 스택을 쓰는 곳이 있다. 예를 들어 함수를 재귀적으로 호출 한 경우 가장 나중에 호출한 것부터 닫힌다.

#include <stdio.h>

#include <stdlib.h>

#define STACK_SIZE 5

void Push(int nData);

int Pop();

int *pStack = NULL;

int main(){

// 메모리 할당

pStack = (int*)malloc((sizeof(int)) * STACK_SIZE);

// 초기화

for (int i = 0; i < STACK_SIZE; i++){

pStack[i] = NULL;

}

Push(1);

Push(2);

Push(3);

Push(4);

Push(5);

for (int i = 0; i < STACK_SIZE; i++){

printf("%d\n", Pop());

}

return 0;

}

void Push(int nData){

int nCount = 0;

for (int i = 0; i < STACK_SIZE; i++){

if (pStack[i] == NULL)

{

break;

}

nCount++;

}

if (nCount != STACK_SIZE){

pStack[nCount] = nData;

}

 

}

int Pop(){

int nCount = STACK_SIZE-1;

int nResult = 0;

for (int i = STACK_SIZE-1; i >0; i--){

if (pStack[i] != NULL)

{

break;

}

nCount--;

}

if (nCount != -1){

nResult = pStack[nCount];

pStack[nCount] = NULL;

}

return nResult;

}