<자료구조 알고리즘> 스택 구현

스택 구현

이번에는 스택을 구현해보자.

구현은 동적 배열을 이용해서도 구현을 할 수 있기는 하지만 중간에 있는 데이터에 접근하지는 않을 것이고 끝에 추가 삭제를 많이 할 테니 연결 리스트를 사용하는 것이 더 효율적일 것이다.

 옆 그림과 같이 일반 연결 리스트를 이용해서 쉽게 구현할 수 있다.

head가 가르키는 곳이 스택의 가장 윗부분이다. 데이터를 추가할 때는 새로운 노드의 다음 노드로 원래 head노드를 저장하고 head가 새로운 노드를 가르키게 하면 된다. 

데이터를 꺼낼 때는 head가 가장 위 노드의 다음 노드를 가르키게 하면 된다. 

코드로 구현해 보면 다음과 같다.

 

 

 

template<typename T>
struct list
{
	T val;
	list* next;
	list() : val(NULL), next(NULL) {};
};

template<typename T>
class stack
{
	list<T>* head = NULL;
	int length = 0;
public:
	void push(T val) {
		list<T>* node = new list<T>;
		node->val = val;
		node->next = head;
		head = node;
		length++;
	}
	void pop() {
		if (length) {
			head = head->next;
			length--;
		}
	}
	T top() {
		if (length)
			return head->val;
		else return NULL;
	}
	int size() {
		return length;
	}
	bool empty() {
		if (length)
			return false;
		else
			return true;
	}
};

 

제대로 구현했는지 확인하기

https://www.acmicpc.net/problem/10828

10828번: 스택

백준에 10828번 문제를 이용하면 제대로 잘 구현했는지 확인 해 볼 수 있다. 

자신이 구현한 스택을 이용하여 위 문제를 풀어보자.

 

#include <iostream>
#include <string>

using namespace std;

template<typename T>
struct list
{
	T val;
	list* next;
	list(T val) : val(val), next(NULL) {};
	list() : val(NULL), next(NULL) {};
};

template<typename T>
class stack
{
	list<T>* head = NULL;
	int length = 0;
public:
	void push(T val) {
		list<T>* node = new list<T>;
		node->val = val;
		node->next = head;
		head = node;
		length++;
	}
	void pop() {
		if (length) {
			head = head->next;
			length--;
		}
	}
	T top() {
		if (length)
			return head->val;
		else return NULL;
	}
	int size() {
		return length;
	}
	bool empty() {
		if (length)
			return false;
		else
			return true;
	}
};
int main() {
	int n, input;
	string s;
	stack<int> q;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		if (s == "push") {
			cin >> input;
			q.push(input);
		}
		else if (s == "pop") {
			if (q.size()) {
				cout << q.top() << endl;
				q.pop();
			}
			else
				cout << -1 << endl;

		}
		else if (s == "size") {
			cout << q.size() << endl;
		}
		else if (s == "empty") {
			cout << q.empty() << endl;
		}
		else if (s == "top") {
			if (q.size())
				cout << q.top() << endl;
			else
				cout << -1 << endl;
		}
	}
}

 

 

stl stack

이제는 c++ 표준라이브러리에서 제공하는 스택에 대해 알아보자.

 

헤더파일

#include<stack>

선언

<>안에 자료형 맨 뒤에 이름 괄호 안에 크기를 적어 선언 할 수 있다.

stack<int> s;
stack<int> s(2); //크기 2

함수

 

s.empty();

스택이 비었으면 true 아니면 false 리턴

상수 시간 복잡도

 

s.size();

스택의 크기 리턴

상수 시간복잡도

 

s.top();

가장 위(마지막에 추가된) 데이터 리턴

상수 시간복잡도

 

s.pop();

가장 위(마지막에 추가된) 데이터 삭제

리턴값 없음

상수 시간 복잡도

 

s.push();

추가할 데이터 매개변수로 전달하면 맨 위에 추가

리턴 값 없음

상수 시간 복잡도

 

s1.swap(s2);

두 스택의 값을 서로 바꿈

바꾸고 싶은 스택을 매개변수로 전달

리턴 값 없음

상수 시간 복잡도

 

더 자세히 알아보고 싶다면 밑에 링크 참고

https://www.cplusplus.com/reference/stack/

<stack> - C++ Reference