스택
한 쪽에서만 데이터의 삽입과 삭제가 가능한 자료구조
한 쪽에서만 삽입, 삭제가 이루어지므로 LIFO(Last In First Out) 자료구조
push : 스택에 데이터를 저장하는 연산
pop : 데이터를 빼는 연산
최근에 저장한 데이터를 가장 먼저 활용해야 할 때(뒤로가기 기능 등) 사용
함수의 매개변수를 스택에 활용
int bar(int y)
{
return y + 2;
}
int foo(int x)
{
bar(2);
return x + 1;
}
foo(1);1. 매개변수 x가 1로 초기화
2. 매개변수 y가 2로 초기화
3. bar 함수가 4를 반환한 뒤 y가 메모리에서 삭제
4. foo가 2를 반환한 뒤 x가 메모리에서 삭제
큐
한쪽으로 데이터를 삽입하고, 다른 한 쪽으로 데이터를 삭제할 수 있는 자료구조
먼저 삽입된 데이터가 먼저 나오는 선입선출(FIFO, First In First Out) 자료구조
enqueue : 한 쪽 끝에 데이터를 삽입하는 연산
dequeue : 다른 한 쪽 끝으로 데이터를 빼는 연산
임시 저장된 데이터를 차례차례 내보내거나 꺼내 와야 하는 각종 버퍼로 활용
원형 큐(circular queue)
데이터를 삽입하는 쪽과 삭제하는 쪽을 하나로 연결해 원형으로 사용하는 자료구조
rear는 큐의 뒤, front는 큐의 앞
1. 리스트에 데이터를 삽입하면, rear는 1로 옮겨짐
2. 리스트에 데이터를 삽입하면, rear는 3로 옮겨짐
3. 리스트에서 데이터를 dequeue() 해주면, front가 1로 옮겨지며, 1에 저장되어 있는 데이터가 반환됨
만약 원형 큐에 데이터가 꽉 차면 더 이상 새로운 데이터를 넣지 못함
deque
double-ended queue의 약자로, 양쪽으로 데이터를 삽입/삭제할 수 있는 큐
priority queue
저장된 요소들이 선입선출로 처리되는 것이 아니라 정해진 우선순위가 높은 순으로 처리되는 큐
힙을 기반으로 구현됨