반응형
스택의 ADT
* void StackInit(Stack* pstack);
- 스택의 초기화를 진행한다.
- 스택 생성 후 제일 먼저 호출되어야 하는 함수이다.
* int SIsEmpty(Stack* pstack);
- 스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)를 반환한다.
* void SPush(Stack* pstack, Data data);
- 스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.
* Data SPop(Stack* pstack);
- 마지막에 저장된 요소를 삭제한다.
- 삭제된 데이터는 반환이 된다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
* Data SPeek(Stack* pstack);
- 마지막에 저장된 요소를 반환하되 삭제하지 않는다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
배열기반 스택
Main.c
#include <stdio.h>
#include "ArrayBaseStack.h"
int ArrayBaseStackMain(void)
{
// Stack의 생성 및 초기화
Stack stack;
StackInit(&stack);
// 데이터 넣기
SPush(&stack, 1); SPush(&stack, 2);
SPush(&stack, 3); SPush(&stack, 4);
SPush(&stack, 5);
// 데이터 꺼내기
while (!SIsEmpty(&stack))
printf("%d ", SPop(&stack));
return 0;
}
ArrayBaseStack.h
#ifndef __AB_STACK_H__
#define __AB_STACK_H__
#define TRUE 1
#define FALSE 0
#define STACK_LEN 100
typedef int Data;
typedef struct _arrayStack
{
Data stackArr[STACK_LEN];
int topIndex;
} ArrayStack;
typedef ArrayStack Stack;
void StackInit(Stack* pstack); // 스택의 초기화
int SIsEmpty(Stack* pstack); // 스택이 비어있는지 확인
void SPush(Stack* pstack, Data data); // 스택의 push 연산
Data SPop(Stack* pstack); // 스택의 pop 연산
Data SPeek(Stack* pstack); // 스택의 peek 연산
#endif
ArrayBaseStack.c
구현해보기
#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"
void StackInit(Stack* pstack) // 스택의 초기화
{
}
int SIsEmpty(Stack* pstack) // 스택이 비어있는지 확인
{
}
void SPush(Stack* pstack, Data data) // 스택의 push 연산
{
}
Data SPop(Stack* pstack) // 스택의 pop 연산
{
}
Data SPeek(Stack* pstack) // 스택의 peek 연산
{
}
구현
#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"
void StackInit(Stack* pstack) // 스택의 초기화
{
pstack->topIndex = -1;
}
int SIsEmpty(Stack* pstack) // 스택이 비어있는지 확인
{
if (pstack->topIndex == -1)
return TRUE;
else
return FALSE;
}
void SPush(Stack* pstack, Data data) // 스택의 push 연산
{
pstack->topIndex += 1;
pstack->stackArr[pstack->topIndex] = data;
}
Data SPop(Stack* pstack) // 스택의 pop 연산
{
int rIdx;
if (SIsEmpty(pstack))
{
printf("Stack Memory Error!");
exit(-1);
}
rIdx = pstack->topIndex;
pstack->topIndex -= 1;
return pstack->stackArr[rIdx];
}
Data SPeek(Stack* pstack) // 스택의 peek 연산
{
if (SIsEmpty(pstack))
{
printf("Stack Memory Error!");
exit(-1);
}
return pstack->stackArr[pstack->topIndex];
}
연결기반 스택
main.c
#include <stdio.h>
#include "ListBaseStack.h"
int main(void)
{
// Stack의 생성 및 초기화
Stack stack;
StackInit(&stack);
// 데이터 넣기
SPush(&stack, 1); SPush(&stack, 2);
SPush(&stack, 3); SPush(&stack, 4);
SPush(&stack, 5);
// 데이터 꺼내기
while (!SIsEmpty(&stack))
printf("%d ", SPop(&stack));
return 0;
}
ListBaseStack.h
#ifndef __LB_STACK_H__
#define __LB_STACK_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node // 연결 리스트의 노드를 표현한 구조체
{
Data data;
struct _node* next;
} Node;
typedef struct _listStack // 연결 리스트 기반 스택을 표현한 구조체
{
Node* head;
} ListStack;
typedef ListStack Stack;
void StackInit(Stack* pstack); // 스택 초기화
int SIsEmpty(Stack* pstack); // 스택이 비어있는지 확인
void SPush(Stack* pstack, Data data); // 스택의 push 연산
Data SPop(Stack* pstack); // 스택의 pop 연산
Data SPeek(Stack* pstack); // 스택의 peek 연산
#endif
ListBaseStack.c
구현해보기
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"
void StackInit(Stack* pstack)
{
}
int SIsEmpty(Stack* pstack)
{
}
void SPush(Stack* pstack, Data data)
{
}
Data SPop(Stack* pstack)
{
}
Data SPeek(Stack* pstack)
{
}
구현
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"
void StackInit(Stack* pstack)
{
pstack->head = NULL; // 포인터 변수 head는 NULL로 초기화
}
int SIsEmpty(Stack* pstack)
{
if (pstack->head == NULL) // 스택이 비면 head에는 NULL이 저장된다.
return TRUE;
else
return FALSE;
}
void SPush(Stack* pstack, Data data)
{
Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
newNode->data = data; // 새 노드에 데이터 저장
newNode->next = pstack->head; // 새 노드가 최근에 추가된 노드를 가리킴
pstack->head = newNode; // 포인터 변수 head가 새 노드를 가리킴
}
Data SPop(Stack* pstack)
{
Data rdata;
Node* rnode;
if (SIsEmpty(pstack)) {
printf("Stack Memory Error!");
exit(-1);
}
rdata = pstack->head->data; // 삭제할 노드의 데이터를 임시로 저장
rnode = pstack->head; // 삭제할 노드의 주소 값을 임시로 저장
pstack->head = pstack->head->next; // 삭제할 노드의 다음 노드를 head가 가리킴
free(rnode); // 노드 삭제
return rdata; // 삭제된 노드의 데이터 반환
}
Data SPeek(Stack* pstack)
{
if (SIsEmpty(pstack)) {
printf("Stack Memory Error!");
exit(-1);
}
return pstack->head->data; // head가 가리키는 노드에 저장된 데이터 반환
}반응형