Stack

개요

한 쪽 끝에서만 삽입 삭제가 일어나는 자료구조

 

 

Stack의 성질

Last-in First-out (LIFO), 즉 후입선출 방식으로 객체를 담는다.

 

삽입과 삭제에 쓸 위치를 알고 있어야 한다.

 

 

Stack

대표적인 operation은 push, pop이 있고, 추가로 top, size, empty 등을 지원할 수 있다.

 

Array 또는 Linked List로 구현할 수 있다.

 

아래는 각각에 대한 예시이다.

 

struct ArrayStack {
    int* stack;
    int maxSize, sz;
    
    ArrayStack(int ms) {
        maxSize = ms;
        sz = 0;
        stack = new int[maxSize];
    }
    
    void push(int data);
    int pop();
}

struct Node {
    int data;
    Node* next;

    Node(int d) {
        data = d;
        next = nullptr;
    }
}

struct SLLStack {
    Node* head;
    int sz;

    SLLStack() {
        head = nullptr;
        sz = 0;
    }

    void push(int data);
    int pop();
}

 

예외처리

빈 스택에 pop, top을 호출하면 예외가 발생한다.

 

이에 대한 적절한 처리 (throw StackEmpty 등)가 필요하다.

 

Array 기반 스택은 사용할 수 있는 공간이 한정되어, 스택이 가득 찼을 때의 push 호출에 대한 예외 처리 역시 필요하다.

 

 

Array 기반 스택

index 0부터 원소를 push한다.

 

마지막에 삽입한 원소의 index를 기억하는 변수를 만들어 다방면에 활용할 수 있다.

 

 

Linked List 기반 스택

Singly linked list의 addFront, removeFront를 구현하였다면 그대로 스택으로 사용할 수 있다.

 

 

Implementation

아래는 이론에서 배운 내용을 구현한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

/*

# Time complexity for both implementations:

# empty()	O(1)
# top()		O(1)
# push()	O(1)
# pop()		O(1)
# size()	O(1)

*/

struct ArrayStack {
	int* stack;
	int maxSize, sz;

	ArrayStack(int ms) {
		maxSize = ms;
		sz = 0;
		stack = new int[maxSize];
		for (int i = 0; i < maxSize; ++i) stack[i] = 0;
	}

	bool empty() {
		return (sz == 0);
	}
	int top() {
		if (empty()) return -1;
		return stack[sz - 1];
	}
	void push(int data) {
		stack[sz] = data;
		sz++;
	}
	int pop() {
		if (empty()) return -1;
		int ret = stack[sz - 1];
		sz--;
		return ret;
	}
	int size() {
		return sz;
	}
};

struct Node {
	int data;
	Node* next;
	
	Node(int d) {
		data = d;
		next = nullptr;
	}
};
struct SLLStack {
	Node* head;
	int sz;

	SLLStack() {
		head = nullptr;
		sz = 0;
	}

	bool empty() {
		return (!head);
	}
	int top() {
		if (empty()) return -1;
		return head->data;
	}
	void push(int data) {
		Node* newNode = new Node(data);
		newNode->next = head;
		head = newNode;
		sz++;
	}
	int pop() {
		if (empty()) return -1;
		Node* tar = head;
		int ret = tar->data;
		head = tar->next;
		delete tar;
		sz--;
		return ret;
	}
	int size() {
		return sz;
	}
};

int main() {
	// ArrayStack A(10000);
	SLLStack A;
	int TEST; cin >> TEST; while (TEST--) {
		string oper; int p; cin >> oper;
		if (oper == "empty") {
			cout << (A.empty() ? 1 : 0) << "\n";
		}
		else if (oper == "top") {
			cout << A.top() << "\n";
		}
		else if (oper == "push") {
			cin >> p; A.push(p);
		}
		else if (oper == "pop") {
			cout << A.pop() << "\n";
		}
		else if (oper == "size") {
			cout << A.size() << "\n";
		}
	}
}

 

 

응용

균형잡힌 세상 boj.kr/4949

4949번: 균형잡힌 세상

#include <bits/stdc++.h>
using namespace std;

struct Node {
	int data;
	Node* next;

	Node(int d) {
		data = d;
		next = nullptr;
	}
};
struct SLLStack {
	Node* head;
	int sz;

	SLLStack() {
		head = nullptr;
		sz = 0;
	}

	bool empty() {
		return (!head);
	}
	int top() {
		if (empty()) return -1;
		return head->data;
	}
	void push(int data) {
		Node* newNode = new Node(data);
		newNode->next = head;
		head = newNode;
		sz++;
	}
	int pop() {
		if (empty()) return -1;
		Node* tar = head;
		int ret = tar->data;
		head = tar->next;
		delete tar;
		sz--;
		return ret;
	}
	int size() {
		return sz;
	}
};

int isParentheses(char t) {
	string open = "([", close = ")]";
	for (char& c : open) if (c == t) return 1;
	for (char& c : close) if (c == t) return 2;
	return 0;
}

int main() {
	while (1) {
		SLLStack A;

		string s; getline(cin, s);
		if (s == ".") break;

		bool good = true;

		for (char& c : s) {
			int type = isParentheses(c);
			if (!type) continue;

			if (type == 1) A.push(c);
			if (type == 2) {
				if (A.empty()) {
					good = false;
				}
				else if (c == ')' && A.top() == '(' || c == ']' && A.top() == '[') {
					A.pop();
					continue;
				}
				else {
					good = false;
				}
			}

			if (!good) break;
		}

		cout << (good && A.empty() ? "yes" : "no") << "\n";
	}
}

 

후위 표기식 boj.kr/1918

1918번: 후위 표기식

#include <bits/stdc++.h>
using namespace std;

struct Node {
	char data;
	Node* next;

	Node(int d) {
		data = d;
		next = nullptr;
	}
};
struct SLLStack {
	Node* head;
	int sz;

	SLLStack() {
		head = nullptr;
		sz = 0;
	}

	bool empty() {
		return (!head);
	}
	char top() {
		if (empty()) return -1;
		return head->data;
	}
	void push(char data) {
		Node* newNode = new Node(data);
		newNode->next = head;
		head = newNode;
		sz++;
	}
	char pop() {
		if (empty()) return -1;
		Node* tar = head;
		int ret = tar->data;
		head = tar->next;
		delete tar;
		sz--;
		return ret;
	}
	int size() {
		return sz;
	}
};

int prec(char t) {
	if (t == '(') return 0;
	if (t == '+' || t == '-') return 1;
	if (t == '*' || t == '/') return 2;
	return -1;
}

int main() {
	SLLStack A;
	string s; cin >> s;

	for (char& c : s) {
		if ('A' <= c && c <= 'Z') cout << c;
		else if (c == '(') A.push(c);
		else if (c == '+' || c == '-' || c == '*' || c == '/') {
			while (!A.empty() && prec(c) <= prec(A.top())) cout << A.pop();
			A.push(c);
		}
		else if (c == ')') {
			while (!A.empty() && A.top() != '(') cout << A.pop();
			A.pop();
		}
	}
	while (!A.empty()) cout << A.pop();
	cout << "\n";

	return 0;
}