init 1주차 과제 - 스택과 큐

1. 과제 내용

백준 스택 & 큐 10828, 10845번 문제 (기초)
사용 언어 : C++

2. 스택

• 10828번
  • 문제
  • 내가 푼 코드

#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;

#define MAX_STACK_SIZE 10000
int stack[MAX_STACK_SIZE];
int top = -1;

int is_empty_() {
	return (top == -1);
}

int is_full() {
	return (top == MAX_STACK_SIZE - 1);
}

void push(int e) {
	if (is_full()) {
		return;
	}
	else {
		stack[++top] = e;
	}
}

int size() { // 스택에 들어 있는 정수 개수 출력
	return top + 1;
}

int pop() {
	if (is_empty_()) return -1;
	else return stack[top--];
}

int top_() { // 스택의 가장 위에 있는 정수 출력
	if (is_empty_()) return -1;
	else return stack[top];
}

int main() {
	int num;
	scanf("%d \n", &num);

	for (int i = 0; i < num; i++) {
		string str;
		cin >> str;

		if (str == "push") {
			int n;
			scanf("%d \n", &n);
			push(n);
		}
		else if (str == "pop") {
			printf("%d\n", pop());
		}
		else if (str == "size") {
			printf("%d\n", size());
		}
		else if (str == "empty") {
			printf("%d\n", is_empty_());
		}
		else if (str == "top") {
			printf("%d\n", top_());
		}
	}

	return 0;
}

• size() 함수 : top은 인덱스 번호를 가리키기 때문에 실제 개수보다 -1이다. 따라서 스택에 들어있는 개수를 구하려면 top + 1을 해야 한다.

3. 큐

• 10845번
  • 문제
  • 내가 푼 코드

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

#define MAX_QUEUE_SIZE 10001

typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front, rear;
	int num; // 큐에 들어있는 요소의 개수
} QueueType;

QueueType q;

int is_full(QueueType* q) {
	return q->num >= MAX_QUEUE_SIZE;
}

int is_empty_(QueueType* q) {
	return q->num <= 0;
}

void push(QueueType* q, element item) { // enqueue
	if (is_full(q)) return;
	else {
		q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
		q->data[q->rear] = item;
		q->num++;
	}
}

int pop(QueueType* q) {             // dequeue
	if (is_empty_(q)) return -1;
	else {
		q->front = (q->front + 1) % MAX_QUEUE_SIZE;
		q->num--;
		return q->data[q->front];
	}
}

int size(QueueType* q) {
	return q->num;
}

int front(QueueType* q) {
	if (is_empty_(q)) return -1;
	else {
		return q->data[q->front + 1];
	}
}

int back(QueueType* q) {
	if (is_empty_(q)) return -1;
	else {
		return q->data[q->rear];
	}
}

int main() {
	int n;
	scanf("%d\n", &n);

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		
		if (str == "push") {
			int number;
			scanf("%d\n", &number);
			push(&q, number);
		}
		else if (str == "pop") {
			printf("%d\n", pop(&q));
		}
		else if (str == "size") {
			printf("%d\n", size(&q));
		}
		else if (str == "empty") {
			printf("%d\n", is_empty_(&q));
		}
		else if (str == "front") {
			printf("%d\n", front(&q));
		}
		else if (str == "back") {
			printf("%d\n", back(&q));
		}
	}
	return 0;
}

• QueueType 구조체에서 num : is_full() 메서드에서 큐가 꽉 찼는지를 확인하기 위해 큐에 들어 있는 요소의 개수를 나타내는 변수를 하나 생성했다.
• 큐에서 front와 rear의 위치
  front가 (첫번째 인덱스)를 가리키고
  rear가 (마지막 인덱스 + 1) 인덱스를 가리킬 수도 있고,
  front가 (첫번째 인덱스 + 1) 인덱스를 가리키고
  rear가 (마지막 인덱스) 인덱스를 가리킬 수도 있다.
  전체적으로 어떻게 진행하고 있는지를 잘 파악해야 할 것 같다. 다른 책을 참고하면서 풀었는데, 그 책에서는 rear를 +1 했고, init의 지난주 ppt 코드에서는 front를 +1 해서 처음에 무심코 코드를 짜다가 약간 혼동이 있었다. 잘 파악하면서 코드를 구현하자!
  
  이 코드에서는
  front가 (첫번째 인덱스 + 1) 인덱스를 가리키고
  rear가 (마지막 인덱스) 인덱스를 가리키는 경우로 구현했다.

front(QueueType* q) 메서드에서는 q->data[q->front + 1]를 반환
back(QueueType* q) 메서드에서는 q->data[q->rear]를 반환

4. 백준 결과 화면

C++ 문법 때문에 틀린 경우가 약간 있고 여러 글을 참고하면서 풀긴 했지만 성공했다!:)