괄호 검사란? 괄호의 종류로는 대중소가 있는데 3가지 조건이 성립해야 한다. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 동일 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 서로 다른 타입의 괄호 쌍이 서로를 교차하면 안된다. 괄호 검사 알고리즘 여는 괄호가 나오면 위치와 함께 PUSH 닫는 괄호가 나오면 POP을 하여 짝을 비교 비교 순서 1. 스택의 길이가 0이면 여는괄호가 앞에 없고 닫는괄호가 나왔다는 것이기 때문에 에러 2. 스택의 길이가 0이 아닌 경우에는, 일단 POP을 한 뒤 현재 괄호와 짝이 맞는 괄호가 스택에 있는지 검사한다. (짝이 맞다면 아무것도 안해도됨, 이미 pop을 했기 때문) 만약 아니라면 POP했던 괄호를 PUSH해줘야함.(여기까지가 여는괄호에러)..

스택의 구현 스택을 구현할 때는 배열로 구현할 수도 있고, 연결리스트(Linked List)를 이용해 구현할 수 있다. 여기서는 배열을 이용해 간단히 구현해본다. 스택의 초기화 #include #define STACK_SIZE 10 // 스택의 사이즈 int stack[STACK_SIZE]; // 스택 int top = -1; // 가장 위의 원소를 가리킬 top 변수 스택의 사이즈를 결정할 STACK_SIZE를 할당하고 해당 사이즈만큼의 배열을 선언한다. 또한 가장 위의 원소를 가리킬 top 변수를 -1로 초기화한다. 이는 스택의 인덱스를 0부터 시작하기 위함이다. 스택의 isFull(), isEmpty() 함수 구현 int isFull(){ if(top >= STACK_SIZE -1){ // stac..

스택의 용도 1. 자료의 순서를 뒤집는데 유용하다. 스택의 요소를 하나씩 뽑아서 배열에 저장한다. 그럼 배열의 요소가 뒤집어지게 된다. 이런 방식으로 데이터의 순서를 뒤집는데 스택이 많이 활용되고 있다. 2. 재귀 함수를 제거하는데 유용하다. 재귀 함수는 자기 자신을 계속 호출하는 함수입니다. 그렇기 부를 때마다 스택 메모리를 잡는다. 함수 안에 가지고 있는 변수를 스택 메모리에 저장한다. 그렇게 스택의 중간 변수값을 계속 올리고 있는 것이다. 따라서 재귀 함수를 재귀를 빼고 반복문으로 작성할 수 있다. 스택의 중간 값을 저장하는 과정을 스택 자료 구조로 사용할 수 있습니다. 스택 자료구조 + 반복문 - > 재귀로 만듦. 3. 컴퓨터 연산 순서에 맞게 자료 재정리합니다. 대표적인 예로 후위(postfix..

Stack의 개념 스택 자료구조는 마치 접시가 쌓이는 것과 비슷하다. 접시를 쌓을 때 아래부터 위로 차근차근 접시를 쌓게 될 것이다. 이때 접시를 가장 먼저 꺼낼 수 있을 것이고 가장 아래에 있는 접시는 가장 나중에 꺼낼 수 있게 될 것이다. 스택도 이와 동일하다. 스택은 후입선출 LIFO(Last in First Out)의 구조로 가장 나중에 들어간 원소가 가장 먼저 나오게 된다. Stack의 연산 push(data) pop() Stack의 구현 스택을 구현 할 때는 배열로 구현할 수도 있고, 연결리스트(Linked List)를 이용해 구현할 수도 있다. 여기서는 배열을 이용해 간단히 구현해본다. #include #define STACK_SIZE 10 // 스택의 사이즈 int stack[STACK_S..