[자료구조와 알고리즘] 4장 스택

 

1장 스택과 std::stack

 

1. 스택

 가. 스택(stack)이란?

• stack, 물건을 쌓아 올린 더미 또는 쌓는 행위
• 자료구조에서 스택은 데이터를 쌓아 올리듯이 저장하는 선행 자료구조로서,
  후입선출 원리에 따라 삽입과 삭제가 수행됨
• 후입선출(LIFO): Last-In-First-Out. 나중에 들어온 데이터가 먼저 출력됨
• 데이터의 입출력이 한쪽 방향에서만 수행되는 리스트
• 스택 사용 예)
  • 텍스트 편집기의 실행 취소(undo) 기능
  • 웹브라우저에서 뒤로 가기
  • 함수 호출 시 복귀 주소 기억

2. 스택의 주요 연산

• push(e) : 스택의 맨 위(=맨 마지막에 들어감)에 원소 e를 추가
• pop() : 스택의 맨 위에 있는 원소를 삭제
• top() : 스택의 맨 위에 있는 원소를 참조. peek()
• empty() : 스택이 비어 있으면 true를 반환
• size() : 스택의 원소 개수를 반환

3. 스택의 구현

가. 배열을 이용한 스택의 구현

•  미리 정해진 크기의 배열을 할당하고, 가장 최근에 입력된 자료 위치를 가리키는 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를 이용한 스택의 구현

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

    bool empty() const { return v.empty(); }
    int size() const { return v.size(); }

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

 
 라. 구현한 stack

#include <iostream>
#include <vector>

using namespace std;

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

    bool empty() const { return v.empty(); }
    int size() const { return v.size(); }

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

int main()
{
    Stack<int> stk;
    stk.push(10);
    stk.push(20);
    stk.push(30);
    stk.pop();

    cout << stk.top() << endl;
    stk.push(40);

    while (!stk.empty() ) {  // 스택이 비어있는 상태가 될 때까지 작동
        auto& e = stk.top();
        std:cout << e << ", ";
        stk.pop();
    }
    std::cout << std::endl;

}

 

 
4. std::stack

가. std::stack

• LIFO 방식의 스택 자료 구조를 구현한 컨테이너 어댑터
• 템플릿 매개변수 T는 스택에 저장할 타입을 지정하고,
  Container에는 내부에서 사용할 컨테이너를 지정
• Container에는 deque, vector, list를 지정할 수 있음
• <stack>에 정의되어 있음
• 주요 멤버 함수
  • stack::push(e)
  • stack::pop()
  • stack::top()

나. std::stack 사용 예제

• stack에서 stack<int>의 s가 소문자로 변경되었다. 멤버 함수 사용법은 동일함

 
 

2장 스택의 응용: 문자열과 벡터 순서 뒤집기

 

1. 문자열 뒤집기

 가. 문자열 뒤집기란?

• 문자열의 각 문자 순서를 역순으로 변경
• ex)
  • "HELLO" -> "OLLEH"
  • "ALGORITHM" -> "MHTIROGLA"
  • "RACECAR" -> "RACECAR" -> 역순과 동일한 palindrome
• 문자열을 역순으로 뒤집는 방법은 여러 가지가 있지만, 스택을 사용하여 변경할 수 있음

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

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

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

 다. 문자열 뒤집기 구현 함수

string reverse(const string& str)

{

    stack<char> stk;

    for (char c : str)

        stk.push(c);

   

    string rev;

    while (!stk.empty()) {

        rev += stk.top();

        stk.pop();

    }

    return rev;

}

 

 

2. 벡터 순서 뒤집기

 가. 벡터 순서 뒤집기란?

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

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

 나. 스택을 이용한 벡터 순서 뒤집기 (입력된 벡터 자체의 순서를 변경하는 코드)

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

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

template <typename T>

void reverse(vector<T>& vec)

{

    stack<T> stk;

    for (const auto& e : vec)

        stk.push(e);

    for (int i = 0; i < vec.size(); i++ ) {

        vec[i] = stk.pop();

        stk.pop();

    }

}

 
 라. 문자열과 벡터 순서 뒤집기 구현 함수 동작 확인
 

#include <stack>

#include <String>

#include <vector>

#include <iostream>

using namespace std;

string reverse(const string& str)

{

    stack<char> stk;

    for (char c : str)

        stk.push(c);

   

    string rev;

    while (!stk.empty()) {

        rev += stk.top();

        stk.pop();

    }

    return rev;

}

template <typename T>

void reverse(vector<T>& vec)

{

    stack<T> stk;

    for (const auto& e : vec)

        stk.push(e);

    for (int i = 0; i < vec.size(); i++ ) {

        vec[i] = stk.pop();

        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(vec);

    for (auto e : vec)

        cout << e << ", ";

    cout << endl;

}

 

3장 스택의 응용: 올바른 괄호 검사

 

1. 올바른 괄호 검사

가. 올바른 괄호 검사?

• 괄호만으로 이루어진 문자열이 주어질 때, 괄호의 종류별로 쌍이 제대로 되어 있는지를 검사하기
• 괄호의 종류: [], {}, ()

 나. 올바른 괄호의 조건

• 괄호의 종류 별로 여는 괄호와 닫는 괄호의 개수가 같아야 한다.
• 같은 종류의 괄호에서 여는 괄호가 닫는 괄호보다 먼저 나타나야 한다.
• 마지막 여는 괄호와 쌍이 되는 닫는 괄호가 먼저 나타나야 한다.

 다. 올바른 괄호 검사 알고리즘

• 문자열의 각 문자를 차례대로 검사
  • 여는 괄호 (, {, [를 만나면 스택에 push
  • 닫는 괄호 ), }, ] 를 만나면 
    • 스택이 비어 있으면 false 반환
    • 스택의 top에 있는 문자가 현재 닫는 괄호와 쌍을 이루는 여는 괄호인지를 검사
      • 쌍이 맞으면 스택에서 pop
      • 쌍이 맞지 않으면 false 반환
• 모든 문자열을 검사한 후, 스택이 비어 있는지를 검사
  • 비어있으면 true 반환
  • 그렇지 않으면 false 반환

 
  라. 올바른 괄호 검사 구현 함수
 

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();

        }

    }

    return stk.empty();

}

 
 마. 올바른 괄호 검사 구현 함수 동작 확인
 

#include <iostream>

#include <stack>

#include <String>

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();

        }

    }

    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;

}