연결 리스트로 구현한 스택

연결리스트를 이용한 스택이나 큐를 연결된 스택(Linked stack) 이라고 한다. 외부에서 보기에는 배열을 이용한 스택이나 연결 리스트를 이용한 스택이나 전혀 차이가 없다. 즉 제공되는 외부 인터페이스는 완전히 동일하다. 연결 리스트를 이용하여 스택을 만들게 되면 크기가 제한되지 않는다는 장점이 있다. 동적 메모리 할당만 할 수만 있으면 스택에 새로운 요소를 삽입할 수 있다. 반면에 연결 리스트를 이용한 스택은 동적 메모리 할당이나 해제를 해야 하므로 삽입이나 삭제 시간은 좀 더 걸린다.

연결된 스택은 기본적으로 연결 리스트이기 때문에 다음과 같이 노드를 정의한다. 노드는 우리가 저장하고 싶은 데이터 필드와 다음 노드를 가리키기 위한 포인터가 들어 있는 링크 필드로 구성된다. 또한 top은 더 이상 정수가 아니고 노드를 가리키는 포인터로 선언된다. 또한 연결된 스택에 관련된 데이터는 top 포인터뿐이지만 일관성을 위하여 LinkedStackType 이라는 구조체 타입으로 정의되었다. 모든 함수들은 이 구조체의 포인터를 매게변수로 받아서 사용한다.

typedef int element;
typedef struct StackNode
{
  element data;
  struct StackNode *link;
} StackNode;

typedef struct {
  StackNode *top;
} LinkedStackType;

삽입

삭제

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
#include <malloc.h>
#include <string.h>

typedef int element;
typedef struct StackNode
{
  element data;
  struct StackNode *link;
} StackNode;

typedef struct {
  StackNode *top;
} LinkedStackType;

//초기화 함수
void init(LinkedStackType *s)
{
  s->top = NULL;
}

//공백 상태 검출 함수
int is_empty(LinkedStackType *s)
{
  return (s->top == NULL);
}

//포화상태 검출함수
int is_full(LinkedStackType *s)
{
  return 0;
}

//삽입 함수
void push(LinkedStackType *s, element item)
{
  StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
  temp->data = item;
  temp->link = s->top;
  s->top = temp;
}

void print_stack(LinkedStackType *s)
{
  for (StackNode *p = s->top; p != NULL; p = p->link)
    printf("%d -> ",p->data);
  printf("NULL \n");
}

//삭제함수
element pop(LinkedStackType *s)
{
  if (is_empty(s)) {
    fprintf(stderr,"스택이 비어있음\n");
    exit(1);
  }
  else {
    StackNode *temp = s->top;
    int data = temp->data;
    s->top = s->top->link;
    free(temp);
    return data;
  }
}

// 피크함수
element peek(LinkedStackType *s)
{
  if (is_empty(s)) {
    fprintf(stderr,"스택이 비어있음\n");
    exit(1);
  }
  else {
    return s->top->data;
  }
}

int main()
{
  LinkedStackType s;
  init(&s);
  push(&s,1); print_stack(&s);
  push(&s,2); print_stack(&s);
  push(&s,3); print_stack(&s);
  pop(&s); print_stack(&s);
  pop(&s); print_stack(&s);
  pop(&s); print_stack(&s);
  return 0;
}