[자료구조][C언어]스택이란?_스택의구현(2)

저번 시간에는 스택이 무엇인지에 대해 간략하게 살펴 보았다.

스택은 맨 윗부분에서만 데이터의 삭제와 삽입이 가능한 자료구조이다. 

 

스택의 구조

 

스택의 구현

 

스택의 구현을 하기 위해서는 먼저 스택을 저장할 배열과 top의 위치를 저장할 변수가 필요하다.

그리고 아래의 연산들을 수행하는 함수가 필요하다.

 

Push(삽입) : 스택의 상단에 데이터를 추가

Pop(제거) : 스택의 상단의 데이터를 삭제

isFull : 스택이 꽉 차있는지 검사

isEmpty : 스택이 비어있는지 검사

peek : 요소를 삭제하지 않으면서 스택의 최상단 원소가 무엇인지 확인

(*pop 함수는 요소를 삭제하면서 가져온다)

 

우리는 먼저 C언어로 구현해볼 예정인데 전역변수로 구현하는 방법과

구조체를 사용한 방법 두가지로 구현해볼 예정이다.

먼저 스택을 저장할 배열과 top의 위치를 저장할 변수를 전역변수로 선언 및 초기화해 주었다.

 

#include <stdio.h>
#include <stdlib.h>
//스택의 최대크기지정
#define MAX_SIZE 100 

//전역변수로 1차원 배열선언
int stack[MAX_SIZE]; 
//전역변수, 배열에 접근하는데 사용 예정
int top = -1;

 

 

push,pop,peek 등의 연산을 하기전에 스택이 가득차있는지 혹은 비어있는지 확인이

필수적이기 때문에 isFull과 isEmpty함수 만들어 주었다.

 

//스택이 가득 차 있는지 검사
int isFull(){
    return top == MAX_SIZE -1; 
  //MAX_SIZE-1 인 이유는 크기가 
  //N인 1차원배열을 선언하였을 때
  //배열의 index는 0부터 N-1이기 때문이다.
}
//스택이 비어있는지 검사
int isEmpty(){ 
    return top == -1;
}

 

push 함수는 어떻게 구현해야 할까???

먼저 최상단의 위치를 저장하는 Top에 1을 더해주고

이 Top을 배열의 위치(index)로 접근해 값을 배열의 Top번째 위치에 넣어주면된다.

자세한 과정은 아래와 같다.

 

push() 함수의 과정

 

위 과정을 코드로 나타낸 push함수이다.

 

//스택의 상단에 데이터를 추가
void push(int element){
    if(isFull()){
        printf("Stack is Full.");
        return;
    }
    else{
    	//최상단의 위치 변경
        top = top+1; 
        
        //최상단에 데이터 추가
        stack[top] = element; 
    }
}

 

그렇다면 pop함수는 어떻게 구현해야 할까???

Top을 이용해 배열의 Top번째 값을 가져와 출력하고

Top의 값을 -1 해주면 된다.

(*이때 pop하기 전의 최상단의 값은 배열에서 pop 연산 후

바로 사라지지 않지만 추후 값을 추가할 때 덮어 씌워짐으로써 사라진다) 

 

pop() 함수의 과정

위 pop() 과정을 코드로 나타내면 이렇게 된다.

 

//스택의 상단에 데이터를 삭제 및 가져오기
int pop(){
    if(isEmpty()){
        printf("Stack is Empty.");
        exit(1);
    }
    else{
        //e 에 최상단의 원소 대입
        int e = stack[top];
        
        //최상단의 위치 변경
        top = top - 1; 
        
        //삭제된 최상단의 값 출력
        return e; 
    }
}

 

pop과 다르게 값을 삭제하지않고 최상단의 값을 가져오는 peek 함수는 어떻게 구현해야할까??

간단하다. 배열에서 top번째에 해당하는 값을 가져오기만 하면 된다.

 

peek() 함수의 과정

위 peek() 과정을 코드로 나타내면 이렇게 된다.

 

int peek(){
    if(isEmpty()){
        printf("Stack is Empty");
        exit(1);
    }
    else{
     //스택의 최상단의 값 출력
        return stack[top];
    }
}

 

위 코드들을 한번에 정리하면 이렇게 된다.

 

#include <stdio.h>
#include <stdlib.h>
//스택의 최대크기지정
#define MAX_SIZE 100 

//전역변수로 1차원 배열선언
int stack[MAX_SIZE]; 
//전역변수, 배열에 접근하는데 사용 예정
int top = -1;

//스택이 가득 차 있는지 검사
int isFull(){
    return top == MAX_SIZE -1; 
  //MAX_SIZE-1 인 이유는 크기가 
  //N인 1차원배열을 선언하였을 때
  //배열의 index는 0부터 N-1이기 때문이다.
}
//스택이 비어있는지 검사
int isEmpty(){ 
    return top == -1;
}

//스택의 상단에 데이터를 추가
void push(int element){
    if(isFull()){
        printf("Stack is Full.");
        return;
    }
    else{
    	//최상단의 위치 변경
        top = top+1; 
        
        //최상단에 데이터 추가
        stack[top] = element; 
    }
}

//스택의 상단에 데이터를 삭제 및 가져오기
int pop(){
    if(isEmpty()){
        printf("Stack is Empty.");
        exit(1);
    }
    else{
        //e 에 최상단의 원소 대입
        int e = stack[top];
        
        //최상단의 위치 변경
        top = top - 1; 
        
        //삭제된 최상단의 값 출력
        return e; 
    }
}

int peek(){
    if(isEmpty()){
        printf("Stack is Empty");
        exit(1);
    }
    else{
     //스택의 최상단의 값 출력
        return stack[top];
    }
}

int main(void){

}

 

만약에 스택을 여러개 사용해야할 경우 일일이 전역변수로 선언해주고 초기화해서 사용하기엔 코드가 너무 복잡해지는 문제가 생긴다.

C언어의 구조체와 포인터를 사용하면 위 문제를 간단하게 해결할 수 있다.

구조체와 포인터를 활용해 구현할 경우 코드는 다음과 같다.

 

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define SIZE 100
typedef struct StackType{
    int top;
    int elem[SIZE];
}StackType;

void init(StackType *S){
    S->top = -1;
}

int isFull(StackType *S){
    return S->top == SIZE - 1;
}

int isEmpty(StackType *S){
    return S->top == -1;
}
void push(StackType *S,int e){
    S->elem[++S->top] = e;
}

int peek(StackType *S){
    if(isEmpty(S)){
        return -1;
    }
    int top = S->elem[S->top];
    return top;
}

int size(StackType *S){
    int size = S->top+1;
    return size;
}

int pop(StackType *S){
    if(isEmpty(S))
        return -1;
    else{
        int e = S->elem[S->top--];
        return e;
    }
}

int main()
{
    return 0;
}

 

다음시간에는 위 코드들을 활용하면 어떤 것들을 할 수 있는지 알아볼 예정이다. 

 

참조

천인국 외 2인 , C언어로 쉽게 풀어쓴 자료구조, 생능출판, 2019