this.code(2).DS_ Stack & Stack Container(STL)

※ Stack

스택은 LIFO(Last-In-First-Out) 입출력 형태, 즉 후입선출 방식을 가진 자료구조이다.

https://images.app.goo.gl/aei6cA:jvUhK2WN86

위의 그림에서 4, 5번째 그림을 보자.    Last In: 3  /  First Out: 3

즉, 가장 마지막에 들어온 data가 가장 먼저 나가는 것을 알 수 있다.

 

push와 pop의 시간복잡도는 둘 다 O(1)의 시간을 갖는다.

단, 탐색의 시간복잡도는 특정 data를 찾을 때까지 돌아야 하므로 O(n)의 시간을 갖는다.

 

그렇다면 Stack을 왜 사용하는 것일까?

 

※ Stack의 사용이유

undo 즉, Ctrl+z라는 키워드처럼 최근에 실행한 명령어를 취소해야 하기 때문이라는 예를 들 수 있다.

 

조금 더 Computer Science적으로 접근해보면 OS에서 process가 바라보는 memory 영역은 크게 4가지로 나뉜다.

- Code: process가 실행할 코드와 매크로 상수가 기계어로 저장된 공간

- Data: 전역변수, static변수 등의 변수들이 저장된 공간

- Heap: malloc, calloc, realloc, new 와 같은 동적할당을 위한 메모리 공간으로 사용한 후 반드시 해제해야한다!

- Stack: heap에 비해 할당할 수 있는 메모리공간이 적지만 포인터로 접근해야하는 heap에 비해 data처리속도가 빠르다.

 

여기서 Stack Segment의 data를 기록하고 종료하는 메커니즘이 후입선출방식(LIFO)으로 이루어진다.

 

 

 

 

 

 

※ Stack Container (STL) ★★★

stack 컨테이너는 vector 클래스의 interface를 제한해 전형적인 stack메모리 구조의 interface를 제공한다.

stack 컨테이너는 stack 헤더파일에 정의되어 있다. 

http://www.tcpschool.com/cpp/cpp_container_adapter

stack 컨테이너는 stack 메모리구조 표현을 위해 다음과 같은 멤버 함수를 제공한다.

http://www.tcpschool.com/cpp/cpp_container_adapter

 

 

※ Stack 선언방식

#include <stack>

stack<데이터타입> 이름;

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

int main() {
    stack<int> intStack1;
    stack<int> intStack2;

    intStack1.push(1);
    intStack1.push(2);
    intStack1.push(3);

    intStack2.push(10);
    intStack2.push(20);
    intStack2.push(30);

    swap(intStack1, intStack2);

    while (!intStack1.empty()) {
        cout << intStack1.top() << endl;
        intStack1.pop();
    }
}

/*
 * 출력결과
 * 30
 * 20
 * 10
 */

출처: https://life-with-coding.tistory.com/406 [코딩젤리:티스토리]

 

 

 

[Stack 관련 백준문제]

백준 10828번: https://www.acmicpc.net/problem/10828

10828번: 스택

백준 1874번: https://www.acmicpc.net/problem/1874

1874번: 스택 수열

백준 3986번: https://www.acmicpc.net/problem/3986

3986번: 좋은 단어

백준 1725번: https://www.acmicpc.net/problem/1725

1725번: 히스토그램

 

 

 

 

 

 

 

 

 

 

※ Stack 자료구조의 구현

위에서 STL 즉, 이미 구현되어 있는 자료구조를 사용한 것을 보았다. 우리는 그 자료구조가 어떻게 구현되어 있는지 뜯어볼 필요가 있다.

 

(pseudo code) 의사코드로 먼저 표현

 

 

§ 배열로 구현

#include <iostream>
using namespace std;

inline void Err (char* ErrMessage){
    printf("%s\n", ErrMessage);
    exit(1);  // 실패상태코드로 프로그램 강제 종료
}

const int Max_Stack_Size = 10;

class stack{
private:
    int top;
    int arr[Max_Stack_Size];
public:
    bool isEmpty();
    bool isFull();
    int push(int data);
    void pop();
    void show();
    void Quit();

    stack() { top = -1; }
    ~stack(){ }
};

bool stack::isEmpty() {
    return top == -1;
}
bool stack::isFull() {
    return top == Max_Stack_Size - 1;
}

int stack::push(int data) {
    if (isFull())
        Err("Stack is Full");
    arr[++top] = data;
}
void stack::pop(){
    if (isEmpty())
        Err("Stack is Empty");
    arr[--top];
}

void stack::show(){
    if (isEmpty())
        cout << "Empty Stack" << endl;
    if (isFull())
        cout << "Full Stack" << endl;
    for (int i = 0; i <= top; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;
}

void stack::Quit(){
    exit(0);
}

int main() {
    stack stack;
    int arr[Max_Stack_Size], i=0;
    int data;
    int num;  // 1. isEmpty  /  2. isFull / 3. push / 4. pop / 5. show / 6. Quit
    while (true){
        cout << "1. push / 2. pop / 3. isEmpty  / 4. isFull / 5. show / 6. Quit"<< endl;
        cin >> num;
        if (num == 1) {
            cout << "push할 숫자를 입력하세요" << endl;
            cin >> data;
            stack.push(data);
        }
        if (num == 2)
            stack.pop();
        if (num == 3)
            stack.isEmpty();
        if (num == 4)
            stack.isFull();
        if (num == 5)
            stack.show();
        if (num == 6)
            stack.Quit();
    }
}

 

 

 

feat. 백준 9012번: https://www.acmicpc.net/problem/9012

9012번: 괄호

§ 예제. 괄호검사 알고리즘. 

조건 1): 왼쪽과 오른쪽 괄호 개수 동일

조건 2): 왼쪽이 먼저 나와야 함

조건 3): 서로 다른 타입의 왼쪽과 오른쪽 괄호쌍을 교차하지 말것.

 

Ex. 

C++로 쉽게 풀어쓴 자료구조 / 천인국.최영규 저

 

(pseudo code) 의사코드로 먼저 표현

 

※ STL을 포함한 stack 실전 구현

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

bool checkBracket(char* s){
    stack<char> stack;  // 괄호를 검사하기 위해 사용할 stack
    map<char, char> bracketMap = {{')', '('},
                                  {']', '['},
                                  {'}', '{'}};

    for(int i=0; s[i]!='\0'; i++){
        // 왼쪽 괄호를 만나는 경우 stack에 push
        if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
            stack.push(s[i]);
        }
        // 오른쪽 괄호를 만나는 경우 stack의 top과 비교
        if(s[i]==')' || s[i]==']' || s[i]=='}'){
            if(stack.empty()){
                return false;   // stack이 비어있는 경우 false
            }else{
                if(bracketMap.find(s[i])->second != stack.top()){
                    return false;   // stack의 top과 괄호의 짝이 맞지 않는 경우 false
                }else{
                    stack.pop();    // stack의 top과 괄호의 짝이 맞는 경우 pop
                }
            }
        }
    }

    // 최종적으로 stack이 empty된 경우 true, 아닌경우 flase
    if(stack.empty()){
        return true;
    }else{
        return false;
    }
}

int main() {
    char* c1 = "1. {A[(i+1)]=0;}";
    char* c2 = "2. if((i==0)&&(j==0)";
    char* c3 = "3. A[(i+1])=0;";

    cout << c1 << " : " << (checkBracket(c1) ? "True" : "False") << endl;
    cout << c2 << " : " << (checkBracket(c2) ? "True" : "False") << endl;
    cout << c3 << " : " << (checkBracket(c3) ? "True" : "False") << endl;
    return 0;
}