티스토리 뷰
자료 구조의 한 형태인 '스택'을 코드로 구현해 봤습니다. (배열로)
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <stdio.h> #include <stdbool.h> #define MAX 100 typedef struct stack { int s[MAX]; int top; }Stack; void init(Stack *p) { p->top = -1; } void push(Stack *p,int data) { p->top++; p->s[p->top] = data; } bool isFull(Stack *p) { if (p->top == MAX-1) return true; else return false; } bool isEmpty(Stack *p) { if (p->top == -1) return true; else return false; } int peek(Stack *p) { if (isEmpty(&p)) return NULL; else return *(p->s + p->top); } void pop(Stack *p) { p->top--; } int main(void) { Stack Stack1; init(&Stack1); push(&Stack1, 10); push(&Stack1, 20); push(&Stack1, 30); push(&Stack1, 40); printf("%d\n", peek(&Stack1)); pop(&Stack1); printf("%d\n", peek(&Stack1)); return 0; } | cs |
1~3:기본 헤더인 <stdio.h> 와 bool을 쓰기위한 <stdbool.h>를 include하고 #define을 이용해서 MAX를 100으로 설정.
5~8:구조체 stack을 데이터배열과 가장나중에 들어온 데이터를 볼 수 있는 top으로 하고 이름을 Stack(struct stack과 다름!!)으로 설정.
10~12:Stack의 포인터를 받아서 top를 -1로 초기화 해주는 init 함수(빈 스택을 높이가 -1인 스택으로 정했어요).
14~17:스택에 데이터를 넣는 push함수 입니다.
19~27:스택이 비어있는지, 가득 찼는지 확인해주는 함수들 입니다.
29~32:스택배열을 주면 맨위에 있는 데이터를 반환해주는 함수 입니다.
34~36:스택의 가장 위에있는 데이터를 빼내는 용도(빼내고 그값을 반환하는 경우도 있어요).
38~50:Stack을 Stack1으로 선언해주고 초기화해준다음 데이터 10,20,30,40을 넣고 맨위값(40)을 출력하고 pop(40을 빼낸후) 다시 맨위값(30)을 출력하고 끝나네요. 스택에는 10과 20이 남아있게 됩니다.
리스트로 구현한 스택
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <stdio.h> #include <stdbool.h> #include <stdlib.h> typedef struct stack { int data; struct stack *next; }Stack; typedef struct stackList { Stack *top; }sList; void initStack(sList *list) { list->top = NULL; } void push(sList *list, int data) { Stack *new = (Stack*)malloc(sizeof(Stack)); new->data = data; new->next = list->top; list->top = new; } void pop(sList *list) { Stack *temp = list->top->next; free(list->top); list->top = temp; } bool isEmpty(sList *list) { if (list->top == NULL) return true; else return false; } int peek(sList *list) { if (isEmpty(list)) return NULL; else return list->top->data; } void freeStack(sList *list) { while (!isEmpty(list)) { pop(list); } } | cs |
배열로 구현한 스택과 다른점은 연결리스트로 구현했기 때문에 크기에 제한이 없어요. 그래서 isFull함수는 리스트로 구현한 스택에서는 필요하지 않습니다. 데이터를 추가할때는 메모리 할당(malloc)을 하고 삭제할때는 메모리 해제(free)를 해줘야 합니다. 그래서 프로그램 종료전에 freeStack함수를 호출 하는 것이 바람직 합니다. 이외에는 다른것이 없으므로 main함수는 생략했어요.
'Coding > dataStucture' 카테고리의 다른 글
| 스택의 응용(후위 표기법) (3) | 2018.05.10 |
|---|---|
| LinkedList.h/LinkedList.c (2) | 2018.04.27 |
| Queue.c (0) | 2018.04.17 |
| 스택의 응용(괄호검사).c (0) | 2018.02.23 |