스택과 큐 직접 구현하기

스택 직접 구현하기

스택을 문제풀이에서 사용하려면 stl에 정의되어있는 stack을 바로 #include<stack>로 불러오면 된다.
하지만 나는 스택이 돌아가는 과정을 좀 더 직관적으로 이해해보기 위해 vector을 사용해서 직접 구현을 해보았다.

직접 구현하는법

다른 분들은 주로 배열과 링크드리스트를 통해서 구현하시는 것 같았다.
배열과 링크드리스트로 스택 구현하기
나는 이러한 것들을 찾아보기도 전에 내가 알고있던 스택의 내용만으로 작성을 했다보니 vector을 사용하여 코드를 작성하였다.

코드 보기

#include<iostream>
#include<vector>
using namespace std;
class Stack {
private:
	vector<int>v;
public:
	int size() {
		return v.size();
	}
	void push(int x) {
		v.push_back(x);
	}
	int peek() {
		if (v.empty()) {
			cout << "스택이 비어있습니다";
			return -1;
		}
		else {
			return v.back();
		}
	}
	void pop() {
		if (v.empty()) {
			cout << "스택이 비어있습니다." << endl;
		}
		else {
			v.pop_back();
		}
	}

	void init(int x) {
		// x로 초기화
		v = vector<int>(v.size(), x);
	}

};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Stack s;
	s.push(1);
	s.push(2);
	s.pop();
	s.push(4);
}

cout를 통해서 다행히 예상대로 작동하는 것을 확인하였다.
참고로 stack이 비어있을 때 -1을 리턴하는 부분들은 들어오면 안되는 값이 들어왔을 때 백준 문제를 풀다보니 저렇게 처리하도록 만드는 문제가 저렇게 짰다.

더 잘된 코드

다른분들은 스택을 과연 어떻게 직접 구현해내실까가 궁금해서 몇개의 글들을 찾아보았다.
이렇게 구현이 되다니
이 분의 경우 배열의 크기를 임시로 조절하는 방식으로 메모리를 절약하는 게 인상적이어서 개인적으로 감탄했다.

큐 직접 구현하기

스택은 위에 코드를 보면 알 수 있듯 제일 처음 입력된 것이 나중에 나오게 된다.
큐는 가장 먼저 들어간 것이 가장 먼저 나와야한다.
큐의 경우 배열로 구현하게 되면 pop을 할 때 앞 부분이 비어있다거나 하는 문제가 생길 수 있기 때문에 이 부분을 고려하여 직접 구현을 해야한다.

링크드리스트 사용

아까 말한 부분들을 해결하기 위해서 어떤 방법을 쓸까 고민하다 링크드리스트를 사용하였다.
예전에 리트코드에서 비슷한 문제를 봤어서 구조체로 node를 정의한 뒤 그 노드를 통하여 front와 back에 각각 접근하도록 풀었다.

코드

#include<iostream>
using namespace std;

class Queue {
private:
    struct Node {
        int data;
        struct Node* next_Node;
    };

    Node* frontNode;
    Node* backNode;

public:
    Queue() : frontNode(nullptr), backNode(nullptr) {}

    void push(int data) {
        Node* newNode = new Node;
        newNode->data = data;
        newNode->next_Node = nullptr;
        if (isEmpty()) {
            frontNode = backNode = newNode;
        }
        else {
            backNode->next_Node = newNode;
            backNode = newNode;
        }
    }

    void pop() {
        if (isEmpty()) {
            cout << "큐가 비어있으면 원소의 삭제가 불가합니다";
        }
        else {
            Node* temp = frontNode;
            frontNode = frontNode->next_Node;
            delete temp;
        }
        if (isEmpty()) {
            backNode = nullptr;
        }
    }

    int frontElement() {
        if (isEmpty()) {
            cout << "큐가 비어있으면 원소의 반환이 불가합니다";
            return -1; 
        }
        else {
            return frontNode->data;
        }
    }

    int backElement() {
        if (isEmpty()) {
            cout << "큐가 비어있으면 원소의 반환이 불가합니다";
            return -1;
        }
        else {
            return backNode->data;
        }
    }

    int getSize() {
        int count = 0;
        Node* current = frontNode;
        while (current != nullptr) {
            count++;
            current = current->next_Node;
        }
        return count;
    }

    bool isEmpty() const {
        return frontNode == nullptr;
    }
};

딱히 주의할점이 많지는 않을 거 같은데 예전에 풀 때에는 nullptr처리를 잘못해서 null포인터 오류가 떴었다.

사용처

stack

예전 카카오 기출문제인 괄호 변환과 같은 문제가 대표적인 스택을 사용하여 푸는 문제이다.
간단하게 말하자면 순서대로 짝을 지어야하는 상황이나, ctrl+z등을 구현할 때 스택을 사용하면 쉽게 풀 수 있다.

queue

큐는 bfs탐색 시에도 사용하고 우선순위 큐 같은 것을 사용하면 프린트 대기열에 대한 문제도 풀 수 있다.
또 예전에 카카오 기출문제인 캐시도 큐를 사용하면 쉽게 풀 수 있다.
나는 당시에는 큐를 활용할 생각을 못해서 vector로 정말 무식하게 풀었는데 나중에 알고보니 큐의 주 사용처중 한 곳이 lru알고리즘 구현이었다.