[자료구조] 스택 (Stack) - 괄호검사, 수식계산, DFS

728x90

1. 스택 (Stack)

1.1 스택이란?

스택(Stack)이란 데이터의 삽입과 삭제를 한 쪽(top)에서만 할 수 있는 LIFO(Last In First Out) 형식의 자료구조이다.

LIFO(Last In First Out)란 후입선출 방식이라고 하며, 가장 최근에 들어온 데이터가 가장 먼저 나가는 것을 의미한다.

1.2 스택 ADT

객체

LIFO 접근방법을 유지하는 동일한 자료형의 요소들의 모음

연산

push(x) : 요소 x를 스택의 맨 위에 추가
pop() : 스택의 맨 위의 요소를 삭제하고 반환
peek() : 스택의 맨 위의 요소를 삭제하지 않고 반환
isEmpty() : 스택이 비어있으면 true 아니면 false 반환
isFull() : 스택이 가득 차 있으면 true 아니면 false 반환
size() : 스택 내의 모든 요소 개수를 반환
display() : 스택 내의 모든 요소 출력

1.3 스택의 구조 및 연산

스택은 순서대로 연결된 선형구조 형태의 자료구조이며, 배열(Array)과 연결 리스트(Linked List)를 이용하여 구현할 수 있다.

우선 이해를 위해 배열로 스택을 구현해보자.

스택에서 top은 가장 최근에 입력되었던 데이터의 위치를 가리키는 변수이다.

스택을 최초로 생성하여 아무런 데이터가 없는 상태에서의 top은 -1이다.

이후 데이터가 추가되거나 삭제될 때마다 top의 값이 변하며 최근 데이터의 위치 값을 가진다.

Push는 스택에 데이터를 추가하는 연산이다.

계속하여 이야기했듯이 스택에서 가장 위에 데이터가 삽입된다.

Push의 시간복잡도는O(1)이다.

Pop은 스택에서 가장 위에 있는 데이터를 삭제하는 연산이다.

삭제하면서 해당 값을 반환하므로, 이를 사용할 수 있다.

Pop의 시간 복잡도 또한 O(1)이다.

1.4 Array를 이용한 스택의 구현 (C++)

간단하게 int 형을 담을 수 있는 stack을 배열을 이용하여 구현해보자.

#include <iostream>
using namespace std;

#define MAX_STACK_SIZE 20

// Stack Class
class Stack {
private:
    int top;
    int data[MAX_STACK_SIZE];

public:
    Stack(){
        top = -1;
    }
    ~Stack(){}

    void push(int n){
        if(isFull()){
            cout << "Stack Full Error" << endl;
            exit(1);
        }
        data[++top] = n;
    }

    int pop(){
        if(isEmpty()){
            cout << "Stack Empty Error" << endl;
            exit(1);
        }
        return data[top--];
    }

    void size(){
        cout << "size : " << top+1 <<endl;
    }

    void display(){
        for(int i=0; i<=top; i++){
            cout << "[" << data[i] << "]";
        }
        cout << endl;
    }

    bool isEmpty(){
        return top == -1;
    }
    bool isFull() {
        return top == MAX_STACK_SIZE - 1;
    }
};

int main() {
    Stack stack;

    for(int i=0; i<10; i++){
        stack.push(i);
    }
    stack.size();
    stack.display();

    stack.pop();
    stack.pop();
    stack.pop();
    stack.size();
    stack.display();
}

1.5 Linked List를 이용한 스택의 구현 (C++)

Array를 이용한 스택은 구현은 간편하지만 스택의 크기가 제한된다는 단점이 있다.

위 code에서 구현한 스택의 크기는 MAX_STACK_SIZE 20이다.

반면 Linked List를 이용하여 스택을 구현하면 데이터의 최대 개수가 한정되어 있지 않으며 삽입, 삭제가 용이하다.

하지만 일일이 노드를 따라가서 조회를 해야 하므로 배열에 비해 데이터의 조회가 힘들다.

Single Linked List (단일 연결 리스트)를 이용해 스택을 구현해보자.

#include <iostream>
using namespace std;

// Node Struct
struct Node {
    int data;
    Node* link; // 이전 Node를 가리키는 pointer

public:
    Node(){
        link = NULL;
        data = 0;
    }
    Node(int n, Node* preNode = nullptr){
        data = n;
        link = preNode;
    }
    ~Node(){}
};

// Stack Class
class Stack {
private:
    Node* top;      // Stack의 top을 가리키는 Node pointer
    int dataSize;   // Stack에 저장된 데이터 size

public:
    Stack(){
        top = nullptr;
        dataSize = 0;
    }
    ~Stack(){
        while(!isEmpty()){
            pop();
        }
        delete top;
    }

    //새로운 node를 생성 후 top을 새로운 node로 변경
    //새로운 node의 link에는 이전node(top이였던)가 들어감
    void push(int n){
        Node* node = new Node(n, top);
        top = node;
        dataSize++;
    }

    //stck이 비어있는 경우 error occurred
    //그렇지 않다면, 우선 top node의 데이터를 임시 변수 'data'에 담아놓음
    //top을 이전 node로 변경한 다음 삭제된 node(top이였던)는 delete 처리 (메모리자원을위해)
    //아까 담아놓은 'data'를 반환
    int pop(){
        if(isEmpty()){
            cout << "Stack Empry Error" << endl;
            exit(EXIT_FAILURE);
        }else{
            int data = top->data;
            Node* node = top;
            top = top->link;
            delete node;
            dataSize--;
            return data;
        }
    }

    // stack의 모든 data 출력
    void display(){
        if(isEmpty()){
            cout << "Stack is Empty" << endl;
        }else{
            Node* node = top;
            while(node){
                cout << "[" << node->data << "]";
                node = node->link;
            }
            cout << endl;
        }
    }

    // stack size 반환
    int size(){
        return dataSize;
    }

    bool isEmpty(){
        return dataSize == 0;
    }
};

int main() {
    Stack stack;

    for(int i=0; i<10; i++){
        stack.push(i);
    }
    cout << "size : " << stack.size() << endl;
    stack.display();

    stack.pop();
    stack.pop();
    stack.pop();
    cout << "size : " << stack.size() << endl;
    stack.display();
}

1.6 C++에서의 Stack 사용 (STL)

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

void display(stack<int> s){
    while(!s.empty()){
        cout << "[" << s.top() << "]";

        s.pop();
    }
    cout << endl;
}

int main() {
    stack<int> s;

    for(int i=0; i<10; i++){
        s.push(i);
    }
    cout << "size : " << s.size() << endl;
    display(s);

    s.pop();
    s.pop();
    s.pop();
    cout << "size : " << s.size() << endl;
    display(s);
}

1.7 Java에서의 Stack 사용 (java.util.Stack)

java에서도 Stack 클래스를 이용하여 stack을 구현해보았다.

import java.util.Stack;

public class Main {
    public static void main(String args[]){
        Stack<Integer> s = new Stack<>();

        for(int i=0; i<10; i++){
            s.push(i);
        }

        System.out.println("size : " + s.size());
        System.out.println(s.toString());

        s.pop();
        s.pop();
        s.pop();

        System.out.println("size : " + s.size());
        System.out.println(s.toString());
    }
}

2. 스택 사용해보기

2.1 괄호 검사

괄호 검사 알고리즘
1. 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 stack에 push, 오른쪽 괄호를 만나면 stack의 top과 괄호의 짝이 맞는지 비교
2. 짝이 맞는 경우 stack에서 pop 수행하고 1번 반복, 짝이 맞지 않거나 stack이 비어있는 경우 False!!
3. 문자열을 전부 검사한 후 stack이 비어있으면 True!! 만약 stack에 괄호가 남아있다면 False!!
C++ 구현

#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;
}

2.2 수식계산

$2 * (4 + 6) / 10 - 8$

우리가 흔히 사용하는 중위표기법으로 나타낸 수식이다.

하지만 컴퓨터는 일반적으로 후위표기법을 사용한다.

후위표기법을 사용하는 경우 식 자체에 우선순위가 포함되어 있어 연산자의 우선순위를 고려할 필요가 없다. 또한 중위표기식은 괄호와 연산자의 우선순위 때문에 수식을 끝까지 읽은 다음 계산을 해야 하지만, 후위표기식의 경우 수식을 읽으면서 바로바로 계산을 수행할 수 있다.

수식 표기법 종류
- 중위표기법 : 연산자를 피연산자 사이에 표기
- 전위표기법 : 연산자를 피연산자 앞에 표기
- 후위표기법 : 연산자를 피연산자 뒤에 표기
중위표기식 → 후위표기식 → 계산 알고리즘
- Step1) 중위표기식 → 후위표기식
  1. 입력값이 피연산자인 경우 그대로 출력
  2. 입력값이 연산자인 경우
    - 스택이 비어있다면 push
    - 스택이 비어있지 않다면 입력값과 top 비교
      - 스택의 top보다 연산자 우선순위가 높은 경우 push
      - 스택의 top보다 연산자 우선순위가 낮거나 같은 경우 top의 우선순위가 입력값보다 높아질 때까지 pop하여 출력한 후 입력값 push
  3. 입력값이 괄호인 경우
    - ((왼쪽괄호)의 경우 스택에 push 후 최하위 우선순위로 취급
    - )(오른쪽괄호)를 만나면 스택에서 (위에 쌓여있는 모든 연산자를 pop하여 출력 후 왼쪽괄호 삭제
  4. 입력이 끝나면 스택의 남은 연산자들을 모두 pop하여 출력
- Step2) 후위표기식 계산
  1. 입력값이 숫자인 경우 스택에 push
  2. 입력값이 연산자인 경우 스택에서 top 2개를 pop하여 연산한 후 다시 스택에 push
  3. 입력이 끝나면 스택에 남아있는 숫자 하나가 연산의 정답임.
C++ 구현

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

// 연산자 우선순위 계산
int getOpPriority(char op){
    switch(op){
        case '(' : case ')' : return 0;
        case '+' : case '-' : return 1;
        case '*' : case '/' : return 2;
    }
    return -1;
}

// 중위연산식 -> 후위연산식
string infixToPostfix(string s){
    stack<char> stack;              // 연산자 stack
    string postfixExpression = "";  // 후위연산식

    for(int i=0; s[i]!='\0'; i++){
        if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/') {  // 연산자
            if (stack.empty()) {
                stack.push(s[i]);
            } else {
                // 현재 연산자 우선순위보다 stack의 top 연산자 우선순위가 높을때 까지 pop 후 현재 연산자 push
                while (!stack.empty() && getOpPriority(s[i]) <= getOpPriority(stack.top())) {
                    postfixExpression.push_back(stack.top());
                    stack.pop();
                }
                stack.push(s[i]);
            }
        }else if(s[i]=='('){    // 왼쪽괄호
            stack.push(s[i]);
        }else if(s[i]==')'){    // 오른쪽괄호
            // 왼쪽괄호 위에 쌓여있는 모든 연산자 pop 후 왼쪽괄호 삭제
            while(!stack.empty() && stack.top()!='('){
                postfixExpression.push_back(stack.top());
                stack.pop();
            }
            stack.pop();
        }else{  // 피연산자
            if(s[i]==' '){
                continue;
            }else{
                postfixExpression.push_back(s[i]);
            }
        }
    }

    // 스택의 남은 연산자를 모두 pop
    while(!stack.empty()){
        postfixExpression.push_back(stack.top());
        stack.pop();
    }

    return postfixExpression;
}

// 후위연산식 계산
double calculatePostfix(string s){
    stack<int> stack;               // 피연산자 stack
    int step = 1;                   // 연산 순서

    for(int i=0; s[i]!='\0'; i++){
        if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/') {  // 연산자
            int num1 = stack.top();
            stack.pop();
            int num2 = stack.top();
            stack.pop();
            cout << "   " << step++ << ". " << num2 << s[i] << num1 << endl;

            switch(s[i]){
                case '+' : stack.push(num1 + num2); break;
                case '-' : stack.push(num1 - num2); break;
                case '*' : stack.push(num1 * num2); break;
                case '/' : stack.push(num1 / num2); break;
            }
        }else{
            stack.push(s[i] - '0');
        }
    }

    return stack.top();
}

int main() {
    cout << "==== infix -> postfix ====" << endl;
    string infixExpression = "6+8/(2*3)+1";
    cout << "- 중위연산식 : " << infixExpression << endl;
    string postfixExpression = infixToPostfix(infixExpression);
    cout << "- 후위연산식 : " << postfixExpression << '\n' << endl;

    cout << "==== calculate posfix ====" << endl;
    cout << "- 연산순서" << endl;
    cout << "- 답 : " << calculatePostfix(postfixExpression) << endl;

    return 0;
}

2.3 미로탐색 알고리즘 (DFS)

깊이 우선 탐색(DFS) 알고리즘
- 깊이 우선 탐색은 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용
- 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용 가능
- 시간복잡도 O(N)
DFS 과정
1. 시작 노드를 스택에 push 하고 해당 노드는 방문했다고 표시한다.
2. 스택의 최상단(top) 노드로부터 인접한 노드 중 방문하지 않은 노드가 있다면 스택에 push하고 방문 표시를 한다. 만약 인접한 노드 중 방문하지 않은 노드가 없다면 스택에서 최상단(top) 노드를 pop 한다.
3. 스택이 empty 될 때까지 2번을 반복한다.
미로탐색 알고리즘
- DFS 알고리즘 이용
- 노드를 탐색하는 과정에서 해당 노드가 출구(x)인 경우 SUCCESS!!
C++ 구현

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

struct Location2D{
    int row;    // 현재 위치의 행
    int col;    // 현재 위치의 열

    Location2D(int r, int c){
        row = r;
        col = c;
    }
};

const int MAX_SIZE = 6;
char map[MAX_SIZE][MAX_SIZE] ={
        {'1','1','1','1','1','1'},
        {'e','0','1','0','0','1'},
        {'1','0','0','0','1','1'},
        {'1','0','1','0','1','1'},
        {'1','0','1','0','0','x'},
        {'1','1','1','1','1','1'}
};

// (row, col) 위치에 갈 수 있는지 검사
bool isValidLoc(int row, int col){
    if(row<0 || col<0 || row>MAX_SIZE || col>MAX_SIZE){
        return false;
    }else{
        return map[row][col] == '0' || map[row][col] == 'x' ? true : false;
    }
}

// 시각적으로 Map 보여주기
void printMap(int row, int col){
    cout << '\n' << "======= [" << row << ", " << col << "] =======" << endl;
    for(int i=0; i<MAX_SIZE; i++){
        for(int j=0; j<MAX_SIZE; j++){
            if(i==row && j==col){   // 현재 위치
                cout << " ❌️ ";
            }else{
                if(map[i][j] == '1') cout << " ⬛️ ";
                if(map[i][j] == 'x') cout << " 🚩️ ";
                if(map[i][j] == '0') cout << " ◻️ ";
                if(map[i][j] == '.') cout << " 👣️ ";
            }
        }
        cout << endl;
    }
}

int main() {
    stack<Location2D> locStack;
    locStack.push(Location2D(1,0));    // start 좌표

    while(!locStack.empty()){
        // 현재 위치를 구하고 stack에서 삭제
        Location2D here = locStack.top();
        locStack.pop();
        int row = here.row;
        int col = here.col;

        printMap(row, col);

        if(map[row][col] == 'x'){
            cout << "SUCCESS!!" << endl;
            return 0;
        }else{
            map[row][col] = '.';
            if(isValidLoc(row, col-1))  // 좌
                locStack.push(Location2D(row, col-1));
            if(isValidLoc(row, col+1))  // 우
                locStack.push(Location2D(row, col+1));
            if(isValidLoc(row-1, col))  // 하
                locStack.push(Location2D(row-1, col));
            if(isValidLoc(row+1, col))  // 상
                locStack.push(Location2D(row+1, col));
        }
    }

    cout << "FAILED!!" << endl;
    return 0;
}