stack 자료구조 설명 및 구현(c++)

스택 자료구조

---

 - 먼저 들어온 데이터가 나중에 나가는 형식 (선입후출)의 자료구조

 

---

STL로 구현

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


int main(void)
{
	stack<int> s; // 스택생성

	// 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4) - 삽입(5) - 삭제()

	s.push(1);
	s.push(2);
	s.push(3);
	s.pop();
	s.push(1);
	s.push(4);
	s.pop();

	cout << "Is it empty?: " << (s.empty() ? "Yes" : "No") << '\n';

	// 스택의 최상단 원소부터 출력
	while (!s.empty()) // empty : 요소가 없으면 true, 있으면 false
	{
		cout << s.top() << ' '; // top은 맨 위에 있는 요소를 반환한다.
		s.pop(); // 삭제
	}
}

stack 라이브러리를 불러오러면 #include <stack>를 사용한다.

 

위 내용을 조금씩 쪼개서 분석해보자

 

- Stack 정의, 값 넣기 및 출력

 

 - stack을 정의할 때는 "stack<데이터 자료형> stack 변수명" 이런 형태로 정의한다.

 

 - stack에 값을 추가할 때는 push라는 함수를 사용한다.

 - 위에는 int형 요소로 구성된 stack으로 정의했기 때문에 push되는 자료형도 int형으로 변환된다.

   (s.push('A') 했을 때 출력시 ASCII 코드값인 65로 출력이 된다.)

 

 - 출력은 정의된 stack의 요소크기 만큼 반복문을 이용하여 top과 pop을 이용해 출력한다.

   (보통은 while문을 많이 쓴다)

 

아래 코드 예시다.

#include <iostream>
#include <stack>

int main(void)
{
	std::stack<int> s;

	/* 1 값 넣기 */
	
	s.push(3);
	s.push(5);

	std::stack<int> tmp = s; // 출력을 위한 값 복사


	/* 1. 반복문을 이용한 출력 */
	for (int i = 0; i <= tmp.size(); i++)
	{
		std::cout << tmp.top() << " ";
		tmp.pop();
	}

	tmp = s; // 출력을 위한 값 복사

	/* 2. while문을 이용한 출력 */
	std::cout << std::endl << "stack empty? : " << (tmp.empty() ? "Yes" : "No") << std::endl;

	while (!tmp.empty()) // 빌때까지 출력
	{
		std::cout << tmp.top() << " ";
		tmp.pop();
	}
		
}

결과

5 3
stack empty? : No
5 3

위 결과를 보면 stack에 입력된 3, 5 순서가 아닌 5, 3 순서로 출력되는데 그 이유는 top 함수가 스택의 가장 처음이 아닌 가장 최근에 추가된 원소를 반환하기 때문이다.

 

가장 최근에 추가된 원소를 뽑아내면서 top에 있는 원소를 삭제하는 pop 함수를 이용해 stack을 차례대로 비우고 stack이 비워질때까지(tmp.empty()) 반복한다.

 

아래는 위 1번을 간략히 적어본 내용이다.

 

---

라이브러리 없이 구현

/*
2021-03-03
참고 사이트 : http://blog.naver.com/PostView.nhn?blogId=tipsware&logNo=221212462913&categoryNo=88&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=search
*/

#include <iostream>
using namespace std;

class Stack {
private:
	int stack_size;  // 스택 사이즈
	int stack_count; // 스택에 저장된 데이터의 개수
	int* p_stack;    // 스택으로 사용할 메모리 주소를 가리킬 포인터

public:
	// 메서드 선언
	Stack(); 
	~Stack();
	void create_stack(int size);
	void push(int value);
	void pop();
	void show_stack();
};

Stack::Stack() // 생성자
{
	// 클래스 변수 초기화
	stack_size = 0;
	stack_count = 0;
	p_stack = NULL;
}

Stack::~Stack() // 소멸자
{
	if (p_stack != NULL) delete[] p_stack; // p_stack이 존재하면 소멸
}

// 스택 생성 -> 스택에 사용할 size를 size 변수로 정의
void Stack::create_stack(int size)
{
	if (p_stack != NULL) delete[] p_stack; // 기존에 사용하던 메모리가 있으면 해당 메모리를 제거한다.
	stack_size = size; // 이 코드를 실행해주는 이유는 class 변수에 값을 넣어주기 위해
	p_stack = new int[stack_size]; // 새로 메모리를 할당한다.
}

// 스택 푸쉬
void Stack::push(int value)
{
	// 스택에 빈 공간이 있을 때 값을 넣는다.
	if (stack_count < stack_size)
	{
		*(p_stack + stack_count) = value; // 스택 메모리 공간에 stack_count index 만큼의 주소값에 값을 넣어 준다.
		stack_count++; // 저장이 되어 스택 count를 증가시킨다.
	}
	else
		cout << "Stack이 가득 찼다" << endl;
}

// pop 구현
void Stack::pop()
{
	if (stack_count == 0) // 저장된 stack이 없으면
	{
		cout << "Stack에 저장된 값들이 없다." << endl;
	}
	else
	{
		cout << "Popped!!" << endl;
		p_stack[stack_count--] = 0; // 마지막 값을 0으로 만들고 stack_count를 감소시킨다.
	}
}


void Stack::show_stack()
{
	if (stack_count == 0) cout << "Stack에 저장된 값들이 없습니다" << endl;

	else 
	{
		cout << "Stack에 저장된 값은 아래와 같습니다." << endl;
		for (int i = 0; i < stack_count; i++)
		{
			cout << i << " : " << p_stack[i] << endl;
		}
		cout << "총 " << stack_count << "개의 value가 저장되어 있다." << endl;
	}
}


int main(void)
{
	Stack stack;
	int s_size = 0;
	int tmp = 0;
	int button = -1; // 아무 숫자로 초기화
	int value = 0;
	cout << "Stack 사이즈를 입력하세요 : ";

	// 입력된 stack 사이즈가 양수인지 체크
	while (s_size <= 0)
	{
		scanf_s("%d", &tmp);
		if (tmp <= 0)
		{
			cout << "stack_size를 양수로 입력하세요, 현재 입력된 값 ->" << s_size << endl << endl;
			cout << "Stack 사이즈를 입력하세요 : ";
		}
		else s_size = tmp;
	}

	// 스택 생성
	stack.create_stack(s_size);


	cout << endl;
	cout << "1. Stack Push" << endl;
	cout << "2. Stack Pop" << endl;
	cout << "3. Stack Print" << endl;
	cout << "0. Exit program" << endl;
	cout << endl << endl;

	while (button != 0)
	{
		cout << "버튼 선택 : ";
		scanf_s("%d", &button);
		cout << endl << endl;
		switch (button)
		{
		case 1: // 입력한 값 저장
			cout << "저장할 값은 ? : ";
			scanf_s("%d", &value);
			stack.push(value);
			break; // break 필수 안그러면 아래 항목들도 실행

		case 2:
			stack.pop();
			break;

		case 3:
			stack.show_stack();
			break;

		}

	}
	return 0;

}

 

라이브러리 없이 구현하는 건 아래 사이트를 참고하여 변경

m.blog.naver.com/PostView.nhn?blogId=tipsware&logNo=221212462913&proxyReferer=https:%2F%2Fwww.google.com%2F

 

내용 참고

www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3