자료구조 (Data structure)
[자료구조] 스택(Stack) 구현하기 in C
yoongrammer
2021. 1. 13. 18:53
728x90
목차
스택(Stack) 구현하기 in C
스택 자료형을 구현하는 방법은 일반적으로 다음 방법들을 사용합니다.
- 배열 기반으로 구현
- 동적 배열을 기반으로 구현
- 연결 리스트로 구현
배열 기반으로 구현
배열을 사용하여 스택을 구현하는 방법입니다.
배열 index를 추적하는 top변수를 사용합니다.
top은 -1로 초기화합니다.
top이 -1이라면 스택이 비어있다는 의미이고 배열 크기-1이라면 스택이 가득 찼다는 의미입니다.
push연산은 top을 1 증가시키고 값을 top위치에 저장하도록 구현합니다.
pop연산은 top을 1 감소시키도록 구현합니다.
C 언어로 구현하면 다음과 같습니다.
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct ArrayStack {
int top;
int capacity;
int* array;
} Stack;
/* 주어진 capacity 크기로 stack을 생성하는 함수 */
Stack* createStack(int capacity) {
Stack* stack = (Stack*)malloc(sizeof(Stack));
if (!stack)
return NULL;
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
/* 스택이 비어있는지 확인하는 함수. */
int isEmpty (Stack* stack) {
return (stack->top == -1);
}
/* 스택이 가득찼는지 확인하는 함수. */
int isFull (Stack* stack) {
return (stack->top == stack->capacity - 1);
}
/* top 위치에 있는 값을 가져오는 함수 */
int peek (Stack* stack) {
if(isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
/* 스택에 값을 추가하는 함수 */
void push(Stack *stack, int data) {
if (isFull(stack))
printf("Stack is full\n");
else {
/* top을 1증가시키고 값을 top에 저장함 */
stack->array[++stack->top] = data;
printf("%d pushed to stack\n", data);
}
}
/* 스택에 값을 삭제하는 함수 */
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return INT_MIN;
}
else /* top의 값을 1 감소시킴 */
return (stack->array[stack->top--]);
}
void main()
{
Stack* stack = createStack(3);
push(stack, 1);
push(stack, 2);
push(stack, 3);
push(stack, 4);
printf("%d poped from stack\n", pop(stack));
}Output:
1 pushed to stack
2 pushed to stack
3 pushed to stack
Stack is full
3 poped from stack배열로 구현 시 스택의 사이즈는 동적이 아니기 때문에 꽉 찬 스택에 push를 할 수 없는 문제점이 있습니다.
728x90
동적 배열을 기반으로 구현
배열 문제점은 동적 배열을 사용하면 해결할 수 있습니다.
push연산 시, 배열이 꽉 차있다면 길이가 2배인 새로운 배열을 만들고 이전 배열에 있던 데이터들을 새로운 배열에 복사한 뒤 push를 수행합니다.
push 함수를 동적 배열로 동작하도록 수정하면 다음과 같습니다.
void push(struct Stack *stack, int data) {
if (isFull(stack)) { /* stack이 가득 찼다면 크기를 2배로 늘립니다. */
stack->capacity *= 2;
stack->array = realloc(stack->array, stack->capacity);
}
/* top을 1증가시키고 값을 top에 저장함 */
stack->array[++stack->top] = data;
printf("%d pushed to stack\n", data);
}하지만, 데이터를 새로운 배열에 복사하는 작업은 오버해드가 크다는 문제점이 있습니다.
연결 리스트로 구현
연결 리스트로 스택을 구현하면 리스트 앞에 노드를 추가하거나 삭제하면 되기 때문에 자유롭게 사이즈를 증가시키거나 줄일 수 있습니다.
Push연산은 리스트 맨 앞에 새로운 노드를 추가하도록 구현합니다.
Pop연산은 리스트 맨 앞 노드를 삭제하도록 구현합니다.
C언어로 구현하면 다음과 같습니다.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct ListStack
{
int data;
struct ListStack *next;
} Stack;
int IsEmptyStack (Stack *Top)
{
return (Top == NULL);
}
void push (Stack **Top, int data)
{
Stack *newNode = NULL;
newNode = (Stack*)malloc(sizeof(Stack));
if(newNode == NULL)
{
printf("Stack is full\n");
return;
}
/* 리스트 맨 앞에 새로운 노드를 추가합니다. */
newNode->data = data;
newNode->next = *Top;
*Top = newNode;
printf("%d pushed to stack\n", data);
}
int pop (Stack **Top)
{
Stack *temp = NULL;
int data = 0;
if(IsEmptyStack(*Top))
{
printf("Stack is Empty\n");
return INT_MIN;
}
else
{ /* Top 위치(리스트 맨 앞)에 있는 노드를 제거합니다 */
temp = *Top;
*Top = temp->next;
data = temp->data;
free(temp);
}
return data;
}
void main(void)
{
Stack *S =NULL;
push(&S, 1);
push(&S, 2);
push(&S, 3);
printf("%d poped from stack\n", pop(&S));
}Output:
1 pushed into stack
2 pushed into stack
3 pushed into stack
3 popped from stack
소스 코드는 아래 깃허브에서 받을 수 있습니다.
728x90