[c++] stack, queue

http://www.cplusplus.com/reference/stack/stack/?kw=stack

stack - C++ Reference

Stack의 정의

template <class T, class Container = deque<T> > class stack;

 

stack은 Last-In-First-Out인 자료구조로 마지막에 들어온 것이 가장 먼저 나가는 자료구조입니다. (LIFO)

(여기서 deque은 vector의 단점을 보완하기 위해 만들어진 container로 배열기반의 구조입니다.

vector는 새로운 원소가 추가 될 때 메모리를 재할당하고 이전 원소를 복사하는 방식으로, 삽입 시에 성능이 저하되는 단점이 있는데, deque은 이를 보완하기 위해서 메모리가 부족할 때마다 일정한 크기의 새로운 메모리 블록을 할당합니다.)

 

Member functions

(constructor)	stack의 생성자
empty	현재 stack이 비어있는지 유무
size	현재 stack의 크기
top	현재 stack의 top element (next element)
push	element를 삽입
emplace	element를 생성 후 삽입
pop	top element를 제거
swap	두 stack의 element 교환

 

stack의 constructor을 살펴보자

// constructing stacks
#include <iostream>       // std::cout
#include <stack>          // std::stack
#include <vector>         // std::vector
#include <deque>          // std::deque

int main ()
{
  std::deque<int> mydeque (3,100);          // deque with 3 elements
  std::vector<int> myvector (2,200);        // vector with 2 elements

  std::stack<int> first;                    // empty stack
  std::stack<int> second (mydeque);         // stack initialized to copy of deque

  std::stack<int,std::vector<int> > third;  // empty stack using vector
  std::stack<int,std::vector<int> > fourth (myvector);

  std::cout << "size of first: " << first.size() << '\n';
  std::cout << "size of second: " << second.size() << '\n';
  std::cout << "size of third: " << third.size() << '\n';
  std::cout << "size of fourth: " << fourth.size() << '\n';

  return 0;
}

Output:

size of first: 0 size of second: 3 size of third: 0 size of fourth: 2

deque와 vector를 이용해서 stack을 생성하는 것과 빈 stack을 생성하는 모습을 볼 수 있습니다.

deque와 vector를 이용해서 생성할 때에는 괄호 안에 생성한 deque와 vecotr를 넣어주면 됩니다.

 

swap의 예를 보면

// stack::swap
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> foo,bar;
  foo.push (10); foo.push(20); foo.push(30);
  bar.push (111); bar.push(222);

  foo.swap(bar);

  std::cout << "size of foo: " << foo.size() << '\n';
  std::cout << "size of bar: " << bar.size() << '\n';

  return 0;
}

Output:

size of foo: 2 size of bar: 3

두 stack의 원소가 모두 바뀌는 것을 알 수 있습니다.

 

// swap stacks
#include <iostream>       // std::cout
#include <Stack>          // std::stack, std::swap(stack)

int main ()
{
  std::stack<int> foo,bar;
  foo.push (10); foo.push(20); foo.push(30);
  bar.push (111); bar.push(222);

  swap(foo,bar);

  std::cout << "size of foo: " << foo.size() << '\n';
  std::cout << "size of bar: " << bar.size() << '\n';

  return 0;
}

Output:

size of foo: 2 size of bar: 3

Non-member function 형식인데,

이런 식으로 파라미터에 두개의 stack을 넣어 바꿀 수도 있습니다.

 

---

 

http://www.cplusplus.com/reference/queue/queue/?kw=queue

queue - C++ Reference

queue의 정의

template <class T, class Container = deque<T> > class queue;

queue와 stack의 차이점은 queue는 FIFO의 형식이라는 것입니다.

FIFO: First-In-First-Out, 즉 가장 먼저 들어온 것이 가장 먼저 나가게 됩니다.

 

Member functions

(constructor)	queue의 생성자
empty	현재 queue가 비어있는지 유무
size	현재 queue의 크기
front	다음 element에 접근
back	마지막 element에 접근
push	element를 삽입
emplace	element를 생성 후 삽입
pop	다음 element를 삭제 (front)
swap	두 queue의 element를 교환

 

queue의 생성자를 살펴보면,

// constructing queues
#include <iostream>       // std::cout
#include <deque>          // std::deque
#include <list>           // std::list
#include <queue>          // std::queue

int main ()
{
  std::deque<int> mydeck (3,100);        // deque with 3 elements
  std::list<int> mylist (2,200);         // list with 2 elements

  std::queue<int> first;                 // empty queue
  std::queue<int> second (mydeck);       // queue initialized to copy of deque

  std::queue<int,std::list<int> > third; // empty queue with list as underlying container
  std::queue<int,std::list<int> > fourth (mylist);

  std::cout << "size of first: " << first.size() << '\n';
  std::cout << "size of second: " << second.size() << '\n';
  std::cout << "size of third: " << third.size() << '\n';
  std::cout << "size of fourth: " << fourth.size() << '\n';

  return 0;
}

Output:

size of first: 0 size of second: 3 size of third: 0 size of fourth: 2

(stack은 deque와 vector를 생성하여 사용한 예시였는데, queue는 deque와 list를 생성하여 사용한 예시를 사용하였습니다.

vector와 list의 차이는 java에서의 ArrayList와 Linked List의 차이이기 때문에, queue에서 front와 back에 접근하는 시간을 줄이기 위해서 list를 사용한 예시를 사용하였습니다.)

 

 

그만 까먹자.