[C] 배열을 통해서 간단하게 스택과 큐 구현하기
C언어에서 배열을 통해 기본적인 기능만 하는 스택과 큐를 만들어보자.
환경 및 선수조건
- C언어 및 gcc
- 스택과 큐의 작동원리 및 이해
C언어에서 빠르게 스택과 큐 구현하기
C에서 알고리즘이나 빠르게 코딩을 할 때 배열을 통해서 스택과 큐를 구현하고자 한다. 단, 여기서 배열의 크기는 들어갈 수 있는 최대를 가정하고 구현할 예정! 즉, 동적할당이 아니라 정적할당으로 임의로 사이즈를 정해주고 구현할겁니다.
비록 여기서 배열에 값들을 삭제하거나 하지는 않지만 추상적으로 보면 최소한의 스택과 큐의 기능을 구현합니다.
-
스택은
LIFO(선입후출)의 구조만top이라는 변수를 통해서 구현합니다. -
큐는
FIFO(선입선출)의 구조만head와tail이라는 변수를 통해서 구현합니다.
배열을 통한 스택의 구현
simple_stack_by_array.c
#include <stdio.h>
int main (){
// 스택에 집어넣을 값들
int values[10] = {10,9,8,7,6,5,4,3,2,1};
// 스택과 TOP변수
int stack[100];
int top=0; // <= 처음에 배열의 첫번째 원소가 top이라 볼 수 있다.
// PUSH
for(int i=0; i < sizeof(values)/sizeof(int); i++){
// 아래와 같이 PUSH를 구현
// top변수를 통해서 계속 top을 바라봅니다.
// top - 1의 위치에 가장 최근에 넣은 값이 있습니다.
stack[top++] = values[i];
}
// POP and PRINT
for(int i=0; i < sizeof(values)/sizeof(int); i++){
// 아래와 같이 POP을 구현합니다.
printf("%d ", stack[--top]);
}
printf("\n");
return 0;
}
배열을 통한 큐의 구현
simple_queue_by_array.c
#include <stdio.h>
int main (){
// 큐에 집어넣을 값들
int values[10] = {10,9,8,7,6,5,4,3,2,1};
// 큐와 HEAD 그리고 TAIL변수
int queue[100];
int head=0,tail=0; // <= 처음에 배열의 첫번째 원소가 head와 tail이라 볼 수 있다.
// ENQUEUE
for(int i=0; i < sizeof(values)/sizeof(int); i++){
// 아래와 같이 ENQUEUE를 구현
// ENQUEUE 할때마다 tail의 위치에 값을 넣고 증가시니다.
queue[tail++] = values[i];
}
// DEQUEUE and PRINT
for(int i=0; i < sizeof(values)/sizeof(int); i++){
// 아래와 같이 DEQUEUE을 구현합니다.
// DEQUEUE 할때마다 head의 위치의 값을 반환하고 증가시킵니다.
printf("%d ", queue[head++]);
}
printf("\n");
return 0;
}