Stack의 개념과 구현

< Stack >

 - 일종의 리스트

 - 단, 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어짐 

 - LIFO( Last-In, First-Out )

 - 삽입/삭제가 일어나는 쪽을 스택의 top이라고 부른다. 

 

< Stack의 연산 >

 - push : 스택에 새로운 원소를 삽입하는 연산

 - pop : 스택의 top에 있는 원소를 스택에서 제거하고 반환

 - peek : 스택 top의 원소를 제거하지 않고 반환 

 - empty : 스택이 비었는지 검사 

< 스택 응용 예 : 괄호 검사 문제 >

 - 입력 수식의 괄호가 올바른지 검사 

      예) [a+b*{c/(d-e)}] + (d/e)

 - 단순히 여는 괄호와 닫느 괄호의 개수 비교 만으로는 부족 

 - 스택을 이용하여 검사 

    - 여는 괄는 스택에 push

    - 닫는 괄호가 나오면 스택에서 pop한 후, 두괄호가 같은 유형이어야

    - 마지막에 스택에 남는 괄호가 없어야

 

< 배열을 이용한 Stack 구현 >

#include "stack.h"
#define MAX_CAPACITY 100

char stack[MAX_CAPACITY];
int top = -1;

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

char pop() {
	if (is_empty()) {
		return;
	}
	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;
}

 

 

< 연결리스트로 구현 >

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;
}