선형 자료구조 정리 (스택)

스택(Stack) 이란?

1. 가장 늦게 들어간게 먼저 나가는 방식.

2. 가장 늦게 들어간 자료가 가장 먼저 나가는 구조를 후입선출(LIFO, Last In First Out)이라고도 부른다.

3. 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있다. 

4. 스택의 가장 위를 top이라고 하고, 삽입과 삭제가 top에서 일어난다.

[그림 1] 스택 구조

스택은 그래프의 자료구조의 탐색방법중 DFS(Depth First Search) 깊이우선 탐색에 사용됩니다.

[그림 2.] 스택 구조2

스택은 자료가 들어가는곳과 나가는곳이 동일하기 때문에 하나의 포인터(top)로 자료 관리가 가능하다.

구현 코드 (C++)

#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[] values;
	}

	void push(T value)
	{
		if(!isFull())
			values[++top] = value;
		else 
			cout << "Stack is Full" << endl;
	}

	void pop()
	{
		if(!empty())
			top--;
		else 
			cout << "Stack is Empty" << endl;
	}

	T Top()
	{
		if(!empty())
			return values[top];
		else
			return NULL;
	}

	bool isEmpty()
	{
		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()
{
	// int형 스택선언
	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;
}

함수 설명

push() : 원소 추가
pop() : 원소 삭제
top() : 스택의 처음이 아닌 가장 끝에있는 원소를 반환
isEmpty() : 스택이 비어있는지의 여부(스택이 비어있으면 true 아니면 false)

isFull() : 스택이 풀인지 확인 (true, false로 반환)
size() : 스택 사이즈를 반환

s1.swap(s2) : stack s2와 요소 바꾸기

프로그램 실행 시 결과 값

Stack push
┌───┐
  1
└───┘

Stack push
┌───┐
  3
  1
└───┘

Stack push
Stack is Full
┌───┐
  3
  1
└───┘

Stack Top : 3

Stack pop
┌───┐
  1
└───┘

Stack pop
┌───┐
└───┘

Stack is Empty
Stack pop
┌───┐
└───┘

계속하려면 아무 키나 누르십시오 . . .