개요

스택은 자료구조의 한 종류로
LIFO(Last In, First Out)방식이다.

말 그대로, 제일 늦게 삽입된 원소가
제일 먼저 빠져나오는 구조로

FIFO(First In, FIrst Out)방식인
큐(queue)와는 반대다.

배열을 이용한 코드

#include<iostream>

using namespace std;

template <typename T>

class stack {
private:
	T* arr;								//스택 원소 넣는 배열
	int s_size;							//스택의 사이즈
	int topCursor;						//스택의 top가리키는 커서						

public:
	stack() {							//초기화
		s_size = 0;
		arr = new T[10'000];
		topCursor= 0;
	}
	~stack() {
		delete[] arr;
	}

	void push(T elem){						//원소 넣기
		arr[topCursor] = elem;
		topCursor++;

	}
	void pop(T elem){						//원소 빼기
		if (s_size!=0) {					//비어있지 않을 때
			arr[topCursor-1] = 0;
			topCursor--;
		}
		else {
			cout << "스택이 비어있습니다." << '\n';
		}
	}
	T top(){								//스택의 top 값(먼저 빠짐)
		return arr[topCursor-1];
	}

	bool empty(){							//스택이 비어있는지 여부
		if (s_size==0)
			return true;
		else 
			return false;
	}
	int size(){								//큐의 크기
		return s_size;
	}
};

스택의 제일 top을 가리키는 topCursor을 이용해
구현했다.

연결리스트를 이용한 코드

#include<iostream>

using namespace std;

template <typename T>

struct Node {
	T data;
	Node* next;
};

template <typename T>
class stack {
private:
	int q_size;								//스택 사이즈
	Node<T>* head;							//스택의 top부분 가리키는 포인터


public:
	//생성자
	stack() {						
		q_size = 0;
		Node<T>* tmpHead = new Node<T>;		
		tmpHead->data = T();
		tmpHead->next = tmpHead;
		head = tmpHead;
	}
	//소멸자
	~stack() {
		Node<T>* tmp = head;
		Node<T>* delNode = tmp;
		while (tmp != nullptr) {
			delNode = tmp;
			tmp = tmp->next;
			delete delNode;
		}

	}
	//원소 넣기
	void push(T elem) {				
		//새로운 노드 생성
		Node<T>* newNode = new Node<T>;
		newNode->data = elem;
		//연결작업
		newNode->next = head->next;
		head->next = newNode;
		q_size++;

	}
	void pop() {							//원소 빼기
		if (!empty()) {						//비어있지 않을 때
			Node<T>* delNode = head->next;
			head->next = delNode->next;
			delete delNode;
			q_size--;
		}
		else {
			cout << "큐가 비어있습니다." << '\n';
		}
	}
	T top() {								//큐의 제일 앞 값(먼저 빠짐)
		return head->next->data;
	}
	bool empty() {							//큐가 비어있는지 여부
		if (q_size == 0)
			return true;
		else return false;
	}
	int size() {								//큐의 크기
		return q_size;
	}
};

이중연결리스트와는 다르게 각 노드의 next포인터만 신경써주면 돼서 한결 구현하기 편했다.