[ 자료구조 ] 5. 연결리스트를 이용한 스택(Stack)

  스택(Stack)을 구현하는 방법은 크게 단순 배열(Array)을 이용한 방법과 단방향 연결 리스트(Linked List)를 이용한 방법이 있습니다. 이번 시간에는 연결 리스트(Linked List)를 이용한 방법에 대해 간단히 알아보도록 하겠습니다.

※ 스택 선언하기 ※

  스택 선언은 기존의 연결 리스트와 동일하게 진행합니다.

----------------------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer next;

} Node;

NodePointer top = NULL;

----------------------------------------------------------------

※ 스택에 삽입하기 ※

  스택 삽입도 기존의 연결 리스트와 흡사하게 진행합니다. 다만 단방향이라서 top을 기준으로만 삽입해주면 됩니다.

----------------------------------------------------------------

int push(int data) {

NodePointer ptr;

ptr = (NodePointer) malloc(sizeof(Node));

// 컴퓨터에 남은 메모리가 없는 경우 

if(ptr == NULL) {

printf("메모리 할당에 실패했습니다.\n");

return -1;

}

ptr->data = data;

// 스택이 비어있는 경우 

if(top == NULL) {

ptr->next = NULL;

}

// 스택이 비어있지 않은 경우

else {

ptr->next = top;

}

// 새 노드를 최상단 노드로 설정합니다. 

top = ptr;

return 1;

}

----------------------------------------------------------------

※ 스택 정보 출력하기 ※

  top부터 출발해서 NULL을 만날 때까지 모든 원소를 출력해주기만 하면 됩니다.

----------------------------------------------------------------

void show() {

NodePointer ptr = top;

while(ptr != NULL) {

printf("%d\n", ptr->data);

ptr = ptr->next;

}

}

int main(void) {

push(5);

push(7);

push(3);

show();

return 0;

}

----------------------------------------------------------------

  실행 결과는 다음과 같습니다.