«   2018/12   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
Statistics Graph
관리 메뉴

언제나 휴일

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

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

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

언제나 휴일 언제나휴일 2016.05.23 17:20

5.4.1 스택 설계, 5.4.2 스택 구현, 5.4.3 스택 테스트


  

5.4.1 스택 설계


 스택도 연결리스트를 래핑하여 만들게요. 연결리스트 형식을 스택 형식으로 타입 재지정합니다.

#include "LinkedList.h"

typedef LinkedList EHStack;

 

 동적으로 스택을 생성하는 함수와 소멸하는 함수를 제공합시다.

EHStack *New_EHStack();

void Delete_EHStack(EHStack *ehs);

 

 스택에 자료를 보관하는 함수와 꺼내는 함수를 제공합시다.

void EHStack_Push(EHStack *ehs, Element data);

Element EHStack_Pop(EHStack *ehs);

 

 스택이 빈 상태인지 확인하는 함수도 제공합시다.

int EHStack_IsEmpty(EHStack *ehs);


 

5.4.2 스택 구현

 

 스택 구현은 큐 구현과 매우 흡사합니다. 먼저 동적으로 스택을 생성하는 함수와 소멸하는 함수는 큐 구현처럼 래퍼 함수로 구현합니다.

EHStack *New_EHStack()

{

    return New_LinkedList();

}

void Delete_EHStack(EHStack *ehs)

{

    Delete_LinkedList(ehs);

}

 

 스택에 자료를 보관하는 함수도 연결리스트에 순차 보관하는 함수를 호출하는 래퍼 함수입니다.

void EHStack_Push(EHStack *ehs, Element data)

{

    LinkedList_PushBack(ehs,data);

}

 

 스택에서 가장 최근에 보관한 자료를 꺼내는 함수를 작성합시다. 이 부분이 큐와 차이가 있는 부분입니다.

Element EHStack_Pop(EHStack *ehs)

{

    Element element = 0;

 스택이 비어있지 않을 때 가장 최근에 보관한 자료를 꺼내야 합니다.

    if( ! EHStack_IsEmpty(ehs))

    {

 연결리스트에서는 마지막 보관한 자료의 다음 노드를 얻어오는 함수가 있습니다. 이를 통해 얻어온 링크는 더미 노드인 tail 정보이며 이 노드의 이전 노드가 가장 최근에(가장 뒤에) 보관한 자료를 가진 노드의 위치 정보입니다.

        Link last = LinkedList_End(ehs);

        last = last->prev;

 이제 해당 노드의 자료를 반환할 element 변수에 설정하고 해당 위치의 노드를 연결리스트에서 제거합니다.

        element = last->data;

        LinkedList_Erase(ehs,last);

    }

 element를 반환합니다.

    return element;

}

 

 스택이 비었는지 확인하는 함수는 큐의 구현처럼 usage값이 0인지 확인한 값을 반환합니다.

int EHStack_IsEmpty(EHStack *ehs)

{

    return ehs->usage == 0;

}

 

5.4.3 테스트

 

 스택을 테스트하는 코드를 작성합시다.

int main()

{

    EHStack *ehs = 0;

    Book *book = 0;

 먼저 스택을 동적으로 생성합니다.

    ehs = New_EHStack();

 적당히 자료를 스택에 보관합니다. 여기에서는 세 개의 도서를 보관할게요.

    EHStack_Push(ehs,New_Book("C언어","홍길동",10));

    EHStack_Push(ehs,New_Book("C++언어","강감찬",20));

    EHStack_Push(ehs,New_Book("자료구조","김구",5));

 

 

 

 이제 하나의 자료를 꺼내어 봅시다. 가장 최근에 보관한 자료는 "자료구조"입니다.

    book = (Book *)EHStack_Pop(ehs);

    if(book)

    {

        Book_View(book);

        Delete_Book(book);

    }

 

 두 개의 도서 정보를 추가로 보관할게요.

    EHStack_Push(ehs,New_Book("알고리즘","이순신",9));

    EHStack_Push(ehs,New_Book("디자인패턴","정약용",13));

 

 스택이 비어있지 않다면 반복해서 보관한 도서를 꺼내와 출력할게요. 스택은 LIFO 방식으로 자료를 꺼내주므로 "디자인 패턴", "알고리즘", "C++언어", "C언어" 순으로 출력하면 정상적으로 동작하는 것입니다.

    while( ! EHStack_IsEmpty(ehs))

    {

        book = (Book *)EHStack_Pop(ehs);

        if(book)

        {

            Book_View(book);

            Delete_Book(book);

        }

    }

    Delete_EHStack(ehs);

    return 0;

}

 

 이상으로 스택 구현을 마칠게요.

▷실행 결과

<0000000005>:<자료구조>

              저자:김구

<0000000013>:<디자인패턴>

              저자:정약용

<0000000009>:<알고리즘>

              저자:이순신

<0000000020>:<C++언어>

              저자:강감찬

<0000000010>:<C언어>

              저자:홍길동

 이번 장에서 구현한 선형 자료구조는 앞으로 뒤에서 나올 알고리즘을 설명하기 위해 사용할 수 있습니다. 그리고 비선형 자료구조에 관한 구현은 이미 3장에서 이진 탐색 트리를 구현하였고 나머지는 필요할 때마다 소개하고 설계 및 구현하여 이용하기로 할게요.

 

 이 책은 알고리즘 중심으로 문제 해결 능력을 다루는 책입니다. 자료구조를 중심으로 집필한 책들과 다루는 소재가 비슷할 수 있지만 집필 순서나 설명의 초점이 다룰 수 있습니다.


관련 게시글

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


실습한 소스 및 헤더 파일

스택.zip


다양한 스택 구현 및 활용

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

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

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

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

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

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

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

3.4 큐(Queue) [디딤돌 자료구조와 알고리즘 with C++]

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

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


0 Comments
댓글쓰기 폼