[자료구조] 스택(stack)

스택(stack)의 개념

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조

스택(stack)의 연산

스택은 LIFO(Last In First Out, 후입선출)을 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

• pop() : 스택에서 가장 위에 있는 항목을 제거한다.
• push(item) : item 하나를 스택의 가장 윗 부분에 추가한다.
• top() : 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty() : 스택이 비어 있을 때에 true를 반환한다.

스택(stack)의 구현

문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

• 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.
• 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
• 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.
  스택은 연결리스트 로 구현할 수 있다. 연결리스트의 같은 방향에서 아이템을 추가하고 삭제하도록 구현한다.

#include <iostream>
#define MAXVALUE 2
using namespace std;

template<class T> class Stack
{
public:
	int top; // 가장 위에 있는 원소
    int size; // 현재 스택에 들어와있는 원소 개수
    T *values;
    
    Stack(){
		size = MAXVALUE;
        values = new T[size];
        top = -1;
        }
   ~Stack(){
   		delete[] value;
        }
        
    void push(T value){
    	if(!isFull())
        	values[++top] = value;
        else
        	cout << 'Stack is Full' <<endl;
         }
    T Top()
	{
		if(!empty())
			return values[top];
		else
			return NULL;
	}

	bool empty()
	{
		if(top < 0)
			return true;
		else 
			return false;
	}

	bool isFull()
	{
		if(top+1 == size) 
			return true;
		else 
			return false;
	}
};

template<typename T>
ostream& operator <<(ostream &out, Stack<T> &st){
	T *temp = st.values;
	out << "┌───┐" <<endl;
	for(int i=st.top; i>=0; i--){
	    out <<"  "<<temp[i]<< endl;
	}
	out << "└───┘" << endl;
    return out;
}

int main()
{
	Stack<int> st;
	cout << "Stack push" << endl;
	st.push(1);
	cout << st << endl;
	cout << "Stack push" << endl;
	st.push(3);
	cout << st << endl;
	cout << "Stack push" << endl;
	st.push(5);
	cout << st <<endl;
	cout << "Stack Top : " <<st.Top() << endl << endl;
	cout << "Stack pop" << endl;
	st.pop();
	cout << st << endl;
	st.pop();
	cout << "Stack pop" << endl;
	cout << st << endl;
	st.pop();
	cout << "Stack pop" << endl;
	cout << st << endl;
}

operator <<

• stack과 Items 에 의해 다중화
• friend로 선언되어 stack의 전용 데이터 멤버에 접근 가능

template <class T>
ostream& operator<<(ostream& os, stack<T>& S){
// os << "top= "<<s.top<<endl;
// for(int i=0;i<=s.top;i++)os<<i<<":"<<s.stack[i]<<endl;
	
    stack<T> s2; //역으로 출력하기 위해 임시스택 s2 이용
    while(!s.empty()) {s2.push(s.top()); s.pop();}
    while(!s2.empty()) {os<<"->"<<s2.top; s.push(s2.top()); s2.pop();}
    return os;
}

스택(stack)의 사용 사례

재귀 알고리즘을 사용하는 경우 스택이 유용하다.

• 재귀 알고리즘
  * 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
  • 재귀함수를 빠져나와 backtrack을 할떄는 스택에 넣어 두었던 임시 데이터를 뺴 줘야 한다.
  • 스택은 이런 일련의 행위를 직관적으로 가능하게 해준다
  • 또한 스택은 재귀 알고리즘을 반복적 형태를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문 기록(뒤로가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호 검사)
• 후위 표기법 계산