자료구조 공부#9 (스택)

 

2021.03.26 - [전체글] - 자료구조 공부#8 (포인터)

이전 내용

---

스택(Stack)

뭐 게임 롤에서 스택이 쌓인다? 라는 느낌이냐 묻냐면 거의같다.

쌓아놓는 다는 개념이라 생각하면 된다.

 

스택의 특징 : 후입선출의 형식이다 가장 마지막에 넣은게 가장 위에 쌓이듯이 꺼낼떄는 가장 마지막에 넣은(제일 위에있는 데이터)를 뽑아간다.

 

스택의 구조 이미지

 

 

함수를 통해 이해해보는 스택의 구조

 

 

 

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

• 객체 : 0개 이상의 원소를 가지는 유한 선형 리스트
• 연산 :
  • create(size) : 최대 크기 size 크기의 공백 스택을 생성
  • is_full(s) : if(스택의 원소수 == size) return TRUE; else return FALSE;
  • is_empty(s) :if(스택의 원소수 == 0) return TRUE; else return FALSE:
  • push(s, item) : 스택 맨위에 item 을 추가함 (꽉차있으면 에러를 리턴)
  • pop(s) : 스택 맨위에 원소를 제거해서 반환함
  • peek(s), top(s) : 스택 맨위에 원소를 제거하지 않구 반환함

 

그림으로 다시 한번 봐보자 스택의 개념

 

배열을 이용한 스택의 구현

• 1차원 배열 stack[]
• 스택에서 가장 최근에 입력되었던 자료를 가리키는 top 변수
• 가장 먼저 들어온 요소는 stack[0]에, 가장 마지막에 들어온 요소는 stack[top]에 저장
• 스택이 공백상태이면 top 은 -1

배열에서 is_empty i_full 구현

 

 

push 연산 구현

pop 연산

전역 변수로 스택 구현하는 방법

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

#define MAX_STACK_SIZE 100
typedef int 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;
}


void pop(){
	if (is_empty()){
    	fprintf(stderr, "스택 공백 \n");
        return;
    }
    else 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

 

마지막에 넣은 3값이 pop 통해 나와서 출력이 되는걸 확인할 수 있다.

 

 

구조체 배열로 구현하기

#define MAX_STACK_SIZE 100

typedef int element;
typedef struct{
	element data[MAX_STACK_SIZE];
    int top;
} Stack Type;


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)){
    	fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}

int main(void){
	StackType s;  
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));	
}

 

 

동적으로 구현하기위해 malloc 과 포인터로 선언하는 방법

typedef int element;

typedef struct{
	element *data;
    int capacity;
    int top;
} StackType;


int main(void){
	StackType* s;
    
    s= (StackType*)malloc(sizeof(StackType));
    init_stack(s);
    push(s, 1);
    push(s, 2);
    push(s, 3);
    printf("%d\n", pop(s));
    printf("%d\n", pop(s));
    printf("%d\n", pop(s));
    free(s);
	
}

 

스택의 응용(괄호 검사)

괄호의 종류 : [].{}.() 대,중,소 괄호

 

조건 

 

1. 왼쪽 괄호와 오른쪽 괄호 갯수가 같아야 한다

2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호 보다 먼저 나와야한다.

3. 괄호 사이에는 포함관계만 존재한다.

 

잘못된 괄호 사용 예시

{{} ()), []], [[]

 

스택으로 괄호 오류 검출하는 과정

괄호 여는걸 푸쉬, 닫는걸 팝 이라 생각하자.

 

 

 

 

---

느낀점 : 스택에 관련되서 중점을 두고 설명해주셨다. 스택을 제대로 이해해야 추후에 다른 작업을 할때 도움이 될것이다.

자료구조 재밌다