스택

4장 스택

- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.

저의 정리가 옳지 않다면 피드백 부탁드립니다.

---

스택

• 사전적 의미 : 건초 * 밀집 따위를 쌓아 놓은 더미, 낟가리
• ex)

1. 창고에 새로운 상자들을 쌓을 때는 상자더미의 맨 윗부분에 놓는다. 상자가 필요하면 상자더미의 맨 위에 있는 상자를 꺼낸다. 만약 중간에서 상자를 꺼내면 전체 상자가 붕괴될 것이다. 따라서 가장 최근에 들어온 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다.
2. 스마트폰에서 “뒤로 가기” 키를 누르면 현재 수행되는 앱이 종료되고 이전에 수행되던 앱이 다시 나타나는 것.

• 입출력 형태 : 후입선출(LIFO : Last-In First-Out)

특징

• 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.
• 스택 상단(stack top) : 스택에서 입출력이 이루어지는 부분
• 스택 하단(stack bottom) : 스택 상단의 반대쪽으로 바닥부분
• 요소(element) : 스택에 저장되는 것
• 공백 스택(empty stack) : 스택에 요소가 하나도 없을 때
• 하나 이상의 배열로 두개 이상의 스택 표현 가능하다.

기본 연산

• 삽입(push) : 스택에 데이터 삽입
• 삭제(pop) : 스택에서 데이터 추출(과 동시에 삭제)

스택의 응용 : 괄호 검사 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100

typedef char element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} stack;

//스택 생성
void init_stack(stack *s)
{
	s->top = -1;
}

//공백 상태 검사
int isEmpty(stack *s)
{
	return (s->top == -1);
}

//포화 상태 검사
int isFull(stack *s)
{
	return (s->top == MAX_STACK_SIZE - 1);
}

//삽입
void push(stack *s, element item)
{
	if (isFull(s)) {
		fprintf(stderr, "full");
		return;
	}
	else s->data[++(s->top)] = item;
}

//삭제
element pop(stack *s)
{
	if (isEmpty(s)) {
		fprintf(stderr, "empty");
		exit(1);
	}
	else return s->data[(s->top)--];
}

//괄호 검사 알고리즘
int check(const char *str)
{
	stack s;
	int i, n = strlen(str);
	char ch, open;
	init_stack(&s);


	for (i = 0; i < n; i++) {
		ch = str[i];

		switch (ch)
		{
		case '(': case '{': case '[':
			push(&s, ch);
			break;
		case ')': case '}': case ']':
			if (isEmpty(&s)) {
				return 0;
			}
			else {
				open = pop(&s);
				if ((open == '(' && ch != ')') || (open == '{' && ch != '}') || open == '[' && ch != ']')
					return 0;
				break;
			}
		}

	}
	if (!isEmpty(&s)) {
		return 0;
	}
	else {
		return 1;
	}
}

#define _CRT_SECURE_NO_WARNINGS
//사용자가 멈출 때(0을 입력) 까지 괄호 검사
int main(void)
{
	while (1)
	{
		char input;
		printf("문자열을 입력하세요. : \n");
		scanf_s("%s", &input, sizeof(input)*50);
		char *q = "q";

		if (strcmp(&input, q) == 0)
			exit(1);

		if (check(&input) == 1) {
			printf("The string is balanced.\n");
		}
		else {
			printf("The string is unbalanced.\n");
		}
	}
	return 0;
}