STACK(스택)이 뭔가요?[2]

본 포스트는 c언어를 중심으로 작성되었습니다.

STACK(스택)이 뭔가요?

앞선 포스트를 먼저 보고 오심을 추천드립니다.

저번 포스트에 이어 스택의 포인터변수를 이용한 구현방식에 대해서 알아보겠습니다.

 

요새 공부를 좀 많이 땡기다보니, 아무래도 포스트를 많이 하면서 또 필자 또한 뿌듯함을 느낍니다.ㅋㅋㅋ뭐 여튼 각설하고

 

앞서서 구현했던 방식은 순차자료구조 형식이란 점 모두 인지하실거라 생각합니다. 1차원 배열변수를 이용하여 아주 쉽게 구현했었죠. 그렇지만 앞서서 포스팅을 보고 오신 분이라면 아시겠지만, 그닥 효율이 좋은 구조는 못됩니다. 아무래도 고정된 크기를 사용하는 만큼 가변적으로 크기가 바뀌어야 할 상황에서 그렇게 잘 못하기 때문에 일단 크게 크기를 잡아놔야 넉넉하다는 겁니다. 그치만 그렇게 되면 메모리 사용의 효율성이 많이 떨어지기 때문에 좋다곤 볼 수 없습니다. 만약 개발자 본인이 그렇게만 사용해도 난 뭐 더 필요하지 않아라고 한다면 할 말이 없네요 ㅎㅎㅎ

 

 

넘어가서 단순연결리스트를 사용해서 연결스택을 구현해 보겠습니다. 각 스택의 데이터는 연결리스트에서 노드가 됩니다. 즉 스택에 데이터를 삽입할때마다 연결리스트에 노드를 하나씩 연결하는 결과라는 말이죠.

 

스택원소의 순서는 연결리스트 노드의 링크로 표현할 예정입니다!

 

스택의 논리적 구조

 

그냥 간단하게 생각해서 좌우식에서 상하식으로 바뀐것 그뿐입니다. 그간에 생성 , 삽입, 삭제 등 또한 비슷한 과정을 거칩니다.

 

그렇다면 실제 코드상에서 어떨지 한번 보겠습니다.

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef int value;
//스택에 들어갈 데이터의 자료형을 정수형으로 정의
 
typedef struct StackNode
{
    value data;
    struct stackNode* link;
} stackNode;
//스택의 노드를 구조체로 정의한건데 뭐 앞서봤던 연결리스트 만드는
//구조체와 동일합니다
 
stackNode* x;
 
int IsNull()
{
    if(x == NULL)return 1;
    else return 0;
}//앞서서 보았던 null상태 확인하는 함수입니다.
 
void InIt(value key)
{
    stackNode* cc = (stackNode*)malloc(sizeof(stackNode));
    cc -> data = key;
    cc -> link = x;//삽입하는 노드를 최상위 노드 위에 연결합니다.
    x = cc;//최상위 노드위치를 삽입 노드로 이동시킵니다.
}
 
value pop()
{
    value key;
    stackNode* first = x;
 
    if(x == NULL)
    {
        printf("\n 스택이 비어있습니다");
        return 0;
    }
    else
    {//스택이 null이 아닌경우에,
        key = first -> data;
        x = first -> link;//최상위 노드를 삭제 노드로 이동
        free(first);//삭제된 노드의 동적메모리를 반환
        return key;//삭제된 데이터를 반환
    }
}
 
//노드 검색하는 알고리즘
value search()
{
    if(x == NULL)
    {
        printf("\n 스택이 비어있습니다");
    }
    else
    {
        //최상위 노드 데이터를 반환함
        return (x -> data);
    }
}
 
void Print()
{
    //스택의 데이터를 최상위 데이터에서 
    //최하위 데이터까지 순서대로 출력하는 연산
    stackNode* p = x;
    printf("\n 스택 : {");
    while(p)
    {
        printf("%d", p->data);
        p = p -> link;
    }
    printf("}");
}
 
int main()
{
    value key;
    x = NULL;
    printf("\n 연결 스택 연산");
    Print();
    InIt(1); Print();
    InIt(2); Print();
    InIt(3); Print();
 
    key = search(); Print();
    printf("search : %d",key);
 
    key = pop(); Print();
    printf("\n pop : %d",key);
 
    key = pop(); Print();
    printf("\n pop : %d",key);
 
 
    key = pop(); Print();
    printf("\n pop : %d",key);
 
    return 0;
}
    
 
 

 

출력결과로는

연결 스택 연산

스택 : {}

스택 : {1}

스택 : {21}

스택 : {321}

스택 : {321}search : 3

스택 : {21}

pop : 3

스택 : {1}

pop : 2

스택 : {}

pop : 1

 

이해가 가지않는 부분있다면 댓글주세요!

 

댓글/피드백 환영합니다!!