Stack 스택은 LIFO(Last In First Out)의 자료구조로, 나중에 들어간 데이터가 먼저 나오는 형태입니다.
데이터를 탑처럼 쌓고, 가져올 때는 위에서부터 가져온다고 생각하면 됩니다.
공대생에게 push의 반대말이 무엇인지 물어보면 pop이라는 대답을 들을 수 있다는 말이 있습니다.
배열을 사용한 간단한 구현 #include <stdio.h> int stack [100000 ], top_pointer;void push () if (top_pointer == 100000 ) { printf ("Error: Full Stack!\n" ); } int in; scanf ("%d" , &in); stack [top_pointer++] = in; } int pop () if (top_pointer <= 0 ) { printf ("Empty\n" ); return 0 ; } else { return stack [--top_pointer]; } } void peek () if (top_pointer <= 0 ) { printf ("Empty\n" ); } else { printf ("Top: %d\n" , stack [top_pointer - 1 ]); } } int main (int argc, char const *argv[]) int a; printf ("1. push\n2. pop\n3. peek\n4. exit\n" ); while (1 ) { scanf ("%d" , &a); switch (a) { case 1 : push(); break ; case 2 : pop(); break ; case 3 : peek(); break ; case 4 : return 0 ; break ; default : break ; } } return 0 ; }
활용은 후위연산 계산기 등에 사용될 수 있을겁니다.
Queue 큐는 FIFO(First In First Out)의 자료구조로, 먼저 들어간 데이터가 먼저 나오는 형태입니다.
스택에 push, pop이 있다면 큐에는 put과 get이 있습니다.
또, front와 rear이라는 위치를 의미하는 용어가 있는데, front는 데이터를 꺼낼 위치를, rear은 데이터를 넣을 위치를 가리킵니다.
큐에는 선형 큐와 순환 큐가 있는데, 선형은 막대모양으로 된 큐로, 데이터를 꺼낼때마다 모든 데이터를 한칸씩 당겨줘야 메모리 활용이 가능하다는 단점이 있습니다.
그외에도 링크드 큐 등이 있지만, 이는 연결리스트 이후에서 설명하도록 하겠습니다.
선형 큐 구현 #include <stdio.h> int queue [1000000 ], cnt = 0 ; void put () if (cnt == 1000000 ) { printf ("Error: Overflow!\n" ); } else { int in; scanf ("%d" , &in); queue [cnt++] = in; } } void get () if (cnt == 0 ) { printf ("Error: Underflow!\n" ); } else { int temp = queue [0 ], i, j; for (i = 1 ; i < cnt + 1 ; ++i) { queue [i - 1 ] = queue [i]; queue [i] = 0 ; } cnt--; printf ("Output: %d\n" , temp); } } int main (int argc, char const *argv[]) char t; printf ("p = put\ng = get\nE = exit\n" ); while (1 ) { scanf ("%c" , &t); switch (t) { case 'p' : put(); break ; case 'g' : get(); break ; case 'E' : return 0 ; break ; default : break ; } } return 0 ; }
순환 큐 구현 #include <stdio.h> int queue [10 ], front = 0 , rear = 0 ; void put () if (rear + 1 == front) { printf ("Error: Overflow!\n" ); } else { if (rear == 10 ) { if (front == 0 ) { printf ("Error: Overflow!\n" ); } else { rear = 0 ; int in; scanf ("%d" , &in); queue [rear++] = in; } } else { int in; scanf ("%d" , &in); queue [rear++] = in; } } } void get () if (front == rear) { printf ("Error: Underflow!\n" ); } else { if (front == 10 ) { front = 0 ; } printf ("Output: %d\n" , queue [front]); queue [front++] = 0 ; } } int main (int argc, char const *argv[]) char t; printf ("p = put\ng = get\nE = exit\n" ); while (1 ) { scanf ("%c" , &t); switch (t) { case 'p' : put(); break ; case 'g' : get(); break ; case 'E' : return 0 ; break ; default : break ; } } return 0 ; }
LinkedList 연결리스트는 노드가 데이터와 포인터를 가지고 기차놀이하듯 연결되어 있는 형태의 자료구조입니다.
구현은 포인터로 다음노드를 가리키고, 그 다음 노드의 포인터는 또 그 다음의 노드를 가리키는 모습을 떠올리면 됩니다.
연결리스트는 단방향 연결리스트와 이중 연결리스트 등으로 나뉩니다.당방향 연결리스트 는 각 노드가 그 다음의 노드 하나를 가리키는 형태이고, 이중 연결리스트 는 각 노드의 두개의 포인터가 그 앞뒤의 노드를 가리키는 형태입니다.
단방향 연결리스트 구현 #include <stdio.h> #include <stdlib.h> typedef struct _node { int val; struct _node *next ; } node; node *first = NULL ; node *last = NULL ; void make_node (int val) node *newnode = (node *) malloc (sizeof (node)); newnode->val = val; newnode->next = NULL ; if (first == NULL ) { first = newnode; last = newnode; } else { last->next = newnode; last = newnode; } } void print_node () node *tmp = first; while (tmp != NULL ) { printf ("%d -> " , tmp->val); tmp = tmp->next; } printf ("Last\n" ); } void free_all () node *tmp = first; node *tmp2 = NULL ; while (tmp != NULL ) { tmp2 = tmp->next; free (tmp); tmp = tmp2; } } int main (int argc, char const *argv[]) char sel; int in; printf ("1. add\n2. print\n3. exit\n" ); while (1 ) { scanf ("%c" , &sel); switch (sel) { case '1' : printf ("input: " ); scanf ("%d" , &in); make_node(in); break ; case '2' : print_node(); break ; case '3' : free_all(); return 0 ; break ; default : break ; } } return 0 ; }
이중 연결리스트 구현 #include <stdio.h> #include <stdlib.h> typedef struct _node { int val; struct _node *prev ; struct _node *next ; } node; node *first = NULL ; node *last = NULL ; void make_node (int val) node *newnode = (node *)malloc (sizeof (node)); newnode->val = val; newnode->prev = last; newnode->next = NULL ; if (first == NULL ) { first = newnode; last = newnode; } else { last->next = newnode; last = newnode; } } void print_node () node *tmp = first; while (tmp != NULL ) { printf ("%d -> " , tmp->val); tmp = tmp->next; } printf ("Last\n" ); } int main (int argc, char const *argv[]) char sel; int in; printf ("1. add\n2. print\n3. exit\n" ); while (1 ) { scanf ("%c" , &sel); switch (sel) { case '1' : printf ("input: " ); scanf ("%d" , &in); make_node(in); break ; case '2' : print_node(); break ; case '3' : return 0 ; break ; default : break ; } } return 0 ; }
LinkedQueue 위에서 언급한 링크드 큐입니다.
구현 #include <stdio.h> #include <stdlib.h> typedef struct _node { int val; struct _node *next ; } node; node *front = NULL ; node *rear = NULL ; void enqueue (int val) node *newnode = (node *)malloc (sizeof (node)); newnode->val = val; newnode->next = NULL ; if (front == NULL ) { front = newnode; rear = newnode; } else { rear->next = newnode; rear = newnode; } } void dequeue () if (front == NULL ) { printf ("Error: Underflow!\n" ); } else { printf ("Output: %d\n" , front->val); node *tmp = front->next; free (front); front = tmp; } } void print_node () node *tmp = front; if (front != NULL ) { printf ("Front -> " ); while (tmp != NULL ) { printf ("%d -> " , tmp->val); tmp = tmp->next; } printf ("Rear\n" ); } else { printf ("Empty\n" ); } } int main (int argc, char const *argv[]) char sel; int in; printf ("1. Enqueue\n2. Dequeue\n3. Print all\n4. Exit\n" ); while (1 ) { scanf ("%c" , &sel); switch (sel) { case '1' : printf ("Input: " ); scanf ("%d" , &in); enqueue(in); break ; case '2' : dequeue(); break ; case '3' : print_node(); break ; case '4' : return 0 ; default : break ; } } return 0 ; }