자료구조와 알고리즘_4_동적배열, 리스트, 스택, 큐

[ 🌱동적 배열 (벡터) ]

 

📍size() vs capacity() :

• size() : 컨테이너에 들어가 있는 실제로 사용중인 데이터의 개수
• capacity() : 컨테이너가 수용가능한 공간의 개수

clear() 이후에 size() 는 0으로 바뀌지만, capacity() 는 한번 늘어난 크기는 줄어들지 않는다.

 

📍resize() vs reserve() :

• resize() : 데이터의 개수를 변경시키기에 size 외에도 capacity도 변경시킨다.
• reserve() : 수용량만 변경시키기에 size에는 영향을 주지 않는다.

reserve() 의 인자로 기존의 capacity보다 적은 값이 들어오면 아무런 변화가 없다.

resize() 의 경우 기존의 size보다 적은 값이 들어오면 데이터의 개수를 줄여버리며 기존의 값들은 소멸하게된다.

때문에 std::vector<int>의 경우 resize()로 값을 줄였다가 다시 늘리면 기존에 값이 들어가 있던 위치에 0이 들어가있다.

 

📍간단 기능 구현 :

구현 목록 : 

• push_back()
• size()
• capacity()
• reserve()
• operator[ ] : 벡터는 Random Access 기능 제공한다.
• clear()

---

코드 :

#include <iostream>
#include <vector>

template<class T>
class Vector
{
public:
    Vector() { }

    ~Vector()
    {
        if (_data)
        {
            if (_data)
            {
                delete[] _data;
                _data = nullptr;
            }
        }
    }

    void push_back(const T& value)
    {
        // 가득찬 경우
        if (_size == _capacity)
        {
            // 증설 작업
            int newCapacity = static_cast<int>(_capacity * 1.5);
            if (newCapacity == _capacity)
            {
                newCapacity++;
            }

            // 새로운 메모리 공간 확보 및 기존 데이터 복사
            reserve(newCapacity);
        }

        // 데이터 저장
        _data[_size] = value;

        // 컨테이너에 들어있는 사이즈 개수 증가
        _size++;
    }

    void reserve(int capacity)
    {
        // 기존 수용량이 새로 설정하려는 수용량보다 큰 경우
        if (_capacity >= capacity)
        {
            // 함수 종료
            return;
        }

        // 수용량 갱신
        _capacity = capacity;

        // 새로운 메모리 공간 할당
        T* newData = new T[_capacity];

        // 기존 데이터 복사
        for (int i = 0; i < _size; i++)
        {
            newData[i] = _data[i];
        }

        // 기존 메모리 공간 해제
        if (_data)
        {
            delete _data;
            _data = nullptr;
        }

        // 교체
        _data = newData;
    }

    void resize(int size)
    {
        // 기존 size랑 같은 경우
        if (size == _size)
        {
            return;
        }

        // 더 크게 변경하려는 경우
        if (size > _size)
        {
            // 수용량보다 변경하려는 사이즈가 큰 경우
            if (size > _capacity)
            {
                int newCapacity = static_cast<int>(_capacity * 1.5f);
                reserve(newCapacity);
            }
        }
        // 더 작게 변경하려는 경우
        else
        {
            for (int i = size; i < _size-1; i++)
            {
                _data[i] = 0;
            }
        }

        _size = size;

    }

    T& operator[] (const int idx)
    {
        if (idx >= _size)
            throw std::out_of_range("vector 의 index 범위를 초과했습니다.");

        return _data[idx];
    }

    int size() { return _size; }

    int capacity() { return _capacity; }

    void clear()
    {
        if (_data)
        {
            delete[] _data;
            _data = new T[_capacity];
        }

        _size = 0;
    }

private:
    T*      _data = nullptr;
    int     _size = 0;
    int     _capacity = 0;
};

int main()
{
    std::vector<int> v;
    //Vector<int> v;

    //v.reserve(100);
    std::cout << v.size() << " " << v.capacity() << std::endl;

    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
        std::cout << v.size() << " " << v.capacity() << std::endl;
    }

    v.resize(5);
    std::cout << v.size() << " " << v.capacity() << std::endl;

    v.resize(10);
    for (size_t i = 0; i < v.size(); i++)
    {
        std::cout << v[i] << " " << v.size() << " " << v.capacity() << std::endl;
    }

    v.clear();
    std::cout << v.size() << " " << v.capacity() << std::endl;

    return 0;
}

---

 

---

[ 🌱연결 리스트 ]

대부분의 경우 리스트 보다 벡터를 사용하는 경우가 많다.

그럼에도 불구하고 리스트를 공부해야하는 이유는 "노드"를 사용하는 다른 자료구조들의 기초가 되기 때문이다.

노드를 사용하는 자료 구조의 종류 : 트리(Tree), 테이블(Table), 힙(Heap)

(refer : https://jin-network.tistory.com/127 )

[자료구조] 자료구조 종류

 

📍간단 구현 :

구현 목록 :

• push_back()
• push_front() :
  std::vector 에는 없는 기능. 벡터의 경우 앞에 데이터를 끼워넣는 작업이 매우 효율이 좋지 않기에 기능을 제공하지 않는다. 그에 비해 리스트의 경우 중간 삽입삭제와 같은 기능이 빠르기에 기능을 제공한다.
• pop_back()
• insert() : 추가한 데이터의 iterator를 반환한다. push_back()의 경우 반환값이 없다.
• begin() : list 내의 head 노드의 next 노드를 가리키는 iterator 를 반환한다.
• end() : list 내의 tail 노드를 가리키는 Iterator 를 반환한다.
• Node class : 리스트는 노드 기반 자료구조다.
• Iterator class : list의 경우 vector에서 지원하는 임의접근을 지원하지 않기에 반복자를 통해 특정 노드에 접근할 수 있다.

---

 코드 :

#include <iostream>
#include <list>

template <class T>
class Node
{
public:
    Node()
        : _prev(nullptr)
        , _next(nullptr)
        , _data(T())
    {
    }

    Node(const T& value)
        : _prev(nullptr)
        , _next(nullptr)
        , _data(value)
    {
    }

public:
    Node*	_prev;
    Node*	_next;
    T		_data;
};

template<typename T>
class Iterator
{
public:
    Iterator() : _node(nullptr)
    {

    }

    Iterator(Node<T>* node) : _node(node)
    {

    }

    // ++it
    Iterator& operator++()
    {
        _node = _node->_next;
        return *this;
    }

    // it++
    Iterator operator++(int)
    {
        Iterator<T> temp = *this;
        _node = _node->_next;
        return temp;
    }

    // --it
    Iterator& operator--()
    {
        _node = _node->_prev;
        return *this;
    }

    // it--
    Iterator operator--(int)
    {
        Iterator<T> temp = *this;
        _node = _node->_prev;
        return temp;
    }

    // *it
    T& operator*()
    {
        return _node->_data;
    }

    // 두 Iterator가 가리키는 Node가 동일한지 비교
    // 두 Iterator가 가리키는 Node가 가리키는 Node의 주소 값 비교
    bool operator==(const Iterator& other)
    {
        return _node == other._node;
    }

    bool operator!=(const Iterator& other)
    {
        return _node != other._node;
    }

public:
    Node<T>* _node;
};


template <class T>
class List
{
public:
    List() : _size(0)
    {
        // [head] <-> ... <-> [tail]
        _head = new Node<T>();
        _tail = new Node<T>();
        _head->_next = _tail;
        _tail->_prev = _head;
    }

    ~List()
    {
        while (_size > 0)
        {
            pop_back();
        }

        delete _head;
        delete _tail;
    }

    void push_back(const T& value)
    {
        AddNode(_tail, value);
    }

    void pop_back()
    {
        RemoveNode(_tail->_prev);
    }

    int size() { return _size; }

private:
    // [head] <-> [1] <-> [prevNode] <-> [nextNode] <-> [tail]
    // [head] <-> [1] <-> [prevNode] <-> [newNode] <-> [nextNode] <-> [tail]
    Node<T>* AddNode(Node<T>* nextNode, const T& value)
    {
        Node<T>* newNode = new Node<T>(value);
        Node<T>* prevNode = nextNode->_prev;

        prevNode->_next = newNode;
        newNode->_prev = prevNode;

        newNode->_next = nextNode;
        nextNode->_prev = newNode;

        _size++;

        return newNode;
    }

    // [head] <-> [prevNode] <-> [target] <-> [nextNode] <-> [tail]
    // [head] <-> [prevNode] <-> [nextNode] <-> [tail]
    Node<T>* RemoveNode(Node<T>* target)
    {
        Node<T>* prevNode = target->_prev;
        Node<T>* nextNode = target->_next;

        prevNode->_next = nextNode;
        nextNode->_prev = prevNode;

        delete target;

        _size--;

        return nextNode;
    }

public:
    using iterator = Iterator<T>;

    iterator begin() { return iterator(_head->_next); }
    iterator end() { return iterator(_tail); }

    iterator insert(iterator it, const T& value)
    {
        Node<T>* node = AddNode(it._node, value);
        return iterator(node);
    }

    iterator erase(iterator it)
    {
        Node<T>* node = RemoveNode(it._node);
        return iterator(node);
    }

private:
    Node<T>*	_head;
    Node<T>*	_tail;
    int			_size;
};

int main()
{
    //std::list<int> li;
    List<int> li;

    //std::list<int>::iterator eraseIt;
    List<int>::iterator eraseIt;

    for (int i = 0; i < 10; i++)
    {
        if (i == 5)
        {
            eraseIt = li.insert(li.end(), i * 10);
        }
        else
        {
            li.push_back(i);
        }
    }

    li.pop_back();

    //li.pop_front();

    li.erase(eraseIt);

    //for (std::list<int>::iterator it = li.begin(); it != li.end(); it++)
    for (List<int>::iterator it = li.begin(); it != li.end(); it++)
    {
        std::cout << *it << std::endl;
    }

    return 0;
}

---

 

---

[ 🌱스택 ]

"후입선출 (Last-In-First-Out, LIFO)"의 구조를 가지고 있다.

vector 와 list 에 비해서 기능이 엄청 많지는 않다.

 

📍간단 구현 :

구현 목록 :

• top() : 최상위 원소를 확인할 수 있다.
• pop() : 최상위 원소 삭제
• push()
• empty() : 컨테이너가 비었으면 true, 데이터가 들어있으면 false
• size()

---

코드 :

vector 또는 list를 활용하여 구현할 수 있는데, 이를 통해 인터페이스 통일화에 대한 장점을 볼 수 있다.

#include <iostream>
#include <stack>
#include <vector>
#include <list>

//template <typename T, typename Container>
template <typename T, typename Container = std::vector<T>>
class Stack
{
public:
    void push(const T& value)
    {
        _container.push_back(value);
    }

    void pop()
    {
        _container.pop_back();
    }

    T& top()
    {
        return _container.back();
    }

    int size() { return _container.size(); }
    bool empty() { return _container.empty(); }

private:
    Container _container;
};


int main()
{
    //std::stack<int> s;
    //Stack<int, std::vector<int>> s;
    Stack<int, std::list<int>> s;

    std::cout << "size : " << s.size() << std::endl;

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

    std::cout << "size : " << s.size() << std::endl;

    while (s.empty() == false)
    {
        // 최상위 원소 = 제일 마지막에 삽인된 값
        int data = s.top();
        // 최상위 원소 제거
        s.pop();

        std::cout << data << std::endl;
    }

    std::cout << "size : " << s.size() << std::endl;

    return 0;
}

---

 

---

[ 🌱큐 ]

"선입선출 (First-In-First-Out)"의 구조를 가지고 있다.

front, rear(=back)

stack보다 다양한 경우에 활용할 수 있다. ex) 대기열

 

📍간단 구현 :

구현 목록 :

• push()
• pop() : stack과 달리 제일 앞의 데이터가 나오기에 vector를 통한 구현에 무리가 있다.
• front()
• empty()
• size()

 

case1) ListQueue : 

---

동적배열(벡터) 보다는 연결 리스트를 통해 구현하는게 좀 더 간단해 보인다.

리스트의 중간 삽입/삭제의 유용함이 빛을 본다.

#include <iostream>
#include <queue>
#include <list>

template <typename T>
class ListQueue
{
public:
    void push(const T& value)
    {
        _container.push_back(value);
    }

    void pop()
    {
        _container.pop_front();
    }

    int front()
    {
        return _container.front();
    }

    bool empty()
    {
        return _container.empty();
    }

    int size()
    {
        return _container.size();
    }

private:
    std::list<T> _container;
};

int main()
{
    //std::queue<int> q;
    ListQueue<int> q;

    std::cout << "size : " << q.size() << std::endl;

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

    while (q.empty() == false)
    {
        int value = q.front();
        q.pop();
        std::cout << value << std::endl;
    }

    std::cout << "size : " << q.size() << std::endl;
}

---

 

case2) DequeQueue : 

---

Deque 역시 pop_front() 기능을 지원하기에 Queue::pop() 기능 구현을 간단하게 할 수 있다.

실제 구현된 STL의 Queue의 구현부를 보면 기본 자료구조로 Deque를 사용한다.

위에서 구현한 ListQueue 에서 container의 타입을 std::list 에서 std::deque 로 변경만 해주면 된다.

#include <iostream>
#include <queue>
#include <deque>

template <typename T>
class DequeQueue
{
public:
    void push(const T& value)
    {
        _container.push_back(value);
    }

    void pop()
    {
        _container.pop_front();
    }

    int front()
    {
        return _container.front();
    }

    bool empty()
    {
        return _container.empty();
    }

    int size()
    {
        return _container.size();
    }

private:
    std::deque<T> _container;
};

int main()
{
    //std::queue<int> q;
    DequeQueue<int> q;

    std::cout << "size : " << q.size() << std::endl;

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

    while (q.empty() == false)
    {
        int value = q.front();
        q.pop();
        std::cout << value << std::endl;
    }

    std::cout << "size : " << q.size() << std::endl;
}

---

 

case3) ArrayQueue  : 

---

배열 기반으로 Queue를 구현할 수 있다.

데이터의 유효 범위를 설정해두고 시작 위치를 유동적으로 관리하는 방식을 사용한다. (순환방식)

• 유효범위 : font ~ back-1
• front : 데이터의 시작 위
• back : 새로운 값이 들어갈 장소

#include <iostream>
#include <queue>
#include <vector>

template <typename T>
class ArrayQueue
{
public:
    ArrayQueue()
    {
        _container.resize(10);
    }

    void push(const T& value)
    {
        if (_size == _container.size())
        {
            // 증설 작업
            int newSize = std::max(1, _size * 2);    // size가 0인 경우 대처
            std::vector<T> newData;
            newData.resize(newSize);

            // 데이터 복사
            for (int i = 0; i < _size; i++)
            {
                int idx = (_front + i) % _container.size();
                newData[i] = _container[idx];
            }

            _container.swap(newData);
            _front = 0;
            _back = _size;
        }

        _container[_back] = value;
        _back = (_back + 1) % _container.size();
        _size++;
    }

    void pop()
    {
        _container[_front] = 0;
        _front = (_front + 1) % _container.size();
        _size--;
    }

    int front()
    {
        return _container[_front];
    }

    bool empty()
    {
        return _size == 0;
    }

    int size()
    {
        return _size;
    }

private:
    std::vector<T> _container;

    int _front = 0; // 첫 데이터가 들어가있는 위치(=index)
    int _back = 0;  // 다음 데이터가 들어갈 위치
    int _size = 0;  // 들어가 있는 데이터의 개수
};

int main()
{
    //std::queue<int> q;
    ArrayQueue<int> q;

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

    while (q.empty() == false)
    {
        int value = q.front();
        q.pop();
        std::cout << value << std::endl;
    }
}

---

 

 

================================

개인 공부 기록용 포스팅입니다.
댓글, 질문 환영해요~!

Refer : Inflearn_C++언리얼로 만드는...Part3
================================