C++ 알고리즘:: 스택(Stack), 큐(Queue), 덱(Deque)

스택은 후입선출 (LIFO : Last In First Out)

큐 선입선출 (FIFO : First In First Out)

 

즉, 스택과 큐는 서로 반대되는 개념이다.

 

 

스택(Stack)

가장 마지막에 들어온 데이터가 가장 먼저 처리가 되는 자료구조이다.

입구와 출구가 하나 밖에 없는 상태이다.

 

스택 사용 방법

1. 스택 직접 구현

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x){
    dat[pos++] = x;
}

void pop(){
    pos--;
}

int top(){
    return dat[pos-1];
}

void test(){
  push(5); push(4); push(3);
  cout << top() << '\n'; // 3
  pop(); pop();
  cout << top() << '\n'; // 5
  push(10); push(12);
  cout << top() << '\n'; // 12
  pop();
  cout << top() << '\n'; // 10
}

int main(void) {
	test();
}

 

2. 스택 라이브러리 사용 : C++ STL Library

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

int main(){
    stack<int> s;
    s.push(7); //값을 넣는다
    s.push(4);
    s.push(5);
    s.pop();
    s.push(6);
    s.pop();
    while(!s.empty()){
        cout<<s.top()<<' ';
        s.pop();
    }
    return 0;
}

 

 

 

큐(Queue)

가장 먼저 들어온 것이 가장 먼저 나가는 자료구조이다. (ex. 은행창구)

 

큐 사용 방법

1. 큐 직접 구현

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x){
    dat[tail++] = x;
}

void pop(){
    head++;
}

int front(){
    return dat[head];
}

int back(){
    return dat[tail-1];
}

void test(){
  push(10); push(20); push(30);
  cout << front() << '\n'; // 10
  cout << back() << '\n'; // 30
  pop(); pop();
  push(15); push(25);
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 25
}

int main(void) {
  test();  
}

 

2. 큐 라이브러리 사용 : C++ STL Library

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

int main(){
    queue<int> q; // 정수형 데이터가 담길 수 있는 큐
    q.push(7); // 값을 넣는다
    q.push(5);
    q.push(4);
    q.pop(); // 가장 먼저 들어온 값을 빼낸다
    q.push(6);
    q.pop();
    while(!q.empty()){ //남아있는 데이터를 출력
        cout<<q.front()<<' '; // 맨 앞을 출력
        q.pop();
    }
    return 0;
}

 

 

 

덱(Deque: Double Ended Que)

양쪽 끝에서 삽입과 삭제가 가능한 자료구조.

 

덱의 성질

head는 가장 앞에 있는 원소의 인덱스, tail은 가장 뒤의 인덱스+1이다.

배열 내에서 실제 큐에는 오른쪽으로만 확장하는 것이고, 덱은 양쪽으로 확장해야한다.

따라서 시작지점을 배열의 중간에 두어야 한다. 배열의 크기는 2*max+1인 것이다.

vector와 유사한 느낌이다. 그러나 vector와 달리 모든 원소들이 연속하게 배치되어 있지는 않다는 것이 차이점이다.

앞쪽과 뒷쪽의 제거가 필요하다면 deque이 좋지만, 배열과 같은 느낌으로 쓰고 싶다면 vector를 사용하면 된다.

 

덱 사용 방법

1. 덱 직접 구현

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;

void push_front(int x){
    dat[--head] = x;
}

void push_back(int x){
    dat[tail++] = x;
}

void pop_front(int x){
    head++;
}

void pop_back(int x){
    tail--;
}

int front(){
   return dat[head]; 
}

int back(){
    return dat[tail-1];
}

void test(){
  push_back(30); // 30
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 30
  push_front(25); // 25 30
  push_back(12); // 25 30 12
  cout << back() << '\n'; // 12
  push_back(62); // 25 30 12 62
  pop_front(); // 30 12 62
  cout << front() << '\n'; // 30
  pop_front(); // 12 62
  cout << back() << '\n'; // 62
}

int main(void){
  test();
}

 

2. 덱 라이브러리 사용 : C++ STL Library

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

int main(){
    deque<int> dq; // 정수형 데이터가 담길 수 있는 큐
    dq.push_front(7); // 7
    dq.push_front(5); // 5 7
    dq.push_back(4); // 5 7 4
    dq.pop_front(); // 7 4
    dq.push_front(6); // 6 7 4
    dq.pop_back(); // 6 7
    while(!dq.empty()){ //남아있는 데이터를 출력
        cout<<dq.front()<<' '; // 6 // 7
        dq.pop_front();
    }
    return 0;
}

 

 

 

 

 

출처 :

https://www.youtube.com/watch?v=WB_BoAgWLNU&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=15 

https://www.youtube.com/watch?v=yAiZ1AVU8Aw&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=15 

https://www.youtube.com/watch?v=0mEzJ4S1d8o&t=243s 

https://velog.io/@choiiis/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue

[자료구조] 스택(Stack), 큐(Queue), 덱(Deque)