[자료구조(C언어)] 스택(Stack) 구현하기 1

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

스택 구현하기

1) 배열을 이용한 구현

stack.c

#include "stack.h"
#define MAX_CAPACITY 100

char stack[MAX_CAPACITY];
int top = -1; // index of the top element

void push(char ch) {
    if (is_full())
        return;
    top++;
    stack[top] = ch;
}

void pop() {
    char tmp = stack[top];
    top--;
    return tmp;
}

char peek() {
    return stack[top];
}

int is_empty() {
    return top == -1;
}

int is_full() {
    return top == MAX_CAPACITY-1;
}

top = 0에서 시작 : top이 배열의 마지막 원소 다음 칸을 가리키게 됨

top = -1에서 시작 : top이 배열의 마지막 원소를 가리키게 됨

 

스택을 배열로 표현하면, 배열의 크기보다 더 많은 데이터를 저장할 수 없기 때문에

배열이 가득차면 더 이상 push할 수 없다.

 

pop()이나 peek()를 호출하기 전에는 먼저 스택이 empty인지 검사해야 한다.

 

2) 연결리스트를 이용한 구현

연결리스트에서는 맨 앞에 노드를 삽입/삭제하는 것이 편하다.

따라서 연결리스트의 첫 번째 노드를 stack의 top으로 한다.

 

구조체 정의

struct node {
	char *data;
	struct node *next;
};
typedef struct node Node;

Node *top = NULL;

 

함수

void push(char *item) {
	Node *p = (Node *)malloc(sizeof(Node));
	p->data = item;
	p->next = top;
	top = p;
}

char *pop() {
	if (is_empty())
		return NULL;
	char *result = top->data;
	top = top->next;
	return result;
}

char *peek() {
	if (is_empty())
		return NULL;
	return top->data;
}

int is_empty() {
	return top == NULL;
}

 

 

문제점

• 만약 스택이 동시에 2개 이상 필요하다면?
• 서로 다른 타입의 데이터를 저장할 스택이 필요하다면?

 

-> 다음 포스팅에서 해결법에 대해 다룰 예정이다.