Stack & Queue 라이브러리 및 구현

C와 Python의 Stack과 Queue 라이브러리 사용법과, C++을 통해 직접 구현한 것을 기록하기 위해 작성한다.

Stack과 Queue란?

Stack은 LIFO(Last In First Out)의 자료구조로, 나중에 들어간 데이터가 먼저 나온다.
Queue는 FIFO(First In First Out)의 자료구조로, 먼저 들어간 데이터가 먼저 나온다.

Python의 Stack과 Queue 라이브러리

파이썬에서 Stack과 Queue를 사용하는 방법.

Stack

파이썬에서는 Stack 자료구조가 따로 존재하는 것이 아닌 List 자료구조로 구현 가능하다.

stack = []  # 빈 stack 생성

stack.append(4)  # push(4)
stack.append(5)  # push(5)

top = stack.pop()  # top = 5
top = stack.pop()  # top = 4

top = stack[-1]  # 원소를 pop 하지 않고 값만 참조.

Queue

파이썬에서는 deque 라이브러리를 통해 queue를 구현한다. deque는 Double-Ended Queue의 줄임말이며, 데이터의 출입이 front와 back 관계없이 가능하다. 그렇기 때문에 당연히 이를 queue를 구현하는데 사용할 수 있다.

from collections import deque

queue = deque([1,2])

queue.append(3)  # push(4)
queue.append(4)  # push(5)

front = queue.popleft()  # front = 1
front = queue.popleft()  # front = 2

C++의 Stack과 Queue 라이브러리

C++의 Stack과 Queue는 STL(Standard Template Library)를 통해 이용 가능하다.

Stack

#include <iostream>
#include <stack>

using namespace std;

int main(){
	stack<int> s;
    
    s.push(1);
    s.push(2);
    
    cout << s.top() << endl;  // 2 출력
    s.pop(); // 2 제거
    
    cout << s.size() << endl;  // 1 출력
    cout << s.empty() ? "비어있음" : "안 비어있음" << endl;  // "안 비어있음" 출력
    
    return 0;
}

push(element) : 스택의 최상단에 element를 추가해준다.
pop() : 스택의 최상단 데이터를 제거한다. (반환값 없음)
top() : 스택의 최상단 데이터를 반환한다.
size() : 스택의 원소 개수를 반환한다.
empty() : 스택이 비어있으면 true, 아니라면 false 반환

queue

#include <iostream>
#include <queue>

using namespace std;

int main(){
	queue<int> q;
    
    q.push(1);
    q.push(2);
    
    cout << s.front() << endl;  // 1 출력
    cout << s.back() << endl;  // 2 출력
    s.pop(); // 1 제거
    
    cout << s.size() << endl;  // 1 출력
    cout << s.empty() ? "비어있음" : "안 비어있음" << endl;  // "안 비어있음" 출력
    
    return 0;
}

push(element) : 큐의 가장 뒤에 element를 추가해준다.
pop() : 큐의 가장 앞 데이터를 제거한다. (반환값 없음)
front() : 큐의 가장 앞 데이터를 반환한다.
back() : 큐의 가장 뒤 데이터를 반환한다.
size() : 큐의 원소 개수를 반환한다.
empty() : 큐가 비어있으면 true, 아니라면 false 반환

C++로 직접 구현

Stack과 Queue 자료구조를 직접 구현해보자

Stack

template <typename T> 
class Stack{
private:
    int _top, _maxSize;
    T *_stack;
    
    bool _isFull();
public:
    Stack(int size = 10);
    
    bool empty();
    
    void push(T value);
    T pop();
    
    T top();
    int size();
};

// 생성자. size 기본값 10
template <typename T> 
Stack<T>::Stack(int size){
    _maxSize = size;
    _stack = new T[_maxSize];
    _top = -1;
}

// 스택이 꽉차있는지 여부를 확인
template <typename T> 
bool Stack<T>::_isFull(){
    if (_top >= _maxSize)
        return true;
    else
        return false;
}

// 스택이 비어있는지 여부를 확인
template <typename T> 
bool Stack<T>::empty(){
    if (_top <= -1)
        return true;
    else
        return false;
}

// 스택에 value 값을 push해준다.
template <typename T> 
void Stack<T>::push(T value){
    _top++;
    
    // 스택이 모두 차면, size doubling 해준다.
    if (_isFull()){
        T *newStack = new T[_maxSize * 2];
        for (int i = 0; i < _maxSize; i++)
            newStack[i] = _stack[i];
        delete[] _stack;
        _stack = newStack;
        
        _maxSize *= 2;
    }
    
    _stack[_top] = value;
}

// 스택의 가장 위의 원소를 꺼내어 반환한다.
// 원소가 없을 시, Error.cpp의 ElementEmpty 발생
template <typename T> 
T Stack<T>::pop(){
    if (empty())
         throw Error::ElementEmpty; // 에러 처리. 원하는 거 암거나...
    else
        return _stack[_top--];
}

// 스택의 top을 반환한다.
template <typename T> 
T Stack<T>::top(){
    if (empty())
        throw Error::StackEmpty; // 에러 처리. 원하는 거 암거나...
    else
        return _stack[_top];   
}

// 현재 스택의 size를 반환한다.
template <typename T> 
int Stack<T>::size(){
    return _top + 1;
}

배열을 통해 구현하였으며, 데이터의 개수가 많아질 경우 배열의 크기를 doubling해줬다.

Queue

// Circular Queue로 구현 
template <typename T>
class Queue{
private:
    // _front는 가장 첫번째 원소 앞칸을 가리킴. 해당 칸은 항상 비어있는 상태임.
    // _rear는 가장 마지막 원소를 가리킴. 해당 칸이 비어있다면, queue가 비어있음
    int _front, _rear, _maxSize;
    T *_queue;
    
    void _sizeDoubling();
public:
    Queue(int size = 10);
    
    bool empty();
    
    void push(T value);
    T pop();
    
    T front();
    T back();
    int size();
};

template <typename T>
void Queue<T>::_sizeDoubling(){
    T *newQueue = new T[_maxSize * 2];
    
    // 모든 데이터가 차례대로 저장되어 있는 경우. (첫번째 데이터의 index가 0 또는 1인 경우)
    if ((_front + 1) % _maxSize <= 1 ){
        for(int i = (_front + 1) % _maxSize, j = 1; i < _maxSize; i++, j++)
            newQueue[j] = _queue[i];
    }
    else{
        int j = 1;
        for(int i = _front + 1; i < _maxSize; i++, j++)
            newQueue[j] = _queue[i];
        for(int i = 0; i < _rear; i++, j++)
            newQueue[j] = _queue[i];
    }
    
    delete[] _queue;
    _queue = newQueue;
    
    _front = 0;
    _rear = _maxSize - 1;
    
    _maxSize *= 2;
}

template <typename T>
Queue<T>::Queue(int size){
    _maxSize = size;
    _queue = new T[_maxSize];
    _front = _rear = 0;
}

template <typename T>
bool Queue<T>::empty(){
    if (_front == _rear)
        return true;
    else
        return false;
}

template <typename T>
void Queue<T>::push(T value){
    _rear = (_rear + 1) % _maxSize;
    
    if (_front == _rear){
        _sizeDoubling();
        
        return push(value);
    }
    
    _queue[_rear] = value;
}

// queue의 front에서 값을 빼옴.
// queue가 비어있으면 Error.cpp의 ElementEmpty 발생
template <typename T>
T Queue<T>::pop(){
    if (empty())
        throw Error::ElementEmpty; // 에러 처리. 원하는 거 암거나...
    else{
        _front = (_front + 1) % _maxSize;
        return _queue[_front];
    }
}

template <typename T>
T Queue<T>::front(){
    if (empty())
        throw Error::ElementEmpty; // 에러 처리. 원하는 거 암거나...
    else
        return _queue[(_front + 1) % _maxSize];
}

template <typename T>
T Queue<T>::back(){
    if (empty())
        throw Error::ElementEmpty; // 에러 처리. 원하는 거 암거나...
    else
        return _queue[_rear];
}

template <typename T>
int Queue<T>::size(){
    return (_rear - _front + _maxSize) % _maxSize;
}

Circular Queue를 배열을 통해 구현하였으며, 데이터의 개수가 많아질 경우 배열의 크기를 doubling해줬다.

스크롤 내리기...