[알고리즘] C언어 배열을 활용한 Stack 구현

스택(Stack)

스택(stack)은 모든 원소들의 삽입(insert)과 삭제(delete)가 

리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 

선형 자료 구조(linear data structure)로서, 

삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 끝을 bottom이라 한다. 

스택은 종종 pushdown stack이라고도 하는데, 

스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, 

가장 최근에 삽입된 원소를 의미하는 스택의 top으로부터 

한 원소를 제거하는 것을 pop이라 한다. 

이와 같은 스택 연상은 항상 스택의 top에서 발생하므로 

top 포인터의 값을 1씩 증가 또는 감소시킴으로써 수행된다

시작 소스

※ 헤더파일을 이용하지 않고 하나의 소스파일 내에서 구현하였음

 

#include<stdio.h>
 
 
// 상수 값 define
#define LEN 10        // 스택의 길이
#define TRUE 1        
#define FALSE 0
 
typedef int Data;    // 데이터형(가변성)                                                                        
 
// 스택 구조체
typedef struct array_stack {
    Data Arr[LEN];
    int top;
} array_stack;
 
// 스택 명명 변환
typedef array_stack Stack;

 

- define으로 스택의 길이와 TURE/FALSE 반환값을 설정해 줌

- 구조체의 가변성을 위하여 typedef로 설정

- 구조체를 이용하여 스택의 기본 바탕을 만든다. 

- 구조체 내부 속성은 배열,top index로 이루어 진다.

- 스택의 이름을 typedef로 변환한다.

스택의 함수

 

// 스택 초기 설정
void stack_init(Stack *pstack) {                                                                            
    pstack->top = -1;
}
 

1. 초기 설정(stack_init)

초기에 스택 내부를 비워주는 초기 설정 함수이다.

이 함수는 스택 선언과 동시에 사용하여 초기화 시켜준다.

 

// 빈 스택 확인
int IsEmpty(Stack *pstack) {                                                                                 
    if (pstack->top == -1)
        return TRUE;
    else
        return FALSE;
}

 

2. 빈 스택 확인(IsEmpty)

IsEmpty 함수를 사용하여 스택 내부가 비어있는지 확인한다.

비었을경우 TRUE, 데이터가 있을경우 FALSE를 반환한다.

 

// 데이터 삽입
void Push(Stack *pstack, Data Data) {                                                                       
    pstack->top += 1;
    pstack->Arr[pstack->top] = Data;
}
 

3. 데이터 삽입(push)

데이터를 삽입하면서 top index가 1 증가한다.

증가한 index의 배열값은 파라미터로 들어온 데이터가 들어간다.

 

// 데이터 삭제
void Pop(Stack *pstack) {
 
    if (IsEmpty == TRUE) {
        printf("memory error!");                                                                           
        exit(-1);
    }
 
    pstack->top -= 1;
}

 

4. 데이터 삭제(pop)

데이터를 제거하기에 앞서 스택이 비어있는지 확인한다.

비어있을 경우 스택값을 제거할 수 없으므로 

에러 메세지를 출력하며 함수가 실행되지 않는다.

비어있지 않은 경우 top값이 감소하며 스택의 크기가 줄어든다.

 

// top index의 데이터 확인
Data peek(Stack *pstack) {
    if (IsEmpty == TRUE) {
        printf("memory error!");
        exit(-1);
    }
 
    return pstack->Arr[pstack->top];                                                                       
}
 

 

5. top index의 데이터 확인(peek)

top index의 배열 데이터를 확인한다. 

이 또한 현재 스택 내부가 비어있는지 확인하는것을 선행한다.

그렇지 않은 경우에는 top index의 배열값을 반환한다.

 

// stack 저장값 출력
void print(Stack *pstack) {
    int i;
    if (IsEmpty == TRUE) {
        printf("memory error!");
        exit(-1);
    }
 
    for (i = 0; i < (pstack->top)+1; i++){                                                                 
        printf("%d\n",pstack->Arr[i]);
    }
}
 

6. stack 내부값 출력

stack에 저장되어있는 값들을 모두 출력한다. 출력에 앞서 스택 내부 확인을 선행한다.

for문을 이용하여 0에서 부터 top index까지 반복하여 출력하는 구조이다.

샘플 예제(main 함수)

 

int main() {
    Stack stack;
    stack_init(&stack);                                                                                     
 
    Push(&stack, 1);
    Push(&stack, 4);
    Push(&stack, 5);
    Push(&stack, 3);
    Push(&stack, 1);
 
    print(&stack);
}

 

샘플로 만든 예제 함수는 다음과 같다.

stack 구조체를 생성 후 초기화, 5번의 push후에 스택 내부의 값을 출력해 보았다.

 

 

결과는 다음과 같다.

전체소스

 

#include<stdio.h>
 
 
// 상수 값 define
#define LEN 10        // 스택의 길이
#define TRUE 1        
#define FALSE 0
 
typedef int Data;    // 데이터형(가변성)                              
 
// 스택 구조체
typedef struct array_stack {
    Data Arr[LEN];
    int top;
} array_stack;
 
// 스택 명명 변환
typedef array_stack Stack;
 
// 스택 초기 설정
void stack_init(Stack *pstack) {
    pstack->top = -1;
}
// 빈 스택 확인
int IsEmpty(Stack *pstack) {
    if (pstack->top == -1)
        return TRUE;
    else
        return FALSE;
}
 
// 데이터 삽입
void Push(Stack *pstack, Data Data) {
    pstack->top += 1;
    pstack->Arr[pstack->top] = Data;
}
 
// 데이터 삭제
void Pop(Stack *pstack) {
 
    if (IsEmpty == TRUE) {
        printf("memory error!");
        exit(-1);
    }
 
    pstack->top -= 1;
}
 
// top index의 데이터 확인
Data peek(Stack *pstack) {
    if (IsEmpty == TRUE) {
        printf("memory error!");
        exit(-1);
    }
 
    return pstack->Arr[pstack->top];
}
 
// stack 저장값 출력
void print(Stack *pstack) {
    int i;
    if (IsEmpty == TRUE) {
        printf("memory error!");
        exit(-1);
    }
 
    for (i = 0; i < (pstack->top)+1; i++){                                                                
        printf("%d\n",pstack->Arr[i]);
    }
}
 
 
int main() {
    Stack stack;
    stack_init(&stack);
 
    Push(&stack, 1);
    Push(&stack, 4);
    Push(&stack, 5);
    Push(&stack, 3);
    Push(&stack, 1);
 
    print(&stack);
}