1. 배열을 이용한 스택 구현
정해진 크기의 배열에서, 배열의 크기에 여유가 있으면 데이터를 하나씩 추가한다.
init: 스택을 초기화 하는 함수. top을 가르키는 변수를 -1로 초기화 한다.
isEmpty: 스택이 비어있는지 체크하는 함수. 비어있으면 1, 비어있지 않으면 0을 반환한다.
push: 스택에 데이터를 삽입하는 함수. 스택이 가득차 있으면 더이상 추가하지 않는다.
pop: 스택에서 데이터를 추출하는 함수. 스택의 top에 에있는 데이터를 반환한다. 스택이 비어있으면 꺼내지 않는다.
seek: 스택의 top에 저장된 데이터를 반환하는 함수. 없어도 되지만 책에 있어서 추가해봤다.
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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include <stdio.h> #define MAX_SIZE 10 typedef struct _stack { int data[MAX_SIZE]; int top; }stack; void init(stack* st) { st->top = -1; } int isEmpty(stack* st) { if (st->top == -1) return 1; else return 0; } void push(stack* st, int data) { if (st->top == MAX_SIZE-1) { printf("stack is full\n"); return; } st->data[++st->top] = data; } int pop(stack* st) { if (isEmpty(st)) { printf("stack is empty\n"); return -1; } return st->data[st->top--]; } int seek(stack* st) { if (isEmpty(st)) { printf("stack is empty\n"); return -1; } return st->data[st->top]; } int main(void) { stack st; init(&st); for (int i = 1; i <= 11; i++) { push(&st, i * 10); printf("stack top : %d\n", seek(&st)); } while(!isEmpty(&st)) printf("pop data : %d \n", pop(&st)); printf("stack top : %d\n", seek(&st)); return 0; } | cs |
예전에 TOP을 초기화할 땐 -1로 했던 것 같은데 요즘엔 0이 대세인 것 같기도하다.
하지만 큰 차이없으니 개인의 취향대로 구현하면 될 것이다.
2. 리스트를 이용한 스택 구현
리스트를 이용할 경우, 배열과 다른점은 top이라는 변수가 따로 없는 것이다. Head가 top과 유사한 역할을 수행한다.
또, 리스트는 제한된 크기가 없기때문에, 메모리가 허용하는 만큼의 데이터를 삽입할 수 있다.
데이터 삽입시 새로운 노드를 생성하고, 새로운 노드에 데이터 할당, NEXT는 HEAD가 가르키고 있던 노드를 할당한다.
그다음 HEAD는 새로운 노드를 가르키게 하면된다.
함수는 배열을 이용한 스택과 같다.
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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include <stdio.h> #include <stdlib.h> typedef struct _node { int data; struct _node* next; }node; typedef struct _stack { node* head; }stack; void init(stack* st) { st->head = NULL; } int isEmpty(stack* st) { if (st->head == NULL) return 1; else return 0; } void push(stack* st, int data) { node* newnode = (node*)malloc(sizeof(node)); newnode->data = data; newnode->next = st->head; st->head = newnode; } int pop(stack* st) { if (isEmpty(st)) { printf("stack is empty\n"); return -1; } int ret = st->head->data; node* temp = st->head; st->head = temp->next; free(temp); return ret; } int seek(stack* st) { if (isEmpty(st)) { printf("stack is empty\n"); return -1; } return st->head->data; } int main(void) { stack st; init(&st); for (int i = 1; i <= 11; i++) { push(&st, i * 10); printf("stack top : %d\n", seek(&st)); } while(!isEmpty(&st)) printf("pop data : %d \n", pop(&st)); printf("stack top : %d\n", seek(&st)); return 0; } | cs |
'컴퓨터공학 > 자료구조' 카테고리의 다른 글
| 큐(queue) (0) | 2018.08.09 |
|---|---|
| 1.2 포인터와 동적 메모리 할당 (0) | 2015.07.19 |
| 1.1 시스템 생명 주기(System Life Cycle) (0) | 2015.07.19 |
| C로 쓴 자료구조론 (0) | 2015.07.19 |