개요

백준 10828번: 스택

• 입력
  첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

• 출력
  출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

접근방법

1, STL라이브러리의 stack을 사용해도 되지만,
스택을 연결리스트를 이용해 구현하여 사용하였다.

코드

#include<iostream>


using namespace std;

int N;

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 << -1 << '\n';
		}
	}
	T top() {								//큐의 제일 앞 값(먼저 빠짐)
		if (empty())return -1;
		else return head->next->data;

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

stack<int>* q = new stack<int>();

void input() {
	string tmp="";
	int tmpInt = 0;
	cin >> N;
	for (int i=0; i < N; i++) {
		cin >> tmp;
		if (tmp == "push") {
			cin >> tmpInt;
			q->push(tmpInt);
		}
		else if (tmp == "pop") {
			if(!q->empty())cout<<q->top() << '\n';
			q->pop();
		}
		else if (tmp == "size") {
			cout<<q->size()<<'\n';
		}
		else if (tmp == "empty") {
			cout << q->empty() << '\n';
		}
		else if (tmp == "top") {
			cout << q->top() << '\n';
		}

	}
}


int main() {
	input();
}

문풀후생

최근 원형 연결리스트, 이중연결리스트등을 직접 구현하다보니
연결리스트 구현도 점점 빨라진다.. 노드 삭제나 노드 추가는 생각안해도 그냥 적을 정도로
좋은 현상인거 같다,,