[자료구조] 2. 스택(stack), 큐(queue)

1. 스택

데이터를일시적으로 저장하기 위한 자료구조

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

push: 데이터를 넣음

pop: 데이터를 꺼냄

top, bottom

함수 호출, 실행 시 스택 사용

스택 만들기

공부한 책은 C언어 기반이라 구조체로 구현했지만 우린 C++에서 클래스를 배웠으므로 C++로 다시 만들어보았다

#include <iostream>
using namespace std;

class stack {
private:
	int max;	//스택 용량
	int ptr;	//스택 데이터의 개수
	int* stk;	//스택 데이터를 넣을 배열(동적할당)
public:
	stack(int max) : ptr(0), max(max) {		//초기화
		stk = new int[max];
	}
	~stack() {
		delete[] stk;
		max = 0;
		ptr = 0;
	}
	int push(int x) {
		if (ptr >= max)	//스택이 가득참
			return -1;
		stk[ptr++] = x;
		return 0;
	}
	int pop(int* x) {
		if (ptr <= 0)	//스택이 비어있음
			return -1;
		*x = stk[--ptr];	//팝 데이터를 x값에 넘겨주고 ptr을 1줄임.
		return 0;
	}

	int peek(int* x) const {	//스택 꼭대기 값 보기(팝 아니고 그냥 확인만 하는거)
		if (ptr <= 0)
			return -1;
		*x = stk[ptr - 1];
		return 0;
	}

	void Clear() {
		ptr = 0;
	}

	int capacity() const {
		return max;
	}

	int size() const {
		return ptr;
	}

	bool IsEmpty() const {
		return ptr <= 0;
	}

	bool IsFull() const {
		return ptr >= max;
	}

	int search(int x) const {
		for (int i = ptr - 1; i >= 0; i--) {
			if (stk[i] == x)
				return i;
		}
		return -1;
	}

	void print() const {
		for (int i = 0; i < ptr; i++) {
			cout << stk[i] << ' ';
		}
		cout << endl;
	}
};

2. 큐

스택과 마찬가지로 데이터를 일시적으로 쌓아두기 위한 자료구조

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

enqueue: 데이터 넣기

dequeue: 데이터 빼기

front, rear(back)

배열로 큐 만들기

요소 인큐는 넣기만 하면 되지만

디큐는 요소를 꺼낸 다음 나머지 요소들을 모두 앞으로 이동시켜주어야 함

시간복잡도가 O(n)이므로 느림

링 버퍼로 큐 만들기

배열 요소를 앞으로 옮길 필요가 없음

배열의 맨 끝에서 다시 맨 앞으로 옴

첫 요소와 마지막 요소를 구별하기 위한 프런트와 리어 변수를 설정해주어야 함

#include <iostream>
using namespace std;

class queue {
private:
	int max;
	int num;	//현재 요소 개수
	int front;
	int rear;
	int* que;
public:
	queue(int max) : max(max), num(0), front(0), rear(0) {
		que = new int[max];
	}
	~queue() {
		delete[] que;
		max = num = front = rear = 0;
	}

	int enque(int x) {
		if (num >= max)		//큐가 가득 참
			return -1;
		else {
			num++;
			que[rear++] = x;
			if (rear == max)
				rear = 0;
		}
		return 0;
	}

	int Deque(int* x) {
		if (num <= 0)		//큐가 비었음
			return -1;
		else {
			num--;
			*x = que[front++];
			if (front == max)
				front = 0;
		}
		return 0;
	}

	int peek(int* x) const {		//큐가 비었음
		if (num <= 0)
			return -1;
		*x = que[front];
		return 0;
	}

	void clear() {
		num = front = rear = 0;
	}

	int capacity() const {
		return max;
	}

	int size() const {
		return num;
	}

	bool IsEmpty() const {
		return num <= 0;
	}

	bool IsFull() const {
		return num <= max;
	}

	int search(int x) const {
		int idx;
		for (int i = 0; i < num; i++) {
			if (que[idx = (i + front) % max] == x)
				return idx;
		}
		return -1;
	}
};

(Do it 자료구조와 함께 배우는 알고리즘 입문 책을 참고해 작성함)