[자료구조] 2. Stack

1. 정의

Stack은 원소의 집합체로, 흔히 LIFO 구조의 시스템이라고 말한다. 간단히 말해 데이터를 위로 쌓는 형태처럼 저장하며, 항상 Stack의 가장 위에 데이터를 추가하거나 삭제할 수 있다. 입력(push)과 출력(pop)은 항상 스택의 Top에서 발생한다. 일반적으로 Stack에 추가적인 공간이 없는 경우, 더 이상의 데이터를 추가하지 못할 때의 상태에서 Push하는 경우 Overflow가 발생할 수 있다.

※ LIFO : Last-In-First-Out. 즉 나중에 들어온 데이터가 먼저 나가짐을 의미한다.

<The Concept of Stack>

2. 구현

1) By List

#include<stdio.h>
#include<stdlib.h>
 
/*Stack에 사용할 Node*/
typedef struct _node *nodeptr;
typedef struct _node{
    int data;
    nodeptr link;
}node;
 
/*Stack의 제일 위*/
nodeptr Top=NULL;
 
void Push(int);
void Pop();
 
int main(void){
    int n,i,temp;
    nodeptr search;
 
    printf("Input the number of data : ");
    scanf("%d",&n);
 
    i=0;
 
    while(i!=n){
        scanf("%d",&temp);
        
        Push(temp);
 
        i++;
    }
    i++;
    while(i){
        Pop();
        i--;
    }
 
    return 0;
}
 
/*Stack에 새로운 데이터를 Top에 추가*/
void Push(int data){
    nodeptr tempnode;
 
    tempnode=(nodeptr)malloc(sizeof(node));
    tempnode->data=data;
    tempnode->link=Top;
    Top=tempnode;
 
    return;
}
 
/*Stack의 Top이 비어있지 않다면, Top의 node를 삭제*/
void Pop(){
    nodeptr temp;
 
    if(Top){
        temp=Top->link;
        free(Top);
        Top=temp;
    }
    else{
        printf("Stack is Empty!\n");
    }
    return;
}