6장 스택

https://www.inflearn.com/course/cpp-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9/dashboard

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

목차

◆  스택
  ●  스택의 개념
  ●  스택의 ADT
  ●  스택의 사용 예시

---

◆  스택의 개념

    ● LIFO(Last In First Out), 가장 최근에 들어간 원소가 가장 먼저 나오는 자료 구조
    ● FILO(First In Last Out)과 동일하다

     코팅 테스트 -> 문제를 풀어야 한다.

     문제가 나온다.
     특정 문제에서 스택을 필요로 하는 경우 스택을 선택할 수 있어야 한다.

     이 문제가 스택 문제인지 인지해야 한다.

     1. 가장 최근에 들어온 원소를 알 수 있는 있다.
     2. 가장 최근에 들어온 원소 순으로 나온다.

---

◆  ADT 란?

  ● ADT(Abstract Data Type)는 추상 데이터 타입의 약어

키보드 구매시에도 세부 사항을 모두 보진 않고
필요한 기능만 보고 사는 것처럼 비슷하다.

자료구조에서는 추상 자료형 타입이라고 합니다.
추상 자료형이란 인터페이스만 있고 실제로 구현되지 않는 자료형입니다.
일종의 자료형의 설계라고 생각하면 됩니다.  -저자님 책 p.179-

---

◆  스택의 ADT 

우측 그림은 스택의 ADT를 나타내었습니다.
스택 외부와 내부에 네모 모양으로 표현한 연산과 상태가 보입니다.
(스택 외부 : IsFull() 등 / 스택 내부 : top , data 등)
연산 시 해야 할 동작과 상태가 가지고 있어야 할 값을 정의하고 있으나,
프로그래밍 언어는 무엇을 사용해야 하고 데이터는 이렇게 저장해야 한다는 등의 내용은 없습니다.

스택 공부할때 ADT만 알고 세부 구현은 몰라도 될까? 자료구조의 세부 동작을 공부하면 큰 도움이 됩니다.
문제가 스택인지 알려면 스택의 세부 구현을 아는 게 도움이 많이 됩니다.

스택의 세부 동작
-  push(3)을 호출하면 내부적으로
1. IsFull()을 수행해 data 배열에 데이터가 가득 찼는지 확인하고
2. 가득 차지 않았다면 top을 1만큼 증가시킨 후
3. top이 가리키는 위치에 data[0]에 3을 추가합니다.

-  pop() 연산을 수행하면
1. IsEmpty() 함수로 data 배열에 데이터가 없는 건 아닌지 확인하고
2. 데이터가 있다면 top을 1만큼 감소시키고
3. 데이터 '3'을 반환합니다.

스택의 ADT에서 top은 최근에 삽입한 데이터의 위치입니다.

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/stack.cpp

codingtest_cpp/STL/stack.cpp at main · dremdeveloper/codingtest_cpp

#include <iostream>
#include <stack>
using namespace std;
int stack_func();
int main()
{
	stack_func();

	return 0;
}
int stack_func()
{
	stack<int> s;
	
	// 원소 삽입
	s.push(1); // push : 스택의 맨 위에 원소가 추가합니다. 스택의 상태는 [1] 입니다. 시간 복잡도 : O(1)
	s.push(2); // push : 스택의 맨 위에 원소가 추가합니다. 스택의 상태는 [1,2] 입니다. 시간 복잡도 : O(1)
	s.push(3); // push : 스택의 맨 위에 원소가 추가합니다. 스택의 상태는 [1,2,3] 입니다. 시간 복잡도 : O(1)

	// 맨 위 원소 확인
	cout << "Top element : " << s.top() << endl; // 출력 : 3
	// top() : 스택의 맨 위 원소를 반환합니다. 스택이 비어 있으면 예외를 던집니다. 예를 들어, 현재 스택의 상태는 [1,2,3] 이므로 top()은 3을 반환합니다. 시간 복잡도 : O(1)

	// 원소 삭제
	s.pop(); // pop(): 스택의 맨 위 원소를 제거합니다. 스택이 비어 있다면 예외를 던집니다. 현재 스택의 상태는 [1,2,3] 이므로 pop()은 3을 제거하여 [1,2]가 됩니다. 시간 복잡도 : O(1)
	cout << "Top element after pop : " << s.top() << endl; // 출력 : 2

	// 스택이 비어있는지 확인
	if (!s.empty())
	{
		cout << "Stack is not empty" << endl; // 출력 : Stack is not empty
	}
	// empty : 스택이 비어 있는지 여부를 확인합니다. 비어 있다면 true, 아니면 false를 반환합니다. 현재 스택의 상태는 [1,2] 이므로 empty()는 false를 반환합니다. 시간 복잡도 : O(1)

	// 스택의 크기 확인
	cout << "Stack size : " << s.size() << endl; // 출력 : 2

	// 스택에서 모든 원소를 pop 하여 출력
	while (!s.empty()) {
		cout << "Popping element : " << s.top() << endl;
		s.pop();
	}
	// 반복문을 통해 모든 원소를 제거합니다. 현재 스택 상태는 [1,2]이므로 pop()은 2와 1을 순서대로 제거합니다. 시간 복잡도 : O(1)

	// 스택이 비어있는지 확인
	if (s.empty()) {
		cout << "Stack is empty after popping all ememnts" << endl; //  출력: Stack is empty after popping all elements
	}
	// empty : 스택이 비어 있는지 여부를 확인합니다. 비어 있다면 true, 아니면 false를 반환합니다. 현재 스택의 상태는 빈 상태이므로 empty()는 true를 반환합니다. 시간 복잡도 : O(1)
	return 0;
}

push() 함수로 {1,2,3} 넣고 현재 top은 3을 가리키고 있지만
pop() 함수 연산을 하게 되면 맨 위에 있던 3이 빠져나가고
top의 위치도 2로 옮기게 된다.

C++ 에서는 스택을 사용할 때는 반환값이 없다는걸 기억하기.

---

◆  스택의 사용 예시 (함수 호출)

    ● 함수 호출 시, 현재 함수의 실행 상태(context)를 저장, 새로운 함수로 제어 이동한다.

C++ 강의 듣는거에서 그대로 배워서 쉽게 이해가 된다.
스택 메모리 VS 힙 메모리 파트에서 스택 메모리를 설명해주셨다.

https://wjplorer.tistory.com/11

C++ 함수 호출의 동작 방식

---

    ● (웹 페이지 예시) 페이지를 전환할때마다 스택에 push(), 이전 페이지로 갈때 pop()

---

◆  문제 08번 괄호 짝 맞추기★★

[내가 한 풀이]

#include <iostream>
#include <stack>
using namespace std;

bool problem_08(string s);
int main()
{
	string s_Data1 = "(())()"; // return val : true
	string s_Data2 = "((())()"; // return val : false
	cout << "1번 값은 " << problem_08(s_Data1) << " 입니다." << endl;
	cout << "2번 값은 " << problem_08(s_Data2) << " 입니다.";
	// 출력값
	// 1번 값은 1 입니다.
	// 2번 값은 0 입니다.
	return 0;
}

bool problem_08(string s) 
{
	stack<char> cStack;

	for (char c : s) {
		if (c == '(')
			cStack.push(c);
		else if (c == ')')
			cStack.pop();
	}
	return cStack.empty();
}

[저자님 코드]

https://github.com/dremdeveloper/codingtest_cpp/blob/main/solution/08.cpp

codingtest_cpp/solution/08.cpp at main · dremdeveloper/codingtest_cpp

#include <iostream>
#include <stack>
using namespace std;

bool solution_08(string s);

int main()
{
	cout << solution_08("(())()") << endl; // 1
	cout << solution_08("((())()") << endl; // 0
	return 0;
}

// solution' 함수는 문자열 's'가 올바른 괄호 구조를 가지고 있는지 확인합니다.
// '('  괄호가 나오면 스택에 push(s)하고, ')' 괄호가 나오면 스택에서 pop() 합니다.
// 모든 문자를 확인한 후 스택이 비어있다면 괄호가 올바르게 닫힌 것 입니다.
bool solution_08(string s)
{
	stack<char> stack;

	for (char c : s) {
		// ❶ '(' 괄호를 스택에 푸시합니다.
		if (c == '(') {
			stack.push(c);
		}
		else if (c == ')')
		{
			// ❷  ')' 괄호가 나오면 스택이 비어있는지 확인
			if (stack.empty()) {
				//❸  스택이 비어있다면 괄호 짝이 맞지 않으므로 false반환
				return false;
			}
			else {
				// ❹ 비어있지 않다면 팝 연산(짝을 찾으므로 여는괄호 스택에서 제거)
				stack.pop();
			}
		}
	}
	//❺ 스택이 비어있다면 괄호가 올바르게 닫힌 것이므로 true 반환, 아니라면 false 반환
	return stack.empty();
}

[나의 코드에서 문제]
pop()하기 전에 stack의 .empty()를 확인하지 않아서 문제가 생길 수 있었다.

해결은 이중 for문도 가능하나(직전값과 비교하는식으로)
그러면 시간복잡도가 O(N*N)이 되어버리니 O(N)에서 끝날 수 있는 스택을 사용해야 한다.

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/parenthesesBalanced.cpp

codingtest_cpp/Algorithm_with_DataStructure/parenthesesBalanced.cpp at main · dremdeveloper/codingtest_cpp

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void do_test_08(string expression);

int main()
{
	do_test_08("{}({})"); // 올바르게 짝이 맞는 경우
	do_test_08("{{({})"); // 여는 괄호가 더 많은 경우
	do_test_08("{}({))"); // 닫는 괄호가 더 많은 경우

	return 0;
}

// 두 문자가 짝이 맞는 괄호인지 확인하는 함수
bool isMatchingPair(char first, char second)
{
	// 각 괄호 쌍을 비교하여 일치하면 true 반환
	if (first == '(' && second == ')') return true;
	else if (first == '{' && second == '}') return true;
	else if (first == '[' && second == ']')return true;
	// 일치 하지 않으면 false 반환
	return false;
	// 시간 복잡도 : O(1)
}

// 주어진 괄호 문자열이 올바르게 짝이 맞는지 확인하는 함수
bool areParenthesesBalanced(string expression)
{
	stack<char> stack; // 여는 괄호를 저장할 스택

	// 문자열의 각 문자를 순회
	for (int i = 0; i < expression.length(); i++) {
		// 여는 괄호는 스택에 푸시
		if (expression[i] == '{' || expression[i] == '(' || expression[i] == '[')
		{
			stack.push(expression[i]);
		}
		
		// 닫는 괄호가 나왔을때
		if (expression[i] == '}' || expression[i] == ')' || expression[i] == ']')
		{
			// 스택이 비어있다면 짝이 맞지 않음
			if (stack.empty()) {
				return false;
			}
			// 스택의 top과 현재 닫는 괄호가 짝이 맞는지 확인
			else if (!isMatchingPair(stack.top(), expression[i])) {
				return false;
			}
			// 짝이 맞으면 스택에서 여는 괄호를 팝
			else {
				stack.pop();
			}
		}
	}
	// 스택이 비어있으면 모든 괄호가 짝이 맞음. 아닌 경우는 짝이 맞지 않음.
	return stack.empty();
	// 시간복잡도 : O(N) , n은 입력 문자열 크기
}

void do_test_08(string expression)
{
	if (areParenthesesBalanced(expression)) {
		cout << "괄호가 올바르게 짝이 맞습니다." << endl;
	}
	else
	{
		cout << "괄호가 올바르게 짝이 맞지 않습니다." << endl;
	}
}

bool isMatchingPair(char first, char second)를 함수를 따로 써주는게 좋다.

초급자들은 main 함수에 모든 함수를 다 때려넣는다.

A동작에서 에러나도 main 함수에서 에러나고
B동작에서 에러나도 main 함수에서 에러나기 때문에
디버깅이 어렵고 비 효율적이다.
나중에 코드를 보는것도 헷갈릴 수 있다.
복잡한 조건문이나 로직들은 함수로 따로 빼주는게 좋다.

bool isMatchingPair(char first, char second) 함수가 의미하는 것은
first가 열린괄호 second가 닫힌괄호라면,
괄호 쌍이 맞을 경우 true를 리턴하는 함수이다.

---

나머지 문제 09에서 14번까지는 다음 페이지에 기록하도록 할 예정이다.