Seung's Learning Record

Queue 란? 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 먼저 들어간 원소가 먼저 나오게 되는 FIFO(First In First Out) 구조이다. 큐에서는 원소가 제거되는 쪽을 가장 앞인 front, 원소가 삽입되는 쪽을 가장 뒤인 rear라고 부른다. Queue 성질 원소의 추가 O(1) 원소의 제거 O(1) 맨 앞, 맨 뒤 원소 확인 O(1) 맨 앞, 맨 뒤를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능 Queue 구현 스택과 마찬가지로 큐 역시 배열을 이용하여 구현하는 방법과 STL을 이용하여 구현하는 방법이 있다. 배열을 사용한 구현 스택에서의 구현 방법을 큐에 대입해보자. 원소가 삽입되면 tail이 가르키는 인덱스에 값을 넣고 tail++를 하면된..

STACK 이란? 한쪽 끝에서만 원소를 삽입/삭제할 수 있는 자료구조이다. FILO(First In Last Out)구조로 가장 먼저 삽입된 원소가 가장 나중에 빠져나온다. 원소가 삭제되는 위치를 최상단, top이라고 부른다. STACK 성질 원소의 추가 O(1) 원소의 제거 O(1) 최상단의 원소 확인 O(1) 최상단의 원소를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능 STACK 구현 스택의 구현 방법에는 배열을 사용하여 구현하는 방법과 STL을 사용하는 방법이 있다. 배열을 사용한 구현 const int MX = 1000000; int dat[MX]; int pos = 0;//다음 원소가 삽입될 인덱스 정보 //원소 삽입 void push(int x){ dat[pos++] = x; } ..