[자료구조] 2. Stack, Queue

[ 해당 글은 C++을 기준으로 작성했습니다. ]

Stack

Last In First Out (LIFO)
원소를 컨테이너의 한쪽 끝(스택의 top)에서만 꺼내거나 넣을 수 있다.

괄호 짝 맞추기를 할때 많이 사용했던 자료형. 중위식을 후위 표기법으로 변환할 때도 쓰인다.

 

Code

<예제 추가 예정>

 

Queue

First In First Out (FIFO)
원소를 컨테이너의 뒤(back)에 넣고, 앞(front)에서 꺼낸다.

BFS의 핵심이 되는 자료형

 

Code

<예제 추가 예정>

 

+ Stack 두 개로 Queue 구현해보기

스택 두 개를 이용해서 큐를 구현해 보았다.

큐는 다음과 같이 1 2 3 순서대로 넣으면 pop을 했을 때 1 2 3 순서대로 나와야 한다. 이를 입력을 받아들일 스택인  stack_for_input과 출력을 할 스택인 stack_for_output을 사용하여 구현해 보았다.

 

원소를 삽입하는 과정은 간단하게 이루어진다.

입력을 받는 스택인 stack_for_input에 원소를 하나씩 push하면 된다.

 

원소를 출력할 때의 과정은 다음과 같다.
먼저 출력 전용 스택인 stack_for_output에 원소가 있는지 살핀다. 원소가 있을 경우는 그냥 pop해주면 된다.

원소가 없을 때에는 input에서 pop할 원소들을 가져온다.
stack_for_input에서 하나씩 pop하고, pop한 순서대로 다시 stack_for_output에 넣는다.

그렇게 원소를 옮기면, 이제 stack_for_output에서 pop하면 된다.

 

Code

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

class QueueWithStack
{
	// stack 2개로 queue를 구현한 class입니다.
public:
	int FrontOfQueue() {
		// Queue의 앞(front)에 존재하는 원소를 print한다
		if (stack_for_output.empty()) {
			MoveElements();
		}

		return stack_for_output.top();
	}

	int SizeOfQueue() {
		// 큐의 사이즈를 출력한다.
		return stack_for_input.size() + stack_for_output.size();
	}

	bool QueueIsEmpty() {
		// 큐가 비었는지를 확인한다.
		if (stack_for_input.empty() && stack_for_output.empty()) {
			return true;
		}
		return false;
	}

	void PushToQueue(int value) {
		// 큐의 back에 원소를 넣는다.
		stack_for_input.push(value);
	}

	void PopFromQueue() {
		// 큐의 front에서 원소를 삭제한다.
		if (stack_for_output.empty()) {
			MoveElements();
		}

		stack_for_output.pop();
	}

private:
	stack<int> stack_for_input;
	stack<int> stack_for_output;

	void MoveElements() {
		// pop연산을 한다던가 할 때, output 스택이 비어 있으면 input에 있는 원소를 하나씩 꺼내서 pop할 수 있도록 옮겨줌
		while (!stack_for_input.empty())
		{
			stack_for_output.push(stack_for_input.top());
			stack_for_input.pop();
		}
	}
};

int main(void) {
	QueueWithStack test;
	test.PushToQueue(1);
	test.PushToQueue(2);
	test.PushToQueue(3);
	cout << test.FrontOfQueue();
	test.PopFromQueue();
	cout << test.FrontOfQueue();

	return 0;
}

C++로 구현한 코드이다.

QueueWithStack class를 만들어 내부 함수로 queue의 동작을 구현하였다.

 

 

해당 글은 다음 글들을 참고하여 작성했습니다.
https://www.cplusplus.com/reference/stack/stack/
https://www.cplusplus.com/reference/queue/queue/?kw=queue