언어 자료구조 알고리즘/[C]디딤돌 자료구조와 알고리즘

[디딤돌 자료구조와 알고리즘] 5.4 스택 (STACK)

언제나휴일 2016. 5. 23. 17:15
반응형

5.4 스택(STACK)



 스택은 큐와 달리 가장 최근에 보관한 자료를 먼저 꺼내는 후입선출(LIFO, Last In First Out)형태로 동작하는 자료구조입니다.

 

스택은 배열이나 연결리스트로 구현할 수 있어요.

여기에서는 배열로 구현하는 것을 먼저 해 본 후에 미리 만든 연결리스트를 래핑하는 방법을 살펴보아요.

 

먼저 스택 구조체를 정의하세요.

스택에는 저장소와 가장 최근에 보관한 위치를 멤버로 갖고 있어야 해요.

#define STACK_SIZE  10

typedef struct Stack //Stack 구조체 정의

{

    int buf[STACK_SIZE];//저장소

    int top; //가장 최근에 보관한 인덱스

}Stack;

 

스택에는 보관하는 동작을 Push라 부르고 꺼내는 동작을 Pop이라 불러요.

void Push(Stack *stack,int data); //스택에 보관

int Pop(Stack *stack); //스택에서 꺼냄

 

배열로 스택을 구현할 때는 저장소가 꽉 찼는지 확인하거나 비었는지 확인하는 기능을 제공하죠.

int IsFull(Stack *stack); //스택이 꽉 찼는지 확인

int IsEmpty(Stack *stack); //스택이 비었는지 확인

 

여기에서는 초기화 기능도 제공하기로 해요.

void InitStack(Stack *stack);//스택 초기화

 

초기화 기능에서는 스택의 top 멤버를 -1로 초기화해요.

top은 가장 최근에 보관한 자료의 위치를 기억하고 있어야 해요.

 

void InitStack(Stack *stack)

{

    stack->top = -1; //스택 초기화에서는 top -1로 설정

}

꽉 찼는지 확인하는 기능에서는 top+1이 스택 크기와 같은지 비교해야겠죠.

int IsFull(Stack *stack)

{

    return (stack->top+1)==STACK_SIZE;//top+1 이 스택 크기와 같으면 꽉 찬 상태

}

스택이 비었는지 확인할 때는 top이 초기값 -1과 비교해요.

int IsEmpty(Stack *stack)

{

    return stack->top == -1;    //top -1이면 빈 상태    

}

스택에 보관하는 Push에서는 꽉 찼는지 확인해요.

그리고 꽉 차지 않을 때는 top1 증가한 후에 보관해요.

void Push(Stack *stack,int data)

{

    if(IsFull(stack))

    {

        printf("스택이 꽉 찼음\n");

        return ;

    }

    stack->top++; //top 1 증가

    stack->buf[stack->top] = data;   //데이터 보관

}

스택이 비었는지 확인하는 Pop 함수는 비었는지 확인해요.

그리고 비어 있지 않을 때는 top위치의 값을 반환해야겠죠.

물론 top 1감소해야 해요.

int Pop(Stack *stack)

{

    int re=0;

    if(IsEmpty(stack))

    {

        printf("스택이 비었음\n");

        return re;

    }

    re = stack->buf[stack->top];//top 인덱스에 보관한 값을 re에 설정

    stack->top--;//top 1 감소

    return re;

}

 

 

//스택 - 고정 크기 버퍼, 정수 형식 보관

#include <stdio.h>

#include <stdlib.h>

 

#define STACK_SIZE  10

typedef struct Stack //Stack 구조체 정의

{

    int buf[STACK_SIZE];//저장소

    int top; //가장 최근에 보관한 인덱스

}Stack;

 

void InitStack(Stack *stack);//스택 초기화

int IsFull(Stack *stack); //스택이 꽉 찼는지 확인

int IsEmpty(Stack *stack); //스택이 비었는지 확인

void Push(Stack *stack,int data); //스택에 보관

int Pop(Stack *stack); //스택에서 꺼냄

 

int main(void)

{

    int i;

    Stack stack;

 

    InitStack(&stack);//스택 초기화

    for(i=1;i<=5;i++)//1~5까지 스택에 보관

    {

        Push(&stack,i);

    }

    while( ! IsEmpty(&stack) )//스택이 비어있지 않다면 반복

    {

        printf("%d ",Pop(&stack));//스택에서 꺼내온 값 출력

    }

    printf("\n");

    return 0;

}

void InitStack(Stack *stack)

{

    stack->top = -1; //스택 초기화에서는 top -1로 설정

}

int IsFull(Stack *stack)

{

    return (stack->top+1)==STACK_SIZE;//top+1 이 스택 크기와 같으면 꽉 찬 상태

}

int IsEmpty(Stack *stack)

{

    return stack->top == -1;    //top -1이면 빈 상태    

}

void Push(Stack *stack,int data)

{

    if(IsFull(stack))

    {

        printf("스택이 꽉 찼음\n");

        return ;

    }

    stack->top++; //top 1 증가

    stack->buf[stack->top] = data;   //데이터 보관

}

int Pop(Stack *stack)

{

    int re=0;

    if(IsEmpty(stack))

    {

        printf("스택이 비었음\n");

        return re;

    }

    re = stack->buf[stack->top];//top 인덱스에 보관한 값을 re에 설정

    stack->top--;//top 1 감소

    return re;

}

 

 

 이 책에서는 앞서 만든 큐처럼 연결리스트를 래핑하여 만들기로 할게요.

 


관련 게시글

[디딤돌 자료구조와 알고리즘] 5.4.1 스택 설계, 5.4.2 스택 구현, 5.4.3 스택 테스트


다양한 스택 및 스택 이용

스택 - 고정 크기 버퍼, 정수 형식 보관, C언어 소스

스택 - 버퍼를 동적 할당, 정수 형식 보관, C언어 소스

스택 - 동적 생성, 소멸, C언어 소스

스택 - 버퍼 크기 자동 확장, C언어 소스

스택 - 버퍼 크기 자동 확장, 동적 생성한 자료 보관, C언어 소스

스택 - 연결리스트로 구현, C언어 소스

단일 연결리스트 - 역순 보관(가장 최근에 보관한 데이터가 맨 앞), C언어 소스

3.3 스택(Stack) [디딤돌 자료구조와 알고리즘 with C++]

9.2 스택을 이용한 수식 파서 [디딤돌 자료구조와 알고리즘 with C++]

9.3 수식 파서 트리(Numeric Parser Tree) [디딤돌 자료구조와 알고리즘 with C++]


반응형