Stacks Using Dynamic Arrays

Stacks using dynamic arrays: array doubling

• When stack is full, double the capacity using realloc. It's called array doubling.

문제 1.

Stacks using dynamic arrays 를 구현하라. Stack 의 capacity(stack 의 size)는 초기값이 1 로
주어지며, stack 에 저장되는 원소의 개수가 capacity 보다 커지면 stack 의 capacity 를 2 배로 증가시킨다.
반대로 만약 stack 에서 원소가 pop 되어 capacity 가 현재 상태보다 반으로 줄어들 수 있으면 capacity 를
1/2 로 줄이도록 한다. 그러나, stack capacity 는 최소 1 이 되도록 유지한다. Stack 은 integer array 를
이용하여 구현한다.

Requirement:

• 1. File (in.txt)로 stack 에 대해 push, pop 할 원소들을 입력 받으며, 입력 파일의 형식은 다음과 같다.
     S0 S1 S2 …. Sn-1
     • 가정
       A. 각 Si (0 <= i < n, 1 <= n <= 100)는 ‘a x’ (x 는 양의 정수) 또는 ‘d’로 구성된다.
       B. Si가 ‘a x’일 때는 stack 에 x 를 push 한다.
       C. Si가 ‘d’이면 stack 에서 원소를 pop 한다.
• 2. top 의 초기값은 -1 이다.
• 3. 최종 결과는 화면에 출력한다. 입력 파일에 의해 push/pop 을 모두 수행한 후 최종 stack 의 상태를
     stack 의 bottom 부터 top 까지 차례대로 출력한다. 출력되는 각 숫자는 space 로 구분한다.
• 4. Stack 이 empty 인 상태에서 pop 을 수행하면 무시하고 수행을 계속한다.

문제 2.

문제 1 과 동일한 입력 파일에 대해 circular queue 를 구현하라. 단, circular queue 는 size 가
5 인 integer array 로 구성한다.

Requirement:

• 1. File (in.txt)로 queue 에 대한 add, delete 원소들을 다음과 같은 형식으로 입력 받는다.
     S0 S1 S2 …. Sn-1
     • 가정
       A. 각 Si (0 <= i < n, 1 <= n <= 100)는 ‘a x’ (x 는 양의 정수) 또는 ‘d’로 구성된다.
       B. Si가 ‘a x’일 때는 queue 에 x 를 add 한다.
       C. Si가 ‘d’이면 queue 에서 원소를 delete 한다.
• 2. front, rear 의 초기값은 0 이다.
• 3. 최종 결과는 화면에 출력한다. 입력 파일에 의해 add/delete 를 모두 수행한 후 최종 queue 의
     상태를 처음부터 끝까지 차례대로 출력한다. 출력되는 각 숫자는 space 로 구분한다.
• 4. Queue 가 empty 인 상태에서 delete 를 수행하면 무시하고 수행을 계속한다.
• 5. Queue 가 full 인 상태에서 add 를 수행하면 ‘queue full’을 출력한 뒤, 현재 queue의 내용을
     처음부터 끝까지 출력하고 수행을 끝낸다.

#include <iostream>
#include <string>
#include <format>
#include <fstream>
#include <cstdlib>

using namespace std;

typedef struct{
	int key;
}element;

element* stack;
int capacity = 1;
int top = -1;
int stackSize;
void StackFull() {
	stack = (element*)realloc(stack, 2 * capacity * sizeof(*stack));
 	capacity *= 2;
}
element StackEmpty() {
	exit(EXIT_FAILURE);
}
element pop() {
	if (top == -1)
		return StackEmpty();
	return stack[top--];
}
void push(int item) { 
	if (top >= capacity - 1)
		StackFull();
	stack[++top].key = item;
}
// 스택 반으로 줄이기
// if (capacity / 2 == top + 1)

void StackCutHalf() {
	if (capacity / 2 == top + 1) {
		stack = (element*)realloc(stack, capacity / 2 * sizeof(*stack));
		capacity /= 2;
	}
}
void P1() {
	string c;
	stack = (element*)malloc(sizeof(element) * capacity);
	fstream in("in.txt");
	while (!in.eof()) { //eof 전까지 반복수행 a 1 0 이렇게 들어감
		in >> c;
		if (c == "a") {
			in >> c;
			if (top == capacity - 1) {
				StackFull();
			}
			int c2 = stoi(c); //str에서 int로 형변환
			push(c2);
		}
		else if (c == "d") {
			pop();
			StackCutHalf();
		}
	}
	for (int i = 0; i <= top; i++) {
		printf("%d ", stack[i].key);
	}
}

int cq[5]; string q; int front = 0; int rear = 0;

void add(string a) {
	if (front - (rear + 1) % 5 == 1) 
	{
		cq[rear] = stoi(a);
		printf("queue full ");
		for (int i = front; i <= rear; i++) {
			printf("%d ", cq[i]);
		}
		exit(EXIT_FAILURE);
	}
	if (rear > 5) {
		rear = (rear + 1) / 6;
	}
	cq[rear++] = stoi(a);
}
int del() {
	return cq[front++]; //FIFO
}
void P2() { //front, rear 초깃값 0
	fstream in("in.txt");
	while (!in.eof()) { // a 10 a 2 a 9 d d a 5
		in >> q;
		if (q == "a") {
			in >> q;
			add(q);			}
		if (q == "d") 
		{
			if (front == 0 && rear == 0) {
			}
			else {
				del();
			}
		}
	}
	for (int i = front; i < rear; i++) {
		printf("%d ", cq[i]);
	} // 9 5
}
int main() {
	printf("문제 1: "); P1();
	printf("\n문제 2: "); P2();
}

(in.txt)
a 10 a 2 a 9 d d a 5
(화면 출력)
문제 1: 10 5
문제 2: 9 5

(in.txt)
d a 2 a 19 a 5 a 70 d d a 8
(화면 출력)
문제 1: 2 19 8
문제 2: 5 70 8

(in.txt)
a 1 a 9 d a 9 a 8 a 7 a 6 d
(화면 출력)
문제 1: 1 9 8 7
문제 2: queue full 9 9 8 7