스택(Stack)

스택(Stack)

스택(Stack)이란?

• 스택(Stack)은 영어사전에서 (건초, 밀집따위를 쌓아놓은) 더미를 의미한다고 한다. 스택의 예로는 창고에 쌓인 박스나, 식당에 쌓인 접시 더미등이 있다.
• 박스를 쌓을때 위에서부터 하나하나 쌓듯이, 반대로 박스를 꺼낼때는 위에서부터 하나하나 꺼낸다. 이런 입출력 형태를 LIFO(Last-In First-Out)이라고 한다.

스택 추상자료형(Stack Abstract Data Type)

• IsFull(): 스택이 다 찼을때, true를 반환한다.
• IsEmpty(): 스택이 비어있을때, true를 반환한다.
• push(): 스택의 맨 위에 item을 추가한다.
• pop(): 스택의 맨 위의 원소를 제거해서 반환한다.
• peek(): 스택의 맨 위의 원소를 제거하지 않고 반환한다.

스택(Stack)의 알고리즘

• SP(Stack Pointer)의 초기값에 따라서 의미가 조금 달라진다.
  • If sp = 0

    push(item){
        if(Full) return; // Full >= N
        S[sp++] = item; // sp는 넣을 자리를 의미한다.
    }
        
    pop(){
        if(Empty) return; // Empty: sp <= 0
        return S[--sp]
    }
    

  • If sp = -1

    push(item){
        if(Full) return; // Full >= N-1
        S[++sp] = item; // sp는 넣은 자리를 의미한다.
    }
        
    pop(){
        if(Empty) return; // Empty: sp <= -1
        return S[sp--]
    }
    

• 연결리스트를 이용해서 스택을 구현하면 배열과는 달리 크기의 제한이 사라진다는 장점이 있다.

  Node *S, *p;
  
  push(p){
    p -> Next = S;
    S -> p
  }
  
  Node* pop(){
    if(S == NULL) return NULL;
    p = S;
    S = S -> Next;
    return p;
  }
  

스택(Stack) 구현

#include <stdio.h>
#define MAX_STACK_SIZE 100

typedef struct {
	int 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, int item){
	if(is_full(s)) printf("Stack is FUll\n");
	else s->data[++(s->top)] = item;
}
int pop(StackType *s){
	if(is_empty(s)) printf("Stack is Empty\n");
	else return s->data[(s->top)--];
}
int peek(StackType *s){
	if(is_empty(s)) printf("Stack is Empty\n");
	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));
}

스택(Stack)의 사용사례

• 함수 호출
• 미로 찾기, 그래프
• 식(expression)의 처리(후위 표기법 계산)
• 웹 브라우저 방문기록(뒤로가기)