[자료구조] 스택과 큐(C++)

스택(Stack)

스택은 LIFO(Last in First out)으로, 가장 마지막으로 추가된 데이터부터 출력되는 자료구조이다.

 

 

스택의 연산 직접 설계하기

push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다.
만약 스택에 들어있는 정수가 없는 경우에는 -1을 리턴한다.
size: 스택에 들어있는 정수의 개수를 리턴한다.
empty: 스택이 비어있으면 1, 아니면 0을 리턴한다.
top: 스택의 가장 위에 있는 정수를 리턴한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 리턴한다.

스택 직접 구현

#include<iostream>

using namespace std;

class Stack {
public:
	Stack() {
		length = 0;
	}
	void push(int x);
	int pop();
	int size();
	bool empty();
	int top();
private:
	int length;
	int ary[10001] = { 0 };
};

void Stack::push(int x)
{
	ary[length] = x;
	length++;
}
int Stack::pop()
{
	if (length == 0) {
		return -1;
	}
	else {
		length--;
		return ary[length];
	}
}
int Stack::size()
{
	return length;
}
bool Stack::empty()
{
	if (length == 0) {
		return true;
	}
	else {
		return false;
	}
}
int Stack::top()
{
	if (length == 0) {
		return -1;
	}
	else {
		return ary[length - 1];
	}
}

 

스택 구현 백준 문제

 

 

---

내장 라이브러리 stack 활용

#include<stack>
stack<자료형> stackname;

 

stack의 내장 함수다.

stackname.push(X); 		 데이터 추가
stackname.pop();		 데이터 제거
stackname.top();		 최상단의 데이터 반환
stackname.empty();		 스택이 비어있으면 True, 그렇지 않으면 False 반환
stackname.size();		 현재 스택에 있는 아이템의 수 반환
stackname.swap(otherstack);	 두 stack의 아이템들을 서로 바꿈

 

 

 

---

큐(Queue)

큐는 FIFO (First in, first out)으로, 제일 처음 추가된 데이터가 제일 먼저 출력되는 자료구조이다.

 

큐의 함수 직접 설계하기

empty: 큐가 비어있으면 1, 아니면 0을 리턴한다.
enqueue(X): X라는 아이템을 큐에 추가한다.
dequeue(&X): 큐의 제일 처음 들어왔던 아이템 X를 큐에서 없애고(실제로 직접 없애는 것보다 front를 한 칸 올리면 없어지는 식), X 아이템을 리턴한다.

 

큐 직접 구현

#include<iostream>
using namespace std;


struct item {
	int num;
};

class queue {
public:
	queue() {
	 maxQue = 100;
	 front = maxQue - 1;
	 rear = maxQue - 1;
	 item = new int[maxQue];
	}
	~queue() {
		delete[] item;
	}
	bool IsEmpty();
	void enqueue(int num);
	void dequeue(int& num);

private:
	int front, rear;
	int maxQue;
	int* item;
};

bool queue::IsEmpty()
{
	return (rear == front);
}


void queue::enqueue(int num) {
	rear = (rear + 1) % maxQue;
	item[rear] = num;
}

void queue::dequeue(int& num) {
	front = (front + 1) % maxQue;
	num = item[front];
}

큐는 위와 같이 동그란 형태라고 생각해야 한다. 큐를 한번 사용하고 나서 다시 비우더라도 시작점은 달라질 수 있기 때문이다.

 

front와 rear의 값이 같으면 원형 큐가 비어 있는 공백 상태이다. 

원형 큐에서는 하나의 자리는 항상 비워두어야 한다. 왜냐하면 포화 상태와 공백 상태를 구별하기 위해서이다. 
따라서 원형 큐에서 front == rear이 공백 상태가 되고 만약 front가 rear보다 하나 앞에 있으면 포화 상태가 된다.
만약 큐의 요소들의 개수를 따로 관리한다면 한자리를 비워두지 않아도 되지만 변수를 정확히 관리해야 하므로 프로그램이 복잡해질 수 있다.

---

내장 라이브러리 queue 활용

#include<queue>
queue<자료형> queuename;

queuename.push(X);		데이터 추가
queuename.pop();		맨 앞의 데이터 제거(제일 처음 들어온 데이터)
queuename.front();		맨 앞의 데이터 반환
queuename.back();		맨 뒤의 데이터 반환(제일 늦게 들어온 데이터임)
queuename.empty();		큐가 비어있으면 True, 그렇지 않으면 False
queuename.size();		큐에 들어있는 데이터의 수 반환
queuename.swap(otherqueue);	다른 큐와의 아이템을 서로 바꿈