c++ 벡터 이용 FIFO

int ,char : stack 메모리 할당

new :heap 메모리 할당

 

push_back()을 통해 벡터에 원소를 넣을 수 있다

맨 뒤에 원소를 추가하게 된다.

다 차게 되면 새로운 곳에 더 큰 공간을 할당받기 때문에 이 때는 O(n)의 시간 복잡도를 가진다.

아닐경우 원소를 추가하는 작업은 O(1)이다.

 

pop_back()을 통해 벡터의 제일 마지막에 있는 원소를 제거할 수 있다.

스택과 큐

#include <queue>를 쓴다

push_back() 대신 push()을 쓰고

pop_back() 대신 pop()을 쓴다.

pop()에서 큐(FIFO)는 제일 앞의 원소를 제거한다.

스택은 맨뒤의 원소를 제거한다.

벡터와 달리 []을 통한 원소의 접근이 불가능하고

큐는 front()을 통해 맨 앞의 원소를, back()을 통해 맨뒤의 원소를 접근할 수 있다.

int main(){
    deque<int> temp;

    temp.push_back(1);

    temp.push_back(2);

    temp.push_front(3);

    temp.push_front(4);

    int k = temp.size();

    for(int i=0;i<k;i++);

        cout << temp[i] << '\n';

    }

    return 0;

}

결과는 4 3 1 2 이다.

1,2 는 큐이므로, FIFO이다.

 

#include <stdio.h>
#include <iostream>
// vector를 사용하기 위해서는 추가한다.
#include <vector>
using namespace std;
// Stack 알고리즘은 FILO(First input Last output)의 성질을 가지고 있다.
// 즉, 가장 먼저 입력된 데이터가 가장 마지막에 나오는 자료구조이다.
template <typename T>
class Stack
{
private:
  // vector를 사용
  vector<T> v;
public:
  // 값을 넣기
  void push(T val)
  {
    v.push_back(val);
  }
  // 값을 빼기 (FILO 구조)
  T pop()
  {
    // 가장 마지막에 넣은 데이터를 취득
    T ret = v.back();
    // 가장 마지막 데이터를 삭제
    v.pop_back();
    // 결과 반환
    return ret;
  }
  // 데이터가 비어 있는 지 확인하는 함수
  bool empty()
  {
    return v.empty();
  }
};
// Queue 알고리즘은 FIFO(First input First output)의 성질을 가지고 있다.
// 즉, 가장 먼저 입력된 데이터가 가장 먼저 나오는 자료구조이다.
template <typename T>
class Queue 
{
private:
  // vector를 사용
  vector<T> v;
public:
  // 값을 넣기
  void push(T val)
  {
    v.push_back(val);
  }
  // 값을 빼기 (FIFO 구조)
  T pop()
  {
    // 가장 처음에 넣은 데이터를 취득
    T ret = v.front();
    // 맨 처음 데이터를 삭제
    v.erase(v.begin());
    // 결과 반환
    return ret;
  }
  // 데이터가 비어 있는 지 확인하는 함수
  bool empty()
  {
    return v.empty();
  }
};
// 실행 함수
int main()
{
  // Stack 알고리즘 선언
  Stack<const char*> stack;
  // 순서대로 입력..
  stack.push("Hello world");
  stack.push("good");
  // 콘솔 출력
  cout << "Stack Result " << endl;
  // stack이 전부 빌때까지 출력
  while (!stack.empty())
  {
    // 콘솔 출력... 입력된 반대로 순서로 출력
    cout << stack.pop() << endl;
  }
  // 개행 출력
  cout << endl;
  // Queue 알고리즘 선언
  Queue<const char*> queue;
  // 순서대로 입력..
  queue.push("Hello world");
  queue.push("good");
  // 콘솔 출력
  cout << "Queue Result " << endl;
  // stack이 전부 빌때까지 출력
  while (!queue.empty())
  {
    // 콘솔 출력... 입력된 순서로 출력
    cout << queue.pop() << endl;
  }
  // 개행 출력
  cout << endl;
 
  return 0;
}

출처: https://nowonbun.tistory.com/733 [명월 일지:티스토리]