스택과 큐와 덱

1. 스택
   

   후입선출 (LIFO, Last In First Out)

#include <cstdio>
#include <cstdlib>
inline void error(char* message) {
	printf("%s\n", message);
	exit(1);
}
const int MAX_STACK_SIZE = 20;
class ArrayStack {
	int top;
	int data[MAX_STACK_SIZE];
public:
	ArrayStack() { top = -1; }
	~ArrayStack() {}
	bool isEmpty() { return top == -1; }
	bool isFull() { return top == MAX_STACK_SIZE; }

	void push(int e) {
		if (isFull()) error("스택 포화 에러");
		data[top++] = e;
	}
	int pop() {
		if (isEmpty()) error("스택 공백 에러");
		return data[top--];
	}
	int peek() {
		if (isEmpty()) error("스택 공백 에러");
		return data[top];
	}
	void display() {
		printf("[스택 항목의 수 = %2d] ==> ", top + 1);
		for (int i = 0; i <= top; i++) {
			printf("<%2d>", data[i]);
		}
		printf("\n");
	}
};

2. 큐
   

   선입선출 (FIFO, First In First Out)

2-1. 원형 큐

#include <cstdio>
#include <cstdlib>
#define MAX_QUEUE_SIZE 100

inline void error(char* message) {
	printf("%s\n", message);
	exit(1);
}

class CircularQueue {
protected:
	int front;
	int rear;
	int data[MAX_QUEUE_SIZE];
public:
	CircularQueue() { front = rear = 0; }
	bool isEmpty() { return front == rear; }
	bool isFull() { return (rear + 1) % MAX_QUEUE_SIZE == front; }
	void enqueue(int val) {
		if (isFull()) error("큐 포화 상태");
		else {
			rear = (rear + 1) % MAX_QUEUE_SIZE;
			data[rear] = val;
		}
		int dequeue() {
			if (isEmpty()) error("큐 공백 상태");
			else {
				front = (front + 1) % MAX_QUEUE_SIZE;
			}
		}
		int peek() {
			if (isEmpty()) error("큐 공백 상태");
			else return data[(front + 1) % MAX_QUEUE_SIZE];
		}
		void display() {
			printf("큐 내용: ");
			int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
			for (int i = front + 1; i <= maxi; i++)
				printf("[%2d] ", data[i % MAX_QUEUE_SIZE]);
			printf("\n");
		}
	}
};

3. 덱
   
   

#include "CircularQueue.h"

class CircularDeque :pulbic CircularQueue {
public:
	CircularDeque() {}
	void addRear(int val) { enqueue(val); }
	int deleteFront() { return deque(); }
	int getFront() { return peek(); }
	void addFront(int val) {
		if (isFull()) error("스택 포화 에러");
		else {
			data[front] = val;
			front = (front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
		}
	}
	int deleteRear() {
		if (isEmpty()) error("스택 공백 에러");
		else {
			int ret = data[rear];
			rear = (rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
			return ret;
		}
	}
	int getRear() {
		if (isEmpty()) error("스택 공백 에러");
		else return data[rear];
	}
	void display() {
		printf("덱의 내용: ");
		int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
		for (int i = 0; i <= maxi; i++) {
			printf("[%2d] ", data[i % MAX_QUEUE_SIZE]);
		}
		printf("\n");
	}
};

출처:
on my way