C++ 스택과 큐

200원짜리개발자·2023년 6월 14일

C++자료구조

C++

목록 보기

9/39

강의 보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린 점이 있을 수 있음에 양해 부탁드립니다. (피드백 환영입니다)

우리가 앞에서 배웠던 동적배열(vector)와 연결리스트로 다양한 것을 선형의 데이터로 구현할 수 있었다.
하지만 선형 자료구조에는
Stack과 Queue라는 것이 더 있다.

그럼 Stack과 Queue에 대해 알아보자.

Stack

스택은 입구와 출구가 동일한 위치에 있다.
우리가 어떠한 데이터를 밀어넣을 때
스택은 입구에 먼저 들어간 쪽이 가장 늦게 나온다.
즉 후입선출(LIFO)라는 뜻이다 (Last In First Out)

이러한 구조를 가지고 있다.

우리가 설거지 할 때 가장 아래에 있는 접시(처음에 싱크대에 넣은 접시)를 마지막에 씻는 것과 비슷하다고 할 수 있다.

Stack으로 무엇을 만들 수 있을까? 생각을 해보면
UI를 끄는 순서를 정할 때? 사용할 수 있을 것 같다. (UI 팝업창)

Queue

큐는 입구와 출구가 일자로 되어있다.
우리가 어떠한 데이터를 밀어넣을 때
큐는 입구에 먼저 들어간 쪽이 먼저 나온다.
즉 선입선출(FIFO)라는 뜻이다 (First In First Out)

이러한 구조를 가지고 있다.

Queue로는 무엇을 만들 수 있을까? 생각을 해보면
대기열?정도 라고 볼 수 있다.

의문점

그럼 여기서 의문이 들 수 있다.
왜 Vector나 List로 다 구현할 수 있는데 왜 Stack이랑 Queue가 필요할까?라는 의문이 말이다.
여기에 대한 답변으로는
기능을 제한하여서 우리가 지금 사용하는 기능만 사용할 수 있게 해놓고 잘 못 다른 기능을 사용하지 못하게 하기 위해서 그런게 아닐까? 라는 답변아닌 답변을 할 수 있다.

Stack과 Queue구현에 관해

연결리스트로 Stack과 Queue를 구현한다면 상당히 간단하게 구현할 수 있다.
하지만 속도에서 연결리스트가 Vector보다 일반적으로 조금 느리다.
그래서 Vector로 Stack과 Queue를 구현해본다!라고 한다면 조금 애매해질 수 있다.

Stack같은 경우는 어차피 Vector가 뒤에 추가하고 뒤에서 빼주기 때문에 쉽게 구현할 수 있을 것이다.

#pragma once
#include "Vector.h"

template<typename T>
class Stack
{
public:

	void push(const T& value)
	{
		_container.push_back(value);
	}

	void pop()
	{
		_container.pop_back();
	}

	T& top()
	{
		return _container.back();
	}

	bool empty() { return size() > 0; }
	int size() { return _container.size(); }


private:
	Vector<T> _container;
};

이런식으로 말이다.
C++에서는 데이터를 꺼내감과 동시에 pop을 하는게 아니라 두 개로 나눠져있다. (메모리 관련해서 이유가 있는거 같다.)
그래서 top()을 사용해 데이터를 꺼내오고 pop을 사용하여 지울 수 있다.

하지만 Queue같은 경우는 List방식으로 만든다면 head와 tail이 있기때문에 쉽게 구현할 수 있지만 Vector같은 경우에는 애매하다.
하지만 Vector로 Queue를 구현할 수 있는 방법이 있다.
front랑 back이라는 변수로 관리할 수 있다.
데이터가 들어갈 때마다 back을 뒤로 넘겨주고
데이터를 뺄때마다 front를 back앞으로 옮겨준다면 Vector로도 구현을 할 수 있을 것이다.
그리고 만약 front나 back이 범위를 벗어났을 떄
다시 처음으로 돌아오기 위해서 나머지 연산으로 _container에 사이즈를 해주면 된다.
그리고 만약 값이 다 차면 늘려주는 코드를 작성해 주면 된다.(아직 안적었다.)
Vector의 reserve처럼 만들어 주면 된다.

#pragma once

#include "Vector.h"

template<typename T>
class Queue
{
public:
	Queue()
	{
		_container.resize(100);
	}

	void push(const T& value)
	{
		// TODO: 다 찼는지 체크
		if (_size == _container.size())
		{

		}

		_container[_back] = value;
		_back = (_back + 1) % _container.size();

		_size++;
	}

	void pop()
	{
		_front = (_front + 1) % _container.size();
		_size--;
	}

	T& front()
	{
		return _container[_front]
	}

	bool empty() { return _size == 0; }
	int size() { return _size; }
private:
	Vector<T> _container;

	int _front = 0;
	int _back = 0;
	int _size = 0;
};