[자료구조] push( ) 와 pop( ) 함수를 이용한 스택

스택의 개념과 구조

: 스택은 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제 됨 / 후입선출 구조 ( LIFO, Last-In-First-Out )

스택에서의 삽입 연산 : push

스택에서의 삭제 연산 : pop

 

기본 설정 

#include <stdio.h>
#define STACK_SIZE 100
 
int S[STACK_SIZE];
int top=-1;

 

100 크기의 S라는 정수형 배열을 만든다.

변수 top은 삽입과 삭제가 일어나는 위치로 현재 스택의 가장 위에 있는 데이터 위치이다.

새로운 데이터가 들어오면 배열의 첫번째인 S[0]에 들어오기 때문에 top의 위치는 0으로 바뀌어야 한다. 그렇기에 top의 초기값은 -1이다.

 

스택의 push( ) 알고리즘

 

: 스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 데이터를 삽입하려면 top의 위치를 하나 증가시킨다. 이 때 top 위치가 스택의 크기 ( =STACK_SIZE )보다 크면 오버플로우 상태이므로 연산이 종료된다. 오버플로우가 아니라면 스택의 top 위치에 데이터 삽입한다.

 

#include <stdio.h>
#define STACK_SIZE 100
 
int S[STACK_SIZE];
int top=-1;
 
int push(int num){
  if(top == STACK_SIZE-1 ) { 
    printf("error!");
    return 0;
    }
 
  S[++top] = num;
  return 1;
 
}

 

먼저 if문으로 오버플로우를 확인한다. 변수 top이 스택 사이즈-1과 동일하다면 스택이 꽉 찬 것이니 에러 메세지를 출력하고 종료한다.

그렇지 않다면 S[++top]으로 top에는 제일 위에 있는 원소의 위치가 들어가고 그 위치에 새 데이터가 삽입되게 된다.

 

스택의 pop( ) 알고리즘

: 공백 스택이 아니면 top에 있는 원소를 삭제하고 반환한다. 스택의 마지막 원소가 삭제되면 그 아래 원소, 즉 남아있는 원소 중 가장 위에 있는 원소가 top이 되어야 하므로 top 위치를 하나 감소시킨다.

 

#include <stdio.h>
#define STACK_SIZE 100
 
int S[STACK_SIZE];
int top=-1;
 
int pop() {
  if(top==-1) { 
    printf("error"); 
    return 0;
    }
 
  return S[top--];
}

 

먼저 if문으로 top = -1이면 스택이 공백이라는 뜻이므로 에러 메세지를 출력하고 종료한다.

그렇지 않다면 S[top--]로 top위치의 원소를 반환하고 top의 위치를 그 아래 위치로 바꾼다. (후위 감소 연산자의 원리 이용)

 

 

참조 : C로 배우는 쉬운 자료구조 / 이지영 / 한빛아카데미