스택

0woy·2023년 3월 27일

stack 스택 자료구조

자료구조

목록 보기

3/4

📕 스택이란?

쌓아놓은 더미
가장 최근에 들어온 데이터가 가장 먼저 나가는 구조(Last-In-First-Out)
스택의 입출력은 맨 위에서만 발생한다. 즉, 중간에서 삭제 불가!

📖 스택의 연산

- Push: 스택에 data 추가
- Pop: 스택에 data 삭제
- is_empty, is_full: 스택의 공백/포화 상태 검사
- peek: 요소를 삭제하지 않고 보기만 함

📙 스택의 구현

- 1차원 배열 stack[]
- top: 가장 최근 입력된 자료를 가리키는 top
- 가장 먼저 들어온 요소 = stack[0] || 가장 나중에 들어온 요소 = stack[top]
- 스택이 공백 상태인 경우: top = -1

📒 전역 변수로 구현

1차원 배열, top 변수를 모두 전역 변수로 구현한다.
따라서 함수의 매개변수로 전달할 필요가 없다.

프로그램 상에서 여러 Stack을 사용하지 않는 경우에 사용하는 방식
하지만 전역 변수로 구현하지 않는 것을 권장!

// 예시
#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); }

// 포화 상태 검출 함수
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()){
    	fpritnf(stderr,"스택 공백 에러\n");
        exit(1);
    }
    else return stack[top--];
}

📗 구조체로 구현

#include<stdio.h>
#include<stdlib.h>

#define MAX_STACK_SIZE 100	//스택의 최대 크기
typedef struct{
	element data[MAX_STACK_SIZE];
    int top;
}StackType;

// 스택 초기화 함수
void init_stack(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)){
    	fprintf(stderr,"스택 포화 에러\n");
        return;
    }
    else s->data[++(s->top)] = item;
}

// 삭제 함수
element pop(StackType *s){
	if(is_empty(s)){
    	fpritnf(stderr,"스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}

📘 동적 배열로 구현

malloc을 사용하여 실행시간에 메모리 할당을 받는다.

앞선 구조들은 컴파일 시간에 정적 메모리를 할당 받음!

typedef int element;
typedef struct{
	element *data;	// data는 포인터로 정의
    int capacity;	// 스택의 현재 크기
    int top;
}StackType;

// 스택 생성
void init_stack(StackType *s){
	s->top = -1;
	s->capacity = 1;	// 1개 요소 저장공간 확보
    s->data = (element*)malloc(s->capacity * sizeof(element));
}

// 스택 삭제
void delete(StackType *s){ free(s); }

// 스택 삽입
void push(StackType *s, element item){
	if(is_full(s)){		// 공간이 부족한 경우
    	s->capacity*=2;	// 메모리 2배 확보	
        s->data = (element*)realloc(s->data, s->capacity*sizeof(element));
    }
    s->data[++(s->top)] = item;
}