[자료구조] 스택(Stack)과 큐(Queue)

스택(Stack)에 대해 설명하고 예제소스를 구현해보아라

• 후입선출(LIFO : Last In Fisrt Out) 방식의 자료구조
• 후입선출이란 나중에 들어간 것이 먼저 나온다는 뜻이다. 
• 배열 정수형 스택 예제
• isFull() : 스택이 가득차있는지 확인하는 함수
• isEmpty() : 스택이 비워져있는지 확인하는 함수
• push(int data) : 스택에 자료를 넣는 함수
• pop() : 스택에 있는 자료를 빼는 함수

#include <iostream>
#include <stdio.h>
#define MAX_SIZE 100

class stack
{
private:
	int nArray[MAX_SIZE];
	int index;

public:
	stack();
	bool isFull();
	bool isEmpty();
	void push(int data);
	int pop();
};

stack::stack()
{
	index = -1;
}

bool stack::isEmpty()
{
	if (index <= -1) return true;
	else			 return false;
}

bool stack::isFull()
{
	if (index >= MAX_SIZE-1) return true;
	else					 return false;

}

void stack::push(int data)
{
	if (isFull()) 
	{
		printf("꽉 찼습니다");
		return;
	}
	nArray[++index] = data;
}

int stack::pop()
{
	if (isEmpty())
	{
		printf("스택이 비었습니다");
		return -1;
	}
	return nArray[index--];
}

int main()
{
	stack st;
	int input;

	scanf_s("%d", &input);
	st.push(input);

	printf("%d", st.pop());

	return 0;
}

---

큐(Queue)에 대해 설명하고 예제소스를 구현해보아라

• 선입선출(FIFO : First In Fisrt Out) 방식의 자료구조
• 선입선출이란 먼저 들어간 것이 먼저 나온다는 뜻이다. (ex : 화장실 줄을 생각해보자)
• 원형큐(Circular Queue)예제
• 앞당김 작업 없이 지속적인 큐의 사용을 위해 사용
• isFull() : 큐에 가득차있는지 확인하는 함수
• isEmpty() : 큐가 비워져있는지 확인하는 함수
• enqueue(int data) : 큐에 자료를 넣는 함수
• dequeue() : 큐에 있는 자료를 빼는 함수

#include <iostream>
#include <stdio.h>
# define MAX_SIZE 5

class Queue
{
private:
	int nArray[MAX_SIZE];
	int index_front;
	int index_back;

public:
	Queue();

	bool isEmpty();
	bool isFull();
	void enqueue(int data);
	int dequeue();

};

Queue::Queue()
{
	index_front = 0;
	index_back = 0;
}

bool Queue::isEmpty()
{
	if (index_front == index_back)  return true;
	else				return false;
}

bool Queue::isFull()
{
	if ((index_back + 1)%MAX_SIZE == index_front)    return true;
	else	 					 return false;
}

void Queue::enqueue(int data)
{
	if (isFull())
	{
		printf("큐 FULL\n");
		return;
	}

	index_back = (index_back + 1) % MAX_SIZE;
	nArray[index_back] = data;

	return;
}

int Queue::dequeue()
{
	if (isEmpty()) 
	{
		printf("큐 Empty\n");
		return -1;
	}

	index_front = (index_front + 1) % MAX_SIZE;
	return nArray[index_front];
}

int main()
{
	Queue tq;
	for (int i = 1; i < 6; i++)
	{
		tq.enqueue(i);
	}

	printf("pop 한번 %d\n", tq.dequeue());
	tq.enqueue(11);

	while (!tq.isEmpty())
	{
		printf("%d\n", tq.dequeue());
	}

	printf("%d\n", tq.isFull());
	printf("%d\n", tq.isEmpty());

	return 0;
}