자료구조 : Stack (Feat. 백준 10828 : 스택)

설명

---

스택은 LIFO (Last In, First Out) 이다. '설명 끝!' 이라고 할 수 있다. 가장 늦게 들어온 데이터가 가장 빨리 나간다. 우리가 코딩한 프로그램이 함수를 호출할 때도 스택 프레임(Stack Frame) 이라는 메모리 블록을 할당하는데 여기에는 함수가 호출될 때 이와 관계되는 변수가 저장된다. 우리가 흔히 사용하는 재귀에서도 스택 구조로 변수가 할당된다.

 

함수에 대한 설명은 백준 10828번 : 스택 을 참조하자.

 

 

코드

---

#include <iostream>
#include <string>

using namespace std;

template <typename T>
class stack;

template <typename T>
class Node
{
	friend class stack<T>;
	
	private:
		T data;
		Node<T>* prev;
		Node<T>* next;
	
	public:
		Node(T data, Node<T>* prev=NULL, Node<T>* next=NULL)
		{
			this->data = data;
			this->prev = prev;
			this->next = next;
		}
};

template <typename T>
class stack
{
	private:
		Node<T>* head;
		Node<T>* tail;
		int size;
	
	public:
		stack()
		{
			head = tail = NULL;
			size=0;
		}
	
		int getSize()
		{
			return size;
		}
	
		void push(T data)
		{
			if(getSize()==0)
			{
				head = new Node<T>(data);
				tail = head;
				++size;
			}
			
			else
			{
				tail->next = new Node<T>(data);
				tail->next->prev = tail;
				tail = tail->next;
				++size;
			}
		}
	
		void top()
		{
			if(empty())
				cout<<"-1\n";
			else
				cout<<tail->data<<'\n';
		}
	
		int empty()
		{
			if(head==NULL)
				return 1;
			else
				return 0;
		}
	
		int pop()
		{
			if(empty())
				return -1;
			else
			{
				int temp = tail->data;
				if(getSize()==1)
				{
					delete head;
					tail=head=NULL;
				}
				else
				{
					tail = tail->prev;
					delete tail->next;
					tail->next = NULL;
				}
				--size;
				return temp;
			}
		}
	
		~stack()
		{
			while(head!=NULL)
			{
				if(empty())
					break;
				else
					pop();
			}
		}
};

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string cmd;
	int data,N;
	cin>>N;
	
	stack<int> s;
	
	for(int i=0; i<N; ++i)
	{
		cin>>cmd;

		if(cmd=="push")
		{
			cin>>data;
			s.push(data);
		}
		
		if(cmd=="pop")
			cout<<s.pop()<<'\n';
		
		if(cmd=="size")
			cout<<s.getSize()<<'\n';

		if(cmd=="empty")
			cout<<s.empty()<<'\n';
		
		if(cmd=="top")
			s.top();
	}
	
	return 0;
}

 

 

실행 결과

---