[c++] STL Queue , Stack 정리

Queue와 Stack이란 ?

Queue와 Stack은 자료구조의 대표적인 FIFO(First in First Out), LIFO(Last In First Out)알고리즘이다.

1. Queue와 Stack이란 ? 

Queue는 대표적인 FIFO 구조이다.즉 FIFO그대로 먼저 넣은데이터가 먼저 빠지는것으로 이해할 수 있다.

즉 데이터를 한쪽으로 넣고 반대쪽으로 데이터가 빠지는 구조로 볼 수 있다.

Queue 구조

Stack은 대표적인 LIFO구조로 먼저넣은데이터가 가장 마지막에 빠지는 자료구조이다.

상자에 데이터를 쌓고 최상위 데이터부터 뺴는것으로 생각하면 된다.

STACK 구조

1.Queue 헤더파일 

#include<queue>;

1.1 queue 생성 

queue<int> q;  기본 생성 방식

queue<int> q( {1,2,3,4,5,6} ) {}내의 데이터로 초기화된 queue 생성

2.Queue 기본 함수 

Queue의 기본함수는 기본적으로 시간복잡도가 O(1)이다.

데이터 추가	q.push(data);	queue<int >q에 data를 추가
데이터 삭제	q.pop()	q의 front 데이터 삭제
첫번째 데이터 반환	q.front()	q의 최상위 데이터 반환
마지막 데이터 반환	q.back()	q의 최하위 데이터 반환
큐 사이즈 반환	q.size()	q의 현재 사이즈 반환
큐가 비어있는지 확인	q.empty()	q가 비어있는지 확인
큐 내용 바꾸기	q.swap(q1,q2)	두 q1 q2의 데이터 스왑하기.

 

3. Queue의 특징

• FIFO 구조
• QUEUE는 한쪽끝을 Front로 정하고 삭제 연산만 수행
• 다른쪽은 rear로 정하고 삽입 연산만 수행
• 그래프 넓이 우선탐색에 사용
• 컴퓨터 버퍼에서 주로 사용, 큐를 만들어 대기하는 용도

---

 

1. Stack 헤더파일 

#include <stack>;

1.1 Stack 생성

stack<int> s; 기본 생성 방식

2.Stack 기본 함수 

데이터 추가	s.push(data)	stack<int> s에 data추가
데이터 삭제	s.pop()	s의 top데이터 삭제
최상위 데이터 반환	s.top()	s의 top데이터 반환
스택 사이즈 반환	s.size()	stack 사이즈 반환
스택 비어있는지 확인	s.empty()	stack이 비어있는지 확인
두 스택내용 바꾸기	s.swap(s1,s2)	두 s1, s2의 데이터 스왑하기

 

3. Stack의 특징

• LIFO 구조 
• 시스템 해킹시 버퍼오버플로우 취약점을 이용한 공격을 할때 스택 메모리 영역을 건듬
• 인터럽트 처리, 수식 계산, 서브루틴의 복귀 번지 저장등 사용
• 그래프 깊이 우선탐색에서 사용
• 재귀적 함수 호출시 사용