[C++] 35. 자료구조 : 큐와 스택(Queue & Stack)

웃겨서 가져와보았습니다

이건 무슨 자료구조일까요? ㅋㅋ

---

*삭제연산이 수행되는 곳을 프론트(front, head, start)라고 부르고, 삽입연산이 이루어지는 곳은 리어(rear,tail,end)라고 부르도록 하자!!

*Queue의 경우 FIFO(First In First Out)구조로서 선입선출이라고 부른다.

*Queue는 프론트에서 이루어지는 삭제연산을 디큐(Dequeue)라고 부르며, 리어에서 이루어지는 삽입연산을 인큐(Enqueue)라고 부른다. 

*Stack은 "쌓다"라는 의미로, 데이터를 순서대로 차곡 차곡 쌓아올린 형태의 자료구조를 떠올리면 된다.

*Stack의 경우 LIFO(Last In First Out)구조로서 후입선출이라고 부른다.

*Stack은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능하다.

*Stack은 프론트에서 이루어지는 삭제연산을 팝(Pop)이라고 부르며, 리어에서 이루어지는 삽입연산을 푸시(Push)라고 부른다.

 

<Queue의 연산함수>
* Queue는 선입선출의 접근방법을 유지한다.
- IsEmpty() : 큐가 비어 있으면 true를 아니면 false를 반환한다.
- IsFull() : 큐가 가득 차 있으면 true를 아니면 false을 반환한다.
- Enqueue(int value) : 새로운 요소 value를 큐의 맨 뒤에 추가한다.
- Dequeque() : 큐가 비어 있지 않으면 맨 앞 요소를 삭제하고 반환한다.
- Peek() : 큐가 비어 있지 않으면 맨 앞 요소를 삭제하지 않고 반환한다.
- Size() : 큐의 모든 요소들의 개수를 반환한다.
- Show() : 큐의 모든 요소들을 출력한다.

 

***큐를 어디에 활용하는지에 대해 잠깐 얘기를 하자면,
- 프로세스 관리

- 은행업무

- 대기열 순서와 같은 우선순위의 작업예약
등 다양한 곳에 활용된다.

 

<Stack의 연산함수>
* Stack은 후입선출의 접근방법을 유지한다.
- IsEmpty() : 스택이 비어 있으면 true를 아니면 false를 반환한다.
- IsFull() : 스택이 가득 차 있으면 true를 아니면 false를 반환한다.
- Push(int value) : 주어진 요소 value를 스택의 맨 위에 추가한다.
- Pop() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다.
- Peek() : 스택이 비어있지 않으면 맨 위에 요소를 삭제하지 않고 반환한다.
- Size() : 스택 내의 모든 요소들의 개수를 반환한다.
- Show() : 스택 내의 모든 요소들을 출력한다.

***스택을 어디에 활용하는지에 대해 잠깐 얘기를 하자면,
- 웹 브라우저의 뒤로가기 버튼
- DFS(깊이 우선 탐색)
- 후위 연산자의 연산 (즉, 계산기)
- 중위 순회(연산) 등을 후위 순회(연산)으로 바꾸는 모듈
- 리커젼을 사용했을 때의 시스템 스택
등 다양한 곳에 활용된다.

---

큐(Queue)

사진을 참고하면 이해하기 쉽다

큐는 선입선출로, 쉽게 말해 줄서기를 떠올리면 된다. 줄을 설때 먼저 들어온 놈이 먼저 나가는 것은 당연한 이치다.

스택은 선입후출로, 쉽게 말해 접시쌓기를 떠올리면 된다. 접시를 쌓으면 먼저 쌓이는 접시는 가장 마지막에 빠진다.  

스택(Stack)

---

1. Node의 등장!!

#include <iostream>
#include <string>
#include <queue>

using namespace std;

class Node
{
public:
	int value;
	Node* next = nullptr;
};

void main()
{
	Node* nodePtrA = new Node();
	nodePtrA->value = 10;

	Node* nodePtrB = new Node();
	nodePtrB->value = 20;

	Node* nodePtrC = new Node();
	nodePtrC->value = 30;

	Node* nodePtrD = new Node();
	nodePtrD->value = 40;

	Node* nodePtrE = new Node();
	nodePtrE->value = 50;

	nodePtrA->next = nodePtrB;
	nodePtrB->next = nodePtrC;
	nodePtrC->next = nodePtrD;
	nodePtrD->next = nodePtrE;
	nodePtrE->next = nodePtrA;

	cout << nodePtrA->value << endl;
	cout << nodePtrA->next->value << endl;
	cout << nodePtrA->next->next->value << endl;
	cout << nodePtrA->next->next->next->value << endl;
	cout << nodePtrA->next->next->next->next->value << endl;
	cout << nodePtrA->next->next->next->next->next->value << endl;

	delete nodePtrA;
	delete nodePtrB;
	delete nodePtrC;
	delete nodePtrD;
	delete nodePtrE;
}

연산 과정

출력결과

---

2. 큐

#include <iostream>
#include <string>
#include <queue>

using namespace std;

class Node
{
public:
	int value;
	Node* next = nullptr;
};

void main()
{
	Node* start = nullptr;
	Node* end = nullptr;

	Node* nodePtrA = new Node();
	nodePtrA->value = 10;
	start = nodePtrA;
	end = nodePtrA;

	Node* nodePtrB = new Node();
	nodePtrB->value = 20;
	end->next = nodePtrB;
	end = nodePtrB;

	Node* nodePtrC = new Node();
	nodePtrC->value = 30;
	end->next = nodePtrC;
	end = nodePtrC;

	Node* nodePtrD = new Node();
	nodePtrD->value = 40;
	end->next = nodePtrD;
	end = nodePtrD;

	cout << "---큐 시작---" << endl;
	// 빼는거
	Node* temp = nullptr;
	temp = start;
	cout << start->value << endl;
	start = start->next;
	delete temp;		// A 삭제

	temp = start;
	cout << start->value << endl;
	start = start->next;
	delete temp;		// B 삭제

	temp = start;
	cout << start->value << endl;
	start = start->next;
	delete temp;		// C 삭제

	temp = start;
	cout << start->value << endl;
	start = start->next;
	delete temp;		// D 삭제

	cout << "---큐 끝---" << endl;
}

연산 과정

출력 결과

---