자료구조 스터디 1주차_ 스택,큐,덱(deque) 구현하기

https://chisel-chocolate-566.notion.site/1-Stack-queue-deque-1a26a793da6280659ce8ffee14b37368

1주차 스택,큐,덱 발표 <담당자: 정재훈>

 

덱은  double ended que

양 끝에서 삽입 삭제가 가능한 구조 이다.

원소의 추가, 제거, 맨 앞/뒤 원소확인시 O(1)의 시간복잡도를 가진다.

맨앞/뒤 외의 자료구조는 확인이 불가하다.

배열로 구현한 덱, 연결리스트로 구현한 덱, 원형 리스트로 구현한 덱 등이 있다. 

연결리스트를 이용한 구현은 다음 주차때 연결리스트를 배우고 하려고 한다.

 

따라서 이번에는 가장 난이도가 쉬운 배열로 덱의 삽입,삭제 기능을 구현해봤다.

 

작성코드

#include <iostream>
using namespace std;

//덱은 시작지점을 배열의 중간에 둬야한다.
const int MX = 5;
int deq[2 * MX + 1];
int head = MX, tail = MX;

bool isEmpty();

// push_front, push_back : 앞 or 뒤에 데이터 추가하기.
void push_front(int x){
	if (head > 0) {
		deq[--head] = x;
	}
	else {
		cout << "front에서 오버플로우\n";
	}
}
void push_back(int x){
	if (tail < 2 * MX + 1) {
		deq[tail++] = x;
	}
	else {
		cout << "back에서 오버플로우\n";
	}
}
// pop_front, pop_back: 앞 or 뒤에 데이터 삭제하기.
void pop_front(){
	if (head < tail) {
		head++;  
	}
	else {
		cout << "덱이 비어있습니다.\n";
	}
}
void pop_back(){
	if (head < tail) {
		tail--; 
	}
	else {
		cout << "덱이 비어있습니다.\n";
	}
	
}
// front(), back() : 앞 or 뒤의 데이터를 반환한다.
int front(){
	if (!isEmpty()) {
		return deq[head];
	}
	else {
		cout << "덱이 비어있습니다.\n";
		return -1;
		//만약에 덱에 -1을 넣었다면 데이터가 있어도 -1을 반환할수있다. 
		//stl deque에서는 자동으로 예외처리를 해줌
	}
}
int back(){
	if (!isEmpty()) {
		return deq[tail - 1];
	}
	else {
		cout << "덱이 비어있습니다.\n";
		return -1;
	}
}
// empty() 덱이 비었는지 확인 , 비면 true  
bool isEmpty(){
	return head == tail;
}
// 덱의 전체 요소의 개수 반환
int size(){
	return tail - head;
}
//head와 tail을 중앙으로 재설정하여 초기화, head ~ tail 사이의 구간만 유효한 요소로 간주
//이전값들은 메모리 상에 그대로 존재하지만 덱의 동작에서는 무시됨 "사라진것처럼 동작"
void clear(){
	head = tail = MX;
}

void test() {
	push_front(3); // 덱: 3
	push_front(2); // 덱: 2 3
	push_front(1); // 덱: 1 2 3
	push_back(4);  // 덱: 1 2 3 4
	pop_back();    // 덱: 1 2 3
	pop_front();   // 덱: 2 3

	cout << "Front: " << front() << "\n"; // 출력: 2
	cout << "Back: " << back() << "\n";   // 출력: 3

	clear(); // 덱 초기화

	if (isEmpty())
		cout << "clear이후 덱은 비어있습니다.\n";
}

int main() {
	test();
	return 0;
}

 

문제 1.

push 할때 오버플로우, pop할때 언더플로우 예외처리가 필요

해결: head >0  tail < 배열의 크기 일때 push
head < tail 일때  pop, 

문제 2.
clear 할때  0으로 초기화 했음

해결: head와 tail을 중앙으로 재설정 하여 초기화
head ~ tail 사이의 구간만 유효한 요소로 간주
이전값들은 메모리 상에 그대로 존재하지만 덱의 동작에서는 무시됨 "사라진것처럼 동작"

문제 3.
덱이 비었음을 알릴때 return -1을 하면 문제가 생김
덱에 들어있는 -1 을 back하면 덱이 비지않아도 -1을 return 함

해결: 
방법1 ) stl::deque 사용시 내부적으로 처리해줌
방법2) int 대신 bool 반환 

 

수정 코드

#include <iostream>
using namespace std;

const int MX = 10;
int deque[2 * MX + 1];
int head = MX, tail = MX;

bool isEmpty();

void push_front(int x){
	if (head > 0) {
		deque[--head] = x;
	}
	else {
		cout << "front에서 오버플로우\n";
	}
}
void push_back(int x){
	if (tail < 2 * MX + 1) {
		deque[tail++] = x;
	}
	else {
		cout << "back에서 오버플로우\n";
	}
}
void pop_front(){
	if (head < tail) {
		head++;
	}
	else {
		cout << "덱이 비어있습니다.\n";
	}
}
void pop_back(){
	if (head < tail) {
		tail--;
	}
	else {
		cout << "덱이 비어있습니다.\n";
	}
}
int front(){
	return deque[head];
}
int back(){
	return deque[tail - 1];
}
bool isEmpty(){
	return head == tail;
}
int size(){
	return tail - head;
}
void clear(){
	head = tail = MX;
}
void test(){
	push_front(1); // 덱: [1]
    push_back(4);  // 덱: [1, 4]
    push_front(2); // 덱: [2, 1, 4]
    push_back(3);  // 덱: [2, 1, 4, 3]
    cout << "Size: " << size() << endl;  // 기대 출력: 4
    cout << front() << endl; // 기대 출력: 2
    cout << back() << endl;  // 기대 출력: 3
    pop_front();   // 덱: [1, 4, 3]
    pop_back();    // 덱: [1, 4]
    cout << "Size after pop: " << size() << endl;  // 기대 출력: 2
    cout << front() << endl; // 기대 출력: 1
    cout << back() << endl;  // 기대 출력: 4
    clear();
    if (!(isEmpty()))
        clear();
    else
        cout << "덱이 비었습니다\n";
}
int main() {
	test();

	return 0;
}

 

stl::queue 를 사용한 예제

 

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

int main() {
	deque<int> dq;

	dq.push_front(3);
	dq.push_front(2);
	dq.push_front(4);
	dq.push_front(13);

	cout << "Front: " << dq.front() << "\n";
	cout << "Back: " << dq.back() << "\n";

	dq.pop_front();
	dq.pop_back();

	cout << "Front: " << dq.front() << "\n";
	cout << "Back: " << dq.back() << "\n";
}

 

stl 덱의 장점:  가장 빠르고 쉽게 구현이 가능하다. 동적으로 크기조절이 가능하다. 언더플로우, 오버플로우를 내부적으로 처리해준다. 앞 뒤에서 O(1)의 시간복잡도로 삽입,삭제가 가능하다.