스택 & 큐

 

Stack : 스택은 후입선출의 특성을 가지고 있는 자료구조로, 데이터 입력(푸쉬) 또는 제거(팝)할 때 항상 스택의 최상단(탑)에서만 이뤄진다는 특징이 있음.

 

Ex) 스마트폰 뒤로가기 버튼, 쌓여있는 책 또는 상자, 시스템 스택(함수 호출 시)

 

 

스택의 추상 자료형

• create() - 최대 크기를 size로 제한한 공백 스택 생성
• is_Full() - 스택이 꽉 찼는지 확인
• is_Empty() - 스택이 비어있는지 확인
• push() - 스택에 요소 추가
• pop() - 스택에 요소 제거
• peek() - 스택의 최상단 요소 반환

 

스택의 구현 방식 중 전역변수로 구현하는 경우, 배열과 top 변수를 함수의 매개 변수로 전달할 필요가 없으나,

하나의 프로그램 안에서 여러 개의 스택을 동시에 사용하기가 어렵다.

 

스택의 요소가 복잡한 구조를 갖는 경우엔 여러 개의 자료형들을 한꺼번에 다룰 수 있는 구조체가 스택의 요소라면 복잡한 구조를 효율적으로 관리할 수 있고, 자료형을 수정할 필요없이 구조체 안에 어떤 자료형이든 넣을 수 있기 때문에 편리하다.

 

스택을 함수의 매개변수로 전달하는 경우(여러 개의 스택), 구조체로 스택과 관련된 변수들을 그룹핑하여 여러 개의 스택을 쉽게 만드는 것이 가능해진다. 함수에는 구조체 포인터로 원본을 전달시켜 각 스택의 요소를 관리할 수 있다.

 

동적 배열 형식으로 스택을 구현한다면, 필요할 때마다 스택의 크기를 동적으로 늘릴 수 있다는 것이 장점이지만, 스택 사용이 끝난 후에는 메모리 낭비 방지를 위해 반드시 동적 메모리를 반환해야 한다.

 

다음은 C++ STL Stack 활용 예시이다.

 

#include <iostream>
#include <stack>
using namespace std;

int main() {
	stack<int> s;
	s.push(7);
	s.push(5);
	s.push(4);
	s.pop();
	s.push(6);
	s.pop();
	while(!s.empty()) {
		cout<<s.top()<<' ';
		s.pop();
	}
}

출력 결과 : 5 7

 

 

Queue : 선입선출의 특성을 갖고 있는 자료구조로써, 큐의 삽입은 큐의 뒤인 rear(back)에서 발생되고 삭제는 front라 불리는 앞에서 이뤄짐.

 

큐의 추상 자료형

• create() : 최대 크기가 max인 공백 큐 생성
• init() : 큐 초기화
• is_empty() : 큐가 비어있는지 체크
• is_full() : 큐가 꽉 찼는지 체크
• enqueue() : 큐 끝에 데이터 삽입
• dequeue() : 큐 맨 앞에 데이터 삭제
• peek() : 큐 맨 앞에 데이터 반환

 

선형 큐의 경우 front, rear 값이 증가만 하기 때문에 배열의 앞부분이 비어 있을 때 사용하질 못한다는 단점이 있다.

사용한다 해도 삭제가 일어날 때 모든 요소들을 왼쪽으로 이동시켜야 하는 번거로움이 있다.

 

다음은 C++ STL Queue 활용 예시이다. 

#include <iostream>
#include <queue>
using namespace std;

int main() {
	queue<int> q;
	q.push(7);
	q.push(5);
	q.push(4);
	q.pop();
	q.push(6);
	q.pop();
	while(!q.empty()) {
		cout<<q.front()<<' ';
		q.pop();
	}
}

출력 결과: 4 6

 

queue 라이브러리에서의 push와 pop은 enqueue, dequeue와 같다고 볼 수 있다.