Stack(스택) 구현 및 링크드리스트

<본 포스팅은 공부목적으로 작성되었습니다. 혹시 틀린 부분이 있거나 문제가 되는 부분이 있다면 답글 달아주세요!>

 

Stack(스택)

• Last In First Out :가장 마지막에 들어온 값이 가장 먼저 제거된다.
• 한 쪽에서만 자료를 넣고 제거할수 있다.

스택을 배열로 구현할 수도 있고 연결 리스트를 이용하여 구현할 수 있다.

 

#include <stdio.h>
 
typedef struct Stack Node; //Stack을 Node 라고 정의 
typedef int element;
struct Stack{ 
    element data;
    struct Stack *link; //자기참조 구조체로 노드를 정의해준다 
};
Node *top=NULL; //top을 널값으로 초기화
 
void push(element data){ //stack에 data집어 넣기 
    Node *ptr=(Node*)malloc(sizeof(Node)); //노드 동적 할당 
 
    ptr->data=data; //입력받은 data을 할당되어진 노드 data영역에 넣는다. 
    ptr->link=top; //기존 헤더의 주소를 할당되어진 노드 link에 넣는다. 
    top=ptr; //top이 가리키는 주소가 최근 추가된 노드의 주소 갖는다.  
}
element pop(){ //stack에서 data 빼기
    Node *ptr; 
    element dat;
    ptr=top; //top에 저장된 주소를 ptr로 옮긴다.
    top=ptr->link; //빼려는 노드의 link가 밑의 노드 가리키는주소 갖는다
                    //그 주소를 top에 넣어준다.
    dat=ptr->data;
    free(ptr); //빼진 노드에 할당된 동적 메모리 해제 
    return dat; 
}
 
int main(void){
    
 
    push(10);
    push(20);
    push(30);
 
    pop();
     
     while(top!=NULL){
        printf("%d \n",top->data);
        top=top->link;
        
    }
 
 
}

위의 코드는 c로 연결리스트를 이용하여 스택을 구현하였다.

 

실행화면

실행하면 위의 사진과 같이 10 20 30에서 pop이 되어 30이 제거되어진 형태를 확인할 수 있다.