스택

스택(stack)은 리스트의 일종으로 연산이 한 쪽 끝에서만 이뤄지는 자료구조 이다.

가장 나중에 들어간 것이 처음에 나온다고 해서 LIFO(Last-In First_Out)구조라고 한다.

스택의 끝을 위(Top)
스택의 시작을 밑(Bottom)

순서대로 vector, forward_list, list 이다

#include <stack> // std::stack을 위한 헤더
#include <iostream>
#include <vector>
#include <forward_list>
#include <list>

using namespace std;



int main()
{
    std::stack<int> s;


    std::vector<int> st;
    st.push_back(1);
    st.pop_back();


    std::forward_list<int> st2;
    st2.push_front(1);
    st2.pop_front();


    std::list<int> st3;
    st3.push_front(1); st3.push_back(2);
    st3.pop_front(); st3.pop_back();


    // 삽입
    for (int i = 1; i <= 5; ++i)
    {
        s.push(i); // push() : 스택에 데이터를 삽입한다.
    }
    // s { 5, 4, 3, 2, 1 }

    // 컨테이너 어댑터는 반복자가 존재하지 않는다.
    //  => 순회 용도로 사용하지 않기 때문이다.

    // 삭제
    s.pop(); // pop() : 스택의 위에서 값을 꺼낸다.
    // s { 4, 3, 2, 1 }

    // 읽기
    std::cout << "stack.top() : " << s.top() << "\n";
    // top() : 가장 마지막으로 삽입된 원소를 가져온다.

    // 크기
    if (s.empty())
    {
        std::cout << "stack is empty\n";
    }
    std::cout << "stack.size() : " << s.size() << "\n";
    // size() : 현재 원소의 개수를 반환한다.
}

큐

큐 : 순서를 구현해야 할 때 사용하면 좋다.

순차 자료구조로 큐를 구현한것이 원형큐 이다.
연결

삽입이 일어나는 쪽을 뒤(Rear)
삭제가 일어나는 쪽을 앞(Front)
라고 한다.

std::queue
std::deque

로 구현되어 있다.

deque == Double-ended Queue

앞 뒤 양쪽에서 삽입과 삭제를 할 수 있다.

std::deque 는 선형 리스트와 연결 리스트를 조합한 청크 리스트 이다.
고정된 길이의 배열을 이용한다.

청크 리스트 도식화

stack과 queue 는 기본적으로 deque를 사용한다.