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언어 소스
3.3 스택(Stack) [디딤돌 자료구조와 알고리즘 with C++]
3.4 큐(Queue) [디딤돌 자료구조와 알고리즘 with C++]
9.2 스택을 이용한 수식 파서 [디딤돌 자료구조와 알고리즘 with C++]
9.3 수식 파서 트리(Numeric Parser Tree) [디딤돌 자료구조와 알고리즘 with C++]
'언어 자료구조 알고리즘 > [C]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| [디딤돌 자료구조와 알고리즘] 5.4 스택 (STACK) (0) | 2016.05.23 |
|---|---|
| [디딤돌 자료구조와 알고리즘] 5.3.2 큐 구현 , 5.3.3 큐 테스트 (0) | 2016.05.23 |
| [디딤돌 자료구조와 알고리즘] 5.3.1 큐(QUEUE) 설계 (0) | 2016.05.23 |
| [디딤돌 자료구조와 알고리즘] 5.3 큐(QUEUE) (0) | 2016.05.23 |
| [디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.3 연결리스트 테스트 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.2 연결리스트 구현 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.2 연결리스트 - 5.2.1 연결리스트 설계 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.3 동적 배열 테스트 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.2 동적 배열 구현 (0) | 2016.05.16 |
| [디딤돌 자료구조와 알고리즘] 5.1 배열 - 5.1.1 동적 배열 설계 (0) | 2016.05.16 |