[C++] 자료구조/Stack 구현

처음 파트는 Linked List로 구현했다

남들은 array로 구현하는게 쉽다고 하는데

본인은 Linked List로 구현하는게 훨씬 쉽다고 느껴졌다

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

class Node {
public:
	int data;
	Node* next;

	Node(int e) {
		this->data = e;
		this->next = NULL;
	}
};

class LinkedList {
public:
	Node* head;
	Node* tail;

	LinkedList() {
		head = NULL;
		tail = NULL;
	}

	~LinkedList() {

	}

	int front() {
		return head->data;
	}

	void addFront(int e) {
		Node* n = new Node(e);
		if (head == NULL) {
			head = tail = n;
		}
		else {
			n->next = head;
			head = n;
		}
	}

	int removeFront() {
		Node* temp = head;
		head = head->next;
		return temp->data;
	}
};

class linkedStack {
public:
	int n; //스택의 원소의 개수
	LinkedList* l;

	linkedStack() {
		this->l = new LinkedList();
		this->n = 0;
	}

	int size() {
		return n;
	}

	bool empty() {
		if (n == 0) {
			return true;
		}
		else {
			return false;
		}
	}

	int top() {
		if (empty()) {
			return -1;
		}
		else {
			return l->front();
		}
	}

	void push(int e) { //스택 element 삽입
		l->addFront(e);
		n++;
	}

	int pop() { //스택 element 삭제
		if (empty()) {
			return -1;
		}
		else {
			int temp = l->front();
			l->removeFront();
			n--;
			return temp;
		}
	}

};

 

이거는 array로 구현했다

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

class arrayStack {
public:
	int* S; //배열
	int capacity; //배열의 크기
	int t; //top의 index

	arrayStack(int capacity) {
		this->capacity = capacity;
		this->S = new int[capacity];
		this->t = -1;
	}

	void size() {
		cout << t + 1 << "\n";
	}

	bool empty() {
		if (t == -1) {
			return true;
		}
		else {
			return false;
		}
	}

	void top() {
		if (t == -1) {
			cout << -1 << "\n";
		}
		else {
			cout << S[t] << "\n";
		}
	}

	void push(int e) {
		t++;
		S[t] = e;
	}

	void pop() {
		if (t == -1){
			cout << -1 << "\n";
		}
		else {
			cout << S[t] << "\n";
			t--;
		}
	}

};