[자료구조] 스택(Stack) 이란? - 컴도리돌이

 

스택(Stack) 이란?

 

스택이란 말 그대로 쌓아놓은 더미로 기본적으로 후입선출 방식으로 가장 최근에 들어온 데이터가 가장 먼저 나가는 형식의 자료구조입니다.

 

스택(Stack)의 연산

스택(stack)의 연산

- 삽입(push) , 삭제(pop)

- is_empty() : 스택이 공백상태인지 검사

- is_full() : 스택이 포화상태인지 검사

- peek(s) : 요소를 스택에서 삭제하지 않고 보기만 하는 연산 

 

스택(stack)의 활용 분야

 

- 자료의 출력이 입력 순서와 역순으로 이루어져야 하는 경우 유용하며, 문서나 그림, 수식 등의 편집기에서 되돌리기(undo) 기능 --- 수행된 명령어들 중에서 가장 최근에 수행된 것부터 순서적으로 취소할 경우

- 함수 호출에서 복귀 순서를 기록하는 데 사용

- 문서나 소스코드에서 괄호 닫기 검사

- 계산기 프로그램에서 입력된 수식을 계산하는 기능

 

스택(stack) 구현 방법

스택(stack) 구현 방법

 

배열로 구현한 스택(stack)

 

배열을 이용한 스택의 구현

top은 가장 최근에 입력되었던 자료를 가리키는 변수로, data []와 top을 전역 변수로 선언하였습니다.

 

배열을 이용한 스택 구현

 

연결리스트를 구현한 스택(stack)

 

연결리스트를 구현한 스택(stack) - 삽입(push) 연산

1. 노드 D의 링크 필드가 노드 C를 가리키도록 한다. : P->link = top;

2. 헤더 포인터 top이 노드 D를 가리키도록 한다. : top = p;

 

연결리스트로 구현한 스택(stack) - 삭제(pop) 연산

 

1. 포인터 변수 p가 노드 C를 가리키도록 한다. : p = top;

2. 헤더 포인터 top이 B를 가리키도록 한다. : top = p->link;

3. 마지막으로 변수 p의 값을 반환하다. : return p;

 

연결리스트로 구현한 스택(stack) 

 

 

#include<stdio.h>
#include<stdlib.h>

typedef int Element;
typedef struct LinkedNode
{
    Element data;
    struct LinkedNode* link;
}Node;

Node* top = NULL;


void error(char* str)
{
    fprintf(stderr,"%s\n",str);
    exit(1);
}

int is_empty(){ return top == NULL;}
void init_stack() { top == NULL;}

Element peek()
{
    if(is_empty())
        error("스택 공백 에러");
    return top->data;
}
Element pop()
{
    Node* p;
    Element e;
    if(is_empty()) error("에러");

    p = top;
    top = p->link;

    e = p->data;
    free(p);
    return e;
}

void destroy_stack()
{
    while(is_empty()==0)
        pop();
}

int size()
{
    Node *p;
    int count = 0;
    for(p = top; p!= NULL; p=p->link)
        count++;
    return count;
}

void push(Element e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->link = top;
    top = p;
}



void print_stack(char* msg)
{
    Node *p;
    printf("%s[%d]= ",msg,size());
    for(p=top; p!= NULL; p = p->link)
        printf("%2d ",p->data);
    printf("\n");
}