스택(Stack)

C언어를 기반으로 자료구조에서의 스택에 대해 정리해보려한다.

스택(Stack)이란?

스택(Stack)은 데이터를 저장하는 추상적인 자료구조이다. 스택은 Last-In-First-Out(LIFO)의 원칙으로 데이터를 삽입 혹은 삭제한다.

즉, 스택은 LIFO의 원칙에 따라 처음 들어간 데이터가 제일 마지막에 나온다는 특징을 가지고 있다.

---

스택(Stack)의 용어

• Top : 스택(Stack)의 맨 꼭대기를 가르킴
• Push : 스택(Stack)의 Top에 데이터를 삽입함
• pop : 스택(Stack)의 Top값을 삭제함

---

스택(Stack)의 기능 구현

• InitStack : 스택(Stack)을 초기화 시킴
• IsFull : 스택(Stack)이 가득 차 있는지 확인함
• IsEmpty : 스택(Stack)이 비어있는지 확인함
• Push : 스택(Stack)의 Top에 데이터를 삽입함
• Pop : 스택(Stack)의 Top값을 삭제함
• Peek : 스택(Stack)의 Top값을 반환함

---

스택의 기능 구현 코드

스택 구현 코드

#define MAX_STACK 100

typedef struct {
	int items[MAX_STACK];
	int top;

}stack;

InitStack함수 구현 코드

void initstack(stack* pstack) {
	pstack->top = -1;
}

IsFull함수 구현 코드

bool isfull(stack* pstack) {
	return pstack->top == MAX_STACK - 1;
}

IsEmpty함수 구현 코드

bool isempty(stack* pstack) {
	return pstack->top == -1;
}

Push함수 구현 코드

void push(stack* pstack, int item) {
	if (isfull(pstack)) {
		exit(1);
	}
	pstack->items[++(pstack->top)] = item;
}

Pop함수 구현 코드

void pop(stack* pstack) {
	if (isempty(pstack)) {
		exit(1);
	}
	--(pstack->top);
}

Peek함수 구현 코드

int peek(stack* pstack) {
	if (isempty(pstack)) {
		exit(1);
	}
	return pstack->items[pstack->top];
}

---

스택(Stack)의 시간 복잡도

Stack	탐색	삽입	삭제
Big-O	O(n)	O(1)	O(1)

---

느낀점

스택은 자료구조에서 중요한 개념이다. 따라서 스택에 대해 열심히 공부하고, 스택을 이용한 Reverseprint, Isparanbalanced 함수에 대해 생각해보고 구현해봐야겠다.