자료구조 배열을 이용한 스택 구현

자료구조 스택(stack)에 대한 포스팅입니다

스택은 쌓아놓은 더미라고도 하지요

특징으로는 후입선출(LIFO, Last-In First-Out)의 특징을 가지고 있습니다

(가장 최근에 들어온 정보가 가장 먼저 나감)

각각의 요소를 element(엘리먼트)라고 하며 

스택의 상단이 top, 스택의 하단을 bottom이라고 부릅니다

스택의 추상 데이터 타입(ADT)

• create()        스택을 생성
• is_empty(s)   스택이 비어있는지 검사
• is_full(s)       스택이 가득 찼는지 검사
• push(s, e)    스택의 맨 위에 요소 k를 추가
• pop(s)         스택의 맨 위에 있는 요소를 삭제
• peek(s)        스택의 맨 위에 있는 요소를 삭제하지 않고 반환

배열을 이용한 스택 구현 예제

#include<stdio.h> #include<stdlib.h> #define MAX_STACK_SIZE 100 typedef int element;  typedef struct {  element stack[MAX_STACK_SIZE];  int top;  } StackType;  // 스택 초기화 함수 void init(StackType *s) {  s->top = -1;  }  // 공백 상태 검출 함수 int is_empty(StackType *s) {  return (s->top == -1);  }  // 포화 상태 검출 함수 int is_full(StackType *s){  return (s->top == (MAX_STACK_SIZE-1));  } // 삽입 함수 void push(StackType *s, element item){ if( is_full(s) ) {  printf("Err!!! stack full\n");  return; }  else s->stack[++(s->top)] = item;  }  // 삭제 함수 element pop(StackType *s) { if( is_empty(s) ) { printf("Err!!! stack empty\n");  exit(1); }  else return s->stack[(s->top)--];  } // 피크 함수 element peek(StackType *s){ if( is_empty(s) ) {  printf("Err!!! stack empty\n");  exit(1); }  else return s->stack[s->top];  }  void main(){ StackType s, *ps=&s; init(ps); printf("%d\n",is_empty(ps)); push(ps, 5); push(ps, 7); push(ps, 3); push(ps, 1); push(ps, 8); peek(&s); printf("poped value = %d\n", pop(ps)); printf("poped value = %d\n", pop(ps)); printf("poped value = %d\n", pop(ps)); printf("poped value = %d\n", pop(ps)); printf("poped value = %d\n", pop(ps)); printf("poped value = %d\n", pop(ps)); }

실행화면

스택의 특징대로 입력한 순서의 반대로 출력되는 모습을 볼 수 있습니다

읽어주셔서 감사합니다 ^^*