자료구조 스택

스택이란?

스택은 사전적으로 '건초', '더미'를 의미한다. 자료구조에서 스택은 LIFO(Last-In First-Out)으로 마지막에 들어온 것이 먼저 나간다는 뜻으로 후입선출법이라고 한다. 예을 들어 접시 더미를 생각해보면 접시를 한개씩 쌓아올리고 맨 위부터 한 개씩 뺀다고 생각하면 먼저 쌓아올린 접시가 나중에 나갈것이고 나중에 쌓아올린 접시가 먼저 나갈 것이다. 이처럼 먼저 들어온게 나중에 나가는 것을 '선입후출'이라하고 나중에 들어온게 먼저 나가는 것을 '후입선출'이라 한다.

 

스택의 삽입과 삭제연산

 

스택의 연산

스택에는 두 가지의 기본 연산이 있다. 위 그림과 같이 삽입 연산(PUSH)과 삭제 연산(POP)이다. 그 외의 연산도 필요한다. 아래에서 연산들을 확인해보자.

 

is_sull(s) : 스택이 가득 차있는지 검사하여 true나 faluse를 반환

push(s, item) : 스택의 가장 윗부분에 데이터 삽입

is_empty(s) : 스택이 비어 있는 지를 검사하여 true나 faluse를 반환

pop(s) : 스택의 가장 윗부분의 데이터 삭제

peek(s) : 스택의 가장 윗부분의 데이터를 제거하지 않고 반환

 

 

스택구현

정수 배열 스택 프로그램

구조체 배열 스택 프로그램

#include <stdio.h>  #include <stdlib.h>  //스택이 전역 변수로 구현된다.  #define MAX_STACK_SIZE 100 // 스택의 최대 크기  typedef int element; // 데이터의 자료형  element  stack[MAX_STACK_SIZE]; // 1차원 배열  int  top = -1;  // 공백 상태 검출 함수  int is_empty()  {      return (top == -1);  // true/false 반환 }  // 포화 상태 검출 함수  int is_full()  {            // true/false 반환     return (top == (MAX_STACK_SIZE - 1));  }  // 삽입 함수  void push(element item)  {      if (is_full()) { //참이면 꽉찬 상태         fprintf(stderr, "스택 포화 에러\n");          return;      }      else         stack[++top] = item;  }  // 삭제 함수  element pop()  {      if (is_empty()) {   // 참이면 빈 상태         fprintf(stderr, "스택 공백 에러\n");          exit(1);      }      else         return stack[top--];  }  // 피크 함수  element peek()  {      if (is_empty()) {    // 참이면 빈 상태         fprintf(stderr, "스택 공백 에러\n");          exit(1);      }      else         return stack[top];  }  int main(void)  {      push(1);      push(2);      push(3);      printf("%d\n", pop());      printf("%d\n", pop());      printf("%d\n", pop());     return 0;  } 실행 결과 3 2 1

#include <stdio.h> #include <stdlib.h> #define MAX_STACK_SIZE 100 #define MAX_STRING 100   typedef struct {     int student_no;     char name[MAX_STRING];     char address[MAX_STRING]; } element; element stack[MAX_STACK_SIZE]; int top = -1;   int is_empty() {  // 공백 상태 검출 함수     return (top == -1); } int is_full() {  // 포화 상태 검출 함수     return (top == (MAX_STACK_SIZE - 1)); } void push(element item) {    // 삽입 함수     if (is_full()) {         fprintf(stderr, "스택 포화 에러\n");         return;     }     else         stack[++top] = item; } element pop() {  // 삭제 함수     if (is_empty()) {         fprintf(stderr, "스택 공백 에러\n");         exit(1);     }     else         return stack[top--]; } element peek() {  // 피크함수     if (is_empty()) {         fprintf(stderr, "스택 공백 에러\n");         exit(1);     }     else         return stack[top]; }   int main(void) {     element ie = { 20190001,                        "Hong",                        "Soeul" };     element oe;       push(ie);     oe = pop();       printf("학번: %d\n", oe.student_no);     printf("이름: %s\n", oe.name);     printf("주소: %s\n", oe.address);     return 0; } 실행 결과 학번: 20190001 이름: Hong 주소: Soeul