[자료구조] 스택과 큐

sangjun

·

2021. 4. 12. 19:14

반응형

먼저 스택과 큐를 C++를 이용해서 쉽게 구현하기 위해서는 템플릿 함수에 대해서

알고 넘어가야 한다.

 

템플릿 함수에 대해 간략히 소개해보겠다.

 

템플릿(Template) 함수란

템플릿 함수란 함수의 return형과 인자형을 int, float, double, char ...등등 여러가지 형으로

자유자재로 변환할 수 있다.

이것을 이용하면 C언어에서 같은 기능을 하지만 return형이 다른 함수들을 여러개 작성할 필요가 없다.

template <class T>
void SelectionSort(T *a, const int n){
	for (int i=0;i<n;i++){
    	int j=i;
        for(int k=i+1;k<n;k++)
        	if(a[k]<a[j]) j=k;
        swap(a[k],a[j]);
}

 

위와 같이 선택정렬의 인자를 T로 선언해주면 어떤 자료형의 배열이 와도 정렬을 완성할 수 있다.

 

Template를 이용하여 어떤 자료형이던 담을 수 있는 Bag을 구현해보도록 하겠다.

template <class T>
class Bag{
public:
	Bag(int bagCapacity=10); //생성자
    ~Bag();			//소멸자
    
    int Size() const;
    bool isEmpty() const;
    T& Element() const;
    
    void Push(const T&);
    void Pop();
private:
	T *array;
    int capacity;
    int top;
}

위에 코드에서 개인적으로 궁금한게 있다.

1. void Push(const T&);에서 템플릿 자료형은 왜 변수 이름 뒤에 &가 붙는지 궁금하다.

2. int Size() const;이렇게 함수 뒤에 const형이 붙으면 어떤 의미인지 궁금하다.

 

 

스택(Stack)이란

Top이라고 하는 한쪽 끝에서 모든 삽입(push)와 삭제(pop)이 일어나는 순서  리스트이다.

후입선출(LIFO)구조 라고도 불린다.

출처 : https://dev.to/theoutlander/implementing-the-stack-data-structure-in-javascript-4164

 

스택은 추상자료형으로 C++로 구현하면 배열, Push, Pop, Peek함수를 만들어 구현할 수 있다.

스택은 재귀함수, 시스템 스택 등 컴퓨터 과학 전반에 걸쳐서 많이 쓰는 자료형이니 꼭 알아둬야 할 자료구조이다.

 

아래는 스택 자료구조를 C++을 이용한 구현중 일부를 발췌한 부분이다.

private:
	T *stack;
    int top;
    int capacity;
template <class T>
Stack<T>::Stack(int stackCapacity): capacity(stackCapacity)
{
	if(capacity<1) throw "Stack capacity must be > 0";
    stack = new T[capacity];
    top = -1;
}

 

 

큐(Queue)란

큐는 일반적인 선착순 대기줄이라고 보면 된다.

남자들이 많이 하는 롤에서 게임을 잡기 위해 큐를 돌린다는 표현이 있다.

여기서 큐는 먼저 게임을 찾기 시작한 사람이 먼저 게임에 배정되는 것이다.

 

이 큐를 이용해 운영체제 단에서 쓰레드의 우선순위 할당할 때도 쓰이고 

여러가지 상황에 효과적으로 쓰일 수 있는 자료 구조라서 필수적으로 알아둬야 한다.

 

리어(read), 프론트(front)로 이루어져 있고 선입선출(FIFO)구조라고도 불린다.

 

큐를 구현하는 방법에는 배열을 이용해 선형 큐와 원형 큐가 있다.

출처 : https://medium.com/@jinseok.choi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90-queue-575fd41bae21

위의 그림은 선형큐이다. 선형큐의 장점은 구현이 편하다는 장점이 있지만

자료형의 추가, 삭제 과정에서 소요되는 오버헤드가 있다.

왜냐하면 데이터 하나가 빠질 때마다 배열의 첫번 째 인덱스에 데이터가 있도록 모든 데이터 움직여야 하기 때문이다.

 

 

이를 보완하기 위해 원형 큐가 많이 채택된다.

아래는 C++로 큐를 구현한 내용 일부이다.

 

push 시에 //rear = (rear+1) % capacity를 이용해 rear를 움직인다.

private:
	T *queue;
    int front,
    	rear,
        capacity;
      
template <class T>
Queue<T>::Queue(int queueCapacity): capacity(queueCapacity){
	if(capacity < 1) throw "Queue capacity must be > 0";
    queue = new T[capacity];
    front=rear=0;
}

 

template <class T>
inline bool Queue<T>::IsEmpty(){	return front==rear;	}

template <class T>
inline T& Queue<T>::Front(){
	if(IsEmpty())	throw "Queue is empty";
    return Queue[(front+1)%capacity];
}

template <class T>
inline T& Queue<T>::Rear(){
	if(IsEmpty())	throw "Queue is Empty";
    return queue[rear];
}
template <class T>
void Queue<T>::Pop()
{
	if(IsEmpty()) throw "Queue is empty";
    front = (front+1) % capacity;
    queue[front].~T();
}
반응형

'프로그래밍' 카테고리의 다른 글

[Network] NAT란  (0) 2021.07.08
[ncurses] linux ui library  (0) 2021.05.16
[JAVA] 접근 지정자  (0) 2021.05.15
[C++] 복사 생성자, 깊은 복사와 얕은 복사  (0) 2021.04.14
[JAVA] Scanner Class 사용법  (1) 2021.04.10

0개의 댓글