Part4. 스택

[01. 스택과 std::stack]

① 스택(stack)이란?

✔︎ stack 물건을 쌓아 올린 더미 또는 쌓는 행위

✔︎ 자료 구조에서 스택은 데이터를 쌓아 올리듯이 저장하는 선형 자료 구조로서, 후입선출 원리에 따라 삽입과 삭제가 수행됨

- 후입선출 : 나중에 들어온 데이터가 먼저 출력됨. LIFO(Last-In First-Out)

- 데이터의 입출력이 한쪽 방향에서만 수행되는 리스트

- 스택의 사용 예:

▪︎ 텍스트 편집기의 실행취소(undo)(ex.ctrl+z) 기능

▪︎ 웹브라우저에서 뒤로 가기

▪︎ 함수 호출 시 복귀 주소 기억

② 스택의 주요 연산

✔︎ push(e) ➠ 스택의 맨 위에 원소 e를 추가

✔︎ pop() ➠ 스택의 맨 위에 있는 원소를 삭제

✔︎ top() ➠ 스택의 맨 위에 있는 원소를 참조. peek()

✔︎ empty() ➠ 스택이 비어 있으면 true를 반환

✔︎ size() ➠ 스택의 원소 개수를 반환

③ 스택의 구현 - ¹ 배열을 이용한 스택의 구현

✔︎ 미리 정해진 크기의 배열을 할당하고, 가장 최근에 입력된 자료 위치를 가리키는 t 변수를 사용

- push(e) : t값을 1 증가시키고, 해당 위치에 e 대입

- pop() : t값을 1 감소

- top() : arr[t]값을 반환

- 장점: 구현이 간단하고, 삽입이나 삭제가 빠르게 동작

- 단점: 미리 정해진 크기보다 많은 데이터를 삽입할 경우, 스택 오버플로우(stack overflow) 에러가 발생

④ 스택의 구현 - ² 연결 리스트를 이용한 스택의 구현

✔︎ 단순 연결 리스트를 이용하여, 새로 추가한 데이터를 연결 리스트 맨 앞에 삽입하는 방식

- push(e) : push_first(e)

- pop() : pop_first()

- top() : head → next 값을 변환

- 장점: 크기가 제한되지 않음

- 단점: 구현이 복잡하고, 삽입이나 삭제 시간이 (배열에 비해) 오래 걸림

⑤ 스택의 구현 - ³ std::vector를 이용한 스택의 구현

push, pop, top, empty, size 모두 다 O(1)이다!!

template <typename T>
class Stack
{
public:
    Stack() {}
    
    void push(const T& e) { v.push_back(e); }
    void pop() { v.pop_back(); }
    const T& top() const { return v.back(); }  //stack 값을 다른 함수에서 변경 못하도록
    
    bool empty() const { return v.empty(); }
    int size() const { return v.size(); }

private:
    std::vector<T> v;
};

#include <iostream>
#include <vector>

template <typename T> class Stack { ... };

int main()
{
    Stack<int> stk;
    stk.push(10);
    stk.push(20);
    stk.push(30);
    stk.pop();
    
    cout<<stk.top()<<endl;    //20
    stk.push(40);   //10,20,40
    
    while(!stk.empty()){   //스택이 비워질 때까지 pop하는 것
        auto& e = stk.top();
        std::cout << e << ", ";  // 40 출력 후 pop, 20 출력 후 pop, 10 출력 후 pop
        stk.pop();
    }
    std::cout << std::endl;
}

⑥ std::stack

✔︎ LIFO(Last-In First-Out) 방식의 스택 자료 구조를 구현한 컨테이너 어댑터(container adaptor)

template<class T, class Container = std::deque<T>>
class stack;

- 템플릿 매개변수 T는 스택에 저장할 타입을 지정하고, Container에는 내부에서 사용할 컨테이너를 지정

- Container에는 deque, vector, list를 지정할 수 있음

- <stack>에 정의되어 있음

- std::stack 사용예제

#include <iostream>
#include <stack>    //vector -> stack으로 변경

template <typename T> class Stack { ... };

int main()
{
    stack<int> stk;  //소문자 s로 변경
    stk.push(10);
    stk.push(20);
    stk.push(30);
    stk.pop();
    
    cout<<stk.top()<<endl;    //20
    stk.push(40);   
    
    while(!stk.empty()){   
        auto& e = stk.top();
        std::cout << e << ", ";  
        stk.pop();
    }
    std::cout << std::endl;
}
//코드 결과는 위의 코드 결과와 같음

[02. 스택의 응용 : 문자열과 벡터 순서 뒤집기]

① 문자열 뒤집기란?

✔︎ 문자열의 각 문자 순서를 역순으로 변경

✔︎ 문자열을 역순으로 뒤집는 방법은 여러 가지가 있지만, 스택을 사용하여 변경할 수 있음

② 스택을 이용한 문자열 뒤집기

✔︎ 문자열의 각 문자를 스택에 push한 후, 다시 스택에서 문자를 하나씩 pop하여 출력 문자열을 생성

- 문자열 뒤집기 구현 함수

#include <iostream>
#include <stack>

using namespace std;

string reverse(const string& str)
{
	stack<char> stk;

	for (char c : str)        //문자열 push
		stk.push(c);

	string res;

	while (!stk.empty()) {    //문자열 출력하면서 pop
		res += stk.top();
		stk.pop();
	}

	return res;
}

int main()
{
	string str1 = "HELLO";
	string str2 = "ALGORITHM";

	cout << str1 << " -> " << reverse(str1) << endl;
	cout << str2 << " -> " << reverse(str2) << endl;
}

③ 벡터 순서 뒤집기란?

✔︎ 벡터의 원소를 역순으로 변경하는 작업

✔︎ 벡터를 역순으로 뒤집는 방법은 여러 가지가 있지만, 스택을 사용하여 변경할 수 있음

④ 스택을 이용한 벡터 순서 뒤집기

✔︎ 벡터의 모든 원소를 스택에 push한 후, 다시 스택에서 원소를 하나씩 pop하여 차례대로 벡터에 넣음

- 벡터의 원소를 역순으로 변경하기

#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

string reverse(const string& str)
{
    stack<char> stk;

    for (char c : str)
        stk.push(c);

    string res;

    while (!stk.empty()) {
        res += stk.top();
        stk.pop();
    }

    return res;
}

template <typename T>
void reverse(vector<T>& vec)
{
    stack<T> stk;
    for (const auto& e : vec)
        stk.push(e);

//    stack<T, vector<T>> stk(vec); 이 한줄은 28,29,30번째 줄을 대체할 수 있다

    for (int i = 0; i < vec.size(); i++) {
        vec[i] = stk.top();
        stk.pop();
    }
}

int main()
{
    string str1 = "HELLO";
    string str2 = "ALGORITHM";

    cout << str1 << " -> " << reverse(str1) << endl;
    cout << str2 << " -> " << reverse(str2) << endl;

    vector<int> vec {10, 20, 30, 40, 50};
//    vector<string> vec {"John", "loves", "Jane"};

    reverse<int>(vec);

    for (auto e : vec)
        cout << e << ", ";
    cout << endl;
}

[03. 스택의 응용 : 올바른 괄호 검사]

① 올바른 괄호 검사란?

✔︎ 괄호만으로 이루어진 문자열이 주어질 때, 괄호의 종류별로 쌍이 제대로 되어 있는지를 검사하기

✔︎ 괄호의 종류 : [ ](대괄호, brackets), { }(중괄호, braces), ( )(소괄호, paraentheses)

- 사칙연산을 할 때를 생각해보면 된다... ➜ ex.[5+{2*(3+4)}] *3 ➜ "[ { ( ) } ]"

② 올바른 괄호의 조건

✔︎ 괄호의 종류별로 여는 괄호와 닫는 괄호의 개수가 같아야 한다

✔︎ 같은 종류의 괄호에서 여는 괄호가 닫는 괄호보다 먼저 나타나야 한다

✔︎ 마지막 여는 괄호와 쌍이 되는 괄호가 먼저 나타나야 한다

③ 올바른 괄호 검사 알고리즘

- 올바른 괄호 검사 구현 함수

#include <iostream>
#include <stack>

using namespace std;

bool paren_check(const string& s)
{
	stack<char> stk;

	for (char c : s) {
		if (c == '(' || c == '{' || c == '[') {
			stk.push(c);
		} else {
			if (stk.empty() || 
				(stk.top() == '(' && c != ')') ||
				(stk.top() == '{' && c != '}') ||
				(stk.top() == '[' && c != ']'))
				return false;

			stk.pop();
		}
	}
    //if(stk.empty()) return true;
    //else return false;
    //이 두 줄을 쓰는 것보다 27번 코드처럼 한 줄 쓰는 것이 낫다

	return stk.empty();
}

int main()
{
    // 올바른 괄호
	cout << paren_check("(){}[]") << endl;
	cout << paren_check("((((()))))") << endl;
	cout << paren_check("(){[()]}") << endl;

    // 올바르지 않은 괄호
	cout << paren_check("((({}))") << endl;
	cout << paren_check(")(") << endl;
	cout << paren_check("({)}") << endl;
}

출처: 어서와! 자료구조와 알고리즘은 처음이지? C++

'[C++ ] 자료구조' 카테고리의 다른 글

Part5. 큐 (0)	2023.05.15
Part3. 연결 리스트 (0)	2023.04.11
Part2. 배열 : C 언어에서 C++ 언어로 (0)	2023.04.03
Part1. 자료구조와 알고리즘은 처음이지? (0)	2023.03.28

부리부리대마왕

Part4. 스택

[01. 스택과 std::stack]

[02. 스택의 응용 : 문자열과 벡터 순서 뒤집기]

[03. 스택의 응용 : 올바른 괄호 검사]

'[C++ ] 자료구조' 카테고리의 다른 글

댓글

티스토리툴바

Part4. 스택

[01. 스택과 std::stack]

[02. 스택의 응용 : 문자열과 벡터 순서 뒤집기]

[03. 스택의 응용 : 올바른 괄호 검사]

'[C++ ] 자료구조' 카테고리의 다른 글

관련글

댓글

티스토리툴바