스택(Stack)

스택은 꼭대기에서 데이터의 입출력이 일어나는 자료구조이다. 데이터의 접근을 스택 꼭대기에서만 일어나게 함으로 자료의 접근을 제한한다고 할 수 있다. 

 

스택은 오직 푸쉬와 팝 연산을 이용하여 자료의 갱신이 가능하다.

푸쉬란 자료를 넣어서 저장하는 행동이고 팝은 자료를 빼서 삭제하는 행동이다.

이런 작업은 항상 데이터의 꼭대기에서 일어나기 때문에 빨리 저장될 수록 데이터의 수정이 빨라진다.

이러한 과정을 후입선출(LIFO)라고 한다.

 

스택의 기본 구성

스택은 실제 프로그램을 구현하는데도 많이 사용한다. 예를 들어 뒤로가기, 후위연산, 역순 문자열 만들기 등이 있다.

 

 

다음은 배열을 이용한 스택을 구현할 때 필요한 함수들이다.

• push : 원소를 맨 앞에 삽입하는 함수, 스택이 꽉 차있다면 원소를 넣지 않음, 원소를 하나씩 넣어줄 때마다 새로 갱신한 원소가 top이 되도록 만듬
• pop : 원소를 맨 앞에서 삭제하는 함수, 스택이 비어있다면 원소를 삭제하지 않음, 원소를 하나씩 삭제할 때마다 삭제한 원소 바로 다음 원소가 top이 되도록 만듬, 스택의 top을 이동해서 원소가 삭제된 것처럼 보이는 것이지 실질적 삭제가 아님
• empty : 비어있는 스택인지 확인하는 함수
• full : 꽉 차있는 스택인지 확인하는 함수
• peek : 꼭대기의 값을 반환하는 함수
• size : 스택의 들어있는 원소의 갯수를 반환하는 함수
• show : 스택의 들어있는 원소들을 출력하는 함수

 

 c++로 배열을 이용한 stack을 구현하면 다음과 같다.

#include <iostream>
using namespace std;

//스택 클래스
class Stack {
private:
	int *mat; //스택의 원소가 담길 공간
	int num; //스택의 크기
	int top; //탑을 나타내는 변수
public:
	//생성자
	Stack(int num) {
		this->num = num;
		mat = new int[num]; //mat를 num만큼 할당
		top = -1; //처음 top의 위치는 -1
	}
	void push(int n); //푸쉬
	int pop(int &n); //팝, 참조를 이용하여 pop한 값을 저장
	bool empty(); //비어있는 스택인지 반환
	bool full(); //스택이 꽉 차있는지 반환
	int peek(int &n); //꼭대기 원소를 반환
	int size(); //현재 스택안에 원소들이 몇 개있는지 반환
	void show(); //스택의 모든 원소를 출력
};

//푸쉬
void Stack::push(int n) {
	if (full()) { //스택이 꽉 차있다면
		cout << "스택이 다 차있습니다.\n";
	}
	else { //스택이 다 차있지 않다면
		mat[++top] = n; //스택의 top을 증가시킨 후 n을 할당
	}
}

//팝, 참조를 이용하여 pop한 값을 반환
int Stack::pop(int &n) {
	if (empty()) { //스택이 비어있다면
		cout << "스택이 비어 있습니다.\n";
		return 0;
	}
	else { //스택이 비어있지 않다면
		n = mat[top--]; //top에 있는 값을 저장 후 top을 1감소
		return 1;
	}
}

//비어있는 스택인지 반환
bool Stack::empty() {
	if (top == -1) { //top이 -1이면, 스택이 비어있는 상태
		return true;
	}
	else { //스택이 비어있는 상태가 아니면
		return false;
	}
}

//스택이 꽉 차있는지 반환
bool Stack::full() {
	if (top + 1 == num) { //top + 1이 스택의 크기와 같다면(배열은 첫 원소 시작이 0이니까 1을 더해야 크기가 나온다.), 스택이 꽉 차있는 상태
		return true;
	}
	else { //스택이 꽉 차있는 상태가 아니면
		return false;
	}
}

//꼭대기 원소를 반환
int Stack::peek(int &n) {
	if (empty()) { //비어있으면
		cout << "스택이 비어있습니다.\n";
		return 0;
	}
	else {
		n = mat[top]; //top이 꼭대기를 가리킨다.
		return 1;
	}
}

//현재 스택안에 원소들이 몇 개있는지 반환
int Stack::size() {
	return top + 1; //top의 시작이 0인 점을 감안하면 top + 1이 맞는 표현이다.
}

//스택의 모든 원소를 출력
void Stack::show() {
	cout << "bottom |";
	for (int i = 0; i <= top; i++) {
		cout << mat[i];
		if (i == top) { //마지막 원소를 만나면 
			break; //탈출(공백을 안찍는다.)
		}
		cout << ' ';
	}
	cout << "| top\n";
}

int main() {
	int num;
	cout << "원하는 스택의 크기 : "; cin >> num;
	Stack stk(num);
	while (1) {
		int what;
		int n;
		cout << "1. 삽입, 2. 삭제, 3. top값 보기, 4. 전체 원소 출력, 5. 스택의 들어있는 원소의 갯수, 6.종료 : "; cin >> what;
		switch (what) {
		case 1:
			cout << "원하는 값 입력 : ";  cin >> n;
			stk.push(n);
			break;
		case 2:
			if (stk.pop(n)) {
				cout << "팝 한 값은 " << n << '\n';
			}
			break;
		case 3:
			if (stk.peek(n)) {
				cout << "top 값은 " << n << '\n';
			}
			break;
		case 4:
			stk.show();
			break;
		case 5:
			cout << "현재 들어있는 원소의 갯수는 " << stk.size() << "입니다.\n";
			break;
		case 6:
			return 0;
		}
		cout << "\n\n";
	}
}

 

다음은 연결 리스트를 이용한 스택을 구현해보자

연결 리스트를 이용할 경우 스택의 크기에는 제한이 없다.

연결리스트를 이용한 스택의 구성

다음은 연결리스트를 이용한 스택을 구현할 때 필요한 함수들이다.

• push : 노드를 맨 앞에 삽입하는 함수, 스택이 꽉 차있다면 노드를 넣지 않음, 노드를 하나씩 넣어줄 때마다 원래 top에 있던 원소를 새로운 노드의 뒤로 이어주고 새로운 노드를 top자리에 넣는다.
• pop : 노드를 맨 앞에서 삭제하는 함수, 스택이 비어있다면 노드를 삭제하지 않음, 삭제하려는 노드의 바로 다음 노드를 top으로 이동한 후 삭제하려는 노드는 delete로 소멸시킨다.
• empty : 비어있는 스택인지 확인하는 함수
• peek : 꼭대기의 값을 반환하는 함수
• size : 스택의 들어있는 원소의 갯수를 반환하는 함수
• show : 스택의 들어있는 원소들을 출력하는 함수

c++로 연결 리스트를 이용한 스택을 구현하면 다음과 같다.

#include <iostream>
using namespace std;

class Node {
public:
	int num; //노드가 가지고 있는 값
	Node *next; //다음 노드를 가리킬 포인터

	//생성자
	Node() {
		num = 0;
		next = NULL;
	}
};

class Stack {
public:
	int cnt; //노드의 갯수
	Node* top; //top을 가리키는 포인터

	//생성자
	Stack() {
		cnt = 0;
		top = NULL;
	}

	void push(int n); //푸쉬
	int pop(int &n); //팝, 참조를 이용하여 팝한 값을 저장
	int size(); //현재 원소의 갯수
	int peek(int &n); //탑의 원소 출력
	bool empty(); //비어있는지 판별
	void show(); //스택의 원소들을 출력
};

//푸쉬
void Stack::push(int n) {
	Node* newNode = new Node; //새로운 노드 생성
	newNode->num = n; //원하는 값을 새로운 노드의 입력
	newNode->next = top; //새로운 노드 다음에 올 노드를 현재 top노드로 삽입
	top = newNode; //top노드로 새로운 노드를 삽입
	cnt++; //노드의 갯수 증가.
}

//팝, 참조를 이용하여 팝한 값을 저장
int Stack::pop(int &n) {
	if (empty()) { //스택이 비어있다면
		cout << "스택이 비어있습니다.\n";
		return 0;
	}
	else { //스택이 비어있지 않다면
		Node* temp = top; //현재 top노드를 임시로 담아 놓음
		n = top->num; //pop한 값을 저장
		top = top->next; //top노드를 현재 top노드 바로 다음값으로 지정
		delete temp; //top노드 소멸
		cnt--; //노드의 갯수 줄이기
		return 1;
	}	
}

//현재 원소의 갯수
int Stack::size() {
	return cnt;
}

//탑의 원소 출력
int Stack::peek(int &n) {
	if (empty()) {
		cout << "스택이 비어있습니다.\n";
		return 0;
	}
	else {
		n = top->num;
		return 1;
	}
}

//비어있는지 판별
bool Stack::empty() {
	if (cnt == 0) { //노드의 갯수가 0이면
		return true;
	}
	else { //노드의 갯수가 0이 아니면
		return false;
	}
}

//스택의 원소들을 출력
void Stack::show() {
	Node* temp = top;
	cout << "top ";
	while (temp) { //노드의 끝을 만날 때까지 반복
		cout << temp->num << ' ';
		temp = temp->next;
	}
	cout << "bottom" << '\n';
}

int main() {
	Stack* stk = new Stack;
	while (1) {
		int what;
		int n;
		cout << "1. 삽입, 2. 삭제, 3. top값 보기, 4. 전체 원소 출력, 5. 스택의 들어있는 원소의 갯수, 6.종료 : "; cin >> what;
		switch (what) {
		case 1:
			cout << "원하는 값 입력 : ";  cin >> n;
			stk->push(n);
			break;
		case 2:
			if (stk->pop(n)) {
				cout << "팝 한 값은 " << n << '\n';
			}
			break;
		case 3:
			if (stk->peek(n)) {
				cout << "top 값은 " << n << '\n';
			}
			break;
		case 4:
			stk->show();
			break;
		case 5:
			cout << "현재 들어있는 원소의 갯수는 " << stk->size() << "입니다.\n";
			break;
		case 6:
			return 0;
		}
		cout << "\n\n";
	}
}