[C언어 자료구조] 5. 스택(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에서는 꽉 찼는지 확인해요.
그리고 꽉 차지 않을 때는 top을 1 증가한 후에 보관해요.
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;
}
이 책에서는 앞서 만든 큐처럼 연결리스트를 래핑하여 만들기로 할게요.
'언어 자료구조 알고리즘 > 디딤돌 자료구조 (C언어)' 카테고리의 다른 글
| [C언어 자료구조] 6. 이진 탐색 트리(Binary Search Tree) (4) | 2016.11.27 |
|---|---|
| [C언어 자료구조] 5.4 스택 소스 코드 (0) | 2016.11.26 |
| [C언어 자료구조] 5.3 스택 테스트 (0) | 2016.11.26 |
| [C언어 자료구조] 5.2 스택 구현 (0) | 2016.11.26 |
| [C언어 자료구조] 5.1 스택 설계 (0) | 2016.11.26 |
| [C언어 자료구조] 4.4 큐 소스 코드 (0) | 2016.11.26 |
| [C언어 자료구조] 4.3 큐 테스트 (0) | 2016.11.26 |
| [C언어 자료구조] 4.2 큐 구현 (0) | 2016.11.26 |
| [C언어 자료구조] 4.1 큐 설계 (0) | 2016.11.26 |
| [C언어 자료구조] 4. 큐(Queue) (0) | 2016.11.26 |