[자료구조] 2. Stack(스택)

Stack

이번 시간에는 Stack이란 무엇인지, 어떻게 구현하는지를 배운다.

---

Stack의 개념

스택은 맨 처음 들어간 게 맨 마지막에 나오는 그릇 모양의 자료 구조이다.

Stack의 구조

• 위의 그림에서, 가장 최근에 들어간 4번 데이터가 가장 먼저 사용될 것이다. 4번 데이터를 빼낸 다음에서야 3번 데이터를 사용할 수 있다.
• 참고로 가장 먼저 들어간 data가 가장 먼저 나오는 자료구조는 queue이다. 도식화하면 다음과 같다.

Queue의 구조

 

 

---

Stack의 유용한 기능들

기능 1: pop()

• top node(가장 최근에 들어간 node)를 stack에서 빼내서 return하는 함수
• 예외 처리: stack이 비어 있는데 pop()으로 하나를 꺼내 달라고 하는 경우

 

기능 2: push(int data)

• Stack에 node를 하나 추가하는 함수
• 이제 top은 새로 추가한 그 node가 될 것이다.
• 예외처리: Stack이 꽉 차있는데 push()로 하나 더 집어 넣으려고 하는 경우

 

기능 3: top()

• top node(가장 최근에 들어간 node)를 return하는 함수
• pop()과는 달리 그냥 이런 게 있다... 하고 알려 주기만 한다.
• 예외 처리: stack이 비어 있는데 top()으로 제일 위에 있는 node의 data를 알려달라고 하는 경우

 

기능 4: size()

• Stack 안에 node가 몇 개 있는지를 return 하는 함수

 

---

배열을 이용해 Stack 구현하기

배열을 이용한 Stack의 전체 코드

#include<iostream>
using namespace std;

class arrStack {
public:
	int* arr;
	int capacity;
	int t;

	arrStack(int capacity) {
		this->capacity = capacity;
		this->arr = new int[capacity];
		this->t = -1;
	}

	int size() { return t + 1; }

	bool is_empty() { return t == -1; }

	int top() {
		if (is_empty()) return -1;
		else return arr[t];
	}

	int push(int data) {
		if (size() == capacity) return -1;
		else arr[++t] = data;
	}

	int pop() {
		if (is_empty()) return -1;
		else arr[t--];
	}
};

 

arrStack의 member data

	int* arr; //나중에 capacity 크기만큼 동적할당할 배열의 첫 주소
	int capacity; //stack의 크기
	int t; //top node의 index

 

 

arrStack의 constructor

	arrStack(int capacity) {
		this->capacity = capacity;
		this->arr = new int[capacity];
		this->t = -1;
	}

• parameter로 받아온 capacity로 총 용량이 정해진 stack을 생성한다.
• arr에 capacity만큼의 int형 배열을 동적할당한다. 앞으로 arr[1]처럼 쓸 수 있다.
• top node의 index를 -1로 초기화한다. 앞으로 node를 한 개 push()했을 때 ++되어 맨 처음 node의 index가 0이 될 것이다.

 

stack의 크기를 반환하는 size()

	int size() { return t + 1; }

• t는 top node, 그러니까 가장 최근에 추가된 node의 index를 담고 있다.
• index는 0부터 시작하므로 n개의 node가 있다면 t의 값은 n-1일 것이다.
• t+1로 size를 반환한다.

 

빈 스택일 경우 true를 반환하는 is_empty()

	bool is_empty() { return t == -1; }

• 만약 Stack이 비어 있을 경우, t는 -1일 것이다. 처음에 -1로 초기화 된 이후로 ++된 적이 없으니까.
• 그렇다면 스택이 비어 있을 경우엔 t==-1인 게 true이다. true를 return한다.

 

가장 최근 들어간 data를 반환하는 top()

	int top() {
		if (is_empty()) return -1;
		else return arr[t];
	}

• (예외처리) 만약 stack이 비어 있다면 -1을 return.
• return -1은 오류라는 뜻이다.
• 정상적인 상태라면 top node의 index에 있는 배열의 값, 곧 top node의 배열의 값을 return.

 

Stack에 data를 하나 추가하는 push()

	int push(int data) {
		if (size() == capacity) return -1;
		else arr[++t] = data;
	}

• (예외처리) 만약 stack이 꽉 차있다면 return -1.
• 정상적인 상태일 경우, ++t로 미리 t값을 한 개 늘려준 다음에
• 새로 만든 index에 data를 집어 넣어준다.
• t는 이미 +1 되어있으므로 top node는 업데이트 되어 있다.

 

top node를 뱉어내는 pop()

	int pop() {
		if (is_empty()) return -1;
		else arr[t--];
	}

• (예외처리) 만약 stack이 비어 있다면 -1을 return.
• 정상적인 상태라면 top node의 index에 있는 배열의 값, 곧 top node의 배열의 값을 return.
• 일단 원래 t의 값을 return한 이후에 후위 연산자인 --로 t값을 하나 줄여준다.

 

 

 

Linked-List를 이용해 Stack 구현하기

 

• Stack은 어차피 중간에 못 끼워 넣는데 왜 굳이 중간에 끼워넣기 용이하게 만든 Linked-List를 쓰는지 궁금했었다.
• 하지만 Linked-List는 size가 확실히 정해지지 않아도 stack을 구현할 수 있다는 장점이 있다.

 

Linked-List를 이용한 Stack의 전체 코드

#include<iostream>
using namespace std;

class Node {
public:
	int data;
	Node* next;

	Node(int data) :data{ data }, next{ nullptr } {}
};

class linkedStack {
public:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;

	linkedStack() = default;

	int size()const { return size; }
	bool is_empty() { return size == 0; }

	int top() {
		if (is_empty()) return -1;
		else return head->data;
	}

	int push(int data) {
		Node* newNode = new Node{ data };

		if (is_empty()) {
			head = newNode;
			tail = newNode;
		}
		else {
			newNode->next = head;
			head = newNode;
		}

		size++;
	}

	int pop() {
		if (is_empty()) return -1;
		else {
			Node* tmp = head;
			head = head->next;
			size--;
			return tmp->data;
		}
	}
};

 

Node 하나하나의 역할을 하는 Node class

class Node {
public:
	int data;
	Node* next;

	Node(int data) :data{ data }, next{ nullptr } {}
};

• Node 하나 당 data와 다음 Node의 주소가 들어간다.
• 생성자에서 각각 초기화한다.

 

linkedArr의 member data

	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;

• head와 tail node의 pointer를 미리 만들어 두고 NULL로 초기화한다.
• size는 현재 stack의 size. 0으로 초기화한다.

 

stack의 크기를 반환하는 size()

	int size()const { return size; }

• 그냥 size 반환... 여기서 뭘 바꿀 이유가 없으니까 const로 안정성

 

빈 스택일 경우 true를 반환하는 is_empty()

	bool is_empty() { return size == 0; }

• 만약 Stack이 비어 있을 경우 size==0. size==0일 경우 true 반환

 

가장 최근 들어간 data를 반환하는 top()

	int top() {
		if (is_empty()) return -1;
		else return head->data;
	}

• (예외처리) 만약 stack이 비어 있다면 -1을 return.
• return -1은 오류라는 뜻이다.
• 정상적인 상태라면 head(top) node의 data를 return.

 

Stack에 node를 하나 추가하는 push()

	int push(int data) {
		Node* newNode = new Node{ data };

		if (is_empty()) {
			head = newNode;
			tail = newNode;
		}
		else {
			newNode->next = head;
			head = newNode;
		}

		size++;
	}

• (예외처리) Stack이 꽉 차있을 경우는 없다. 왜냐하면 애초에 전체 capacity를 정해줄 필요가 없으니까...
• (예외처리) 만약 node가 하나도 없다면 만들어준 그 node가 head이자 tail이 되어야 한다.
• 새로운 data를 data로 갖는 node를 하나 동적할당해주고, 그 주소를 newNode에 저장한다.
• 새로 만든 newNode의 link field에 기존의 head를 등록해준다.
• head를 새로 만든 node로 업데이트해준다.
• size를 한 개 늘려준다.

 

top node를 뱉어내는 pop()

	int pop() {
		if (is_empty()) return -1;
		else {
			Node* tmp = head;
			head = head->next;
			size--;
			return tmp->data;
		}
	}

• (예외처리) 만약 stack이 비어 있다면 -1을 return.
• 없앨 head를 하나 복사해준다.(shallow copy)
• head를 직전의 node로 업데이트해준다.
• size를 1 줄인다.
• 복사해 둔 원래 tmp의 data를 return한다.