추상적 자료형(Abstract data type)과 자료구조(Data structure)는 엄밀히 말하면 다르다.
가령 스택의 경우는 추상적 자료형이다. 그 이유는 리스트(List)는 정의만 존재하고 구현은 사용자 마음이다.
그러나 만약 누군가가 연결리스트(Linked List), 혹은 배열리스트(Array List, Vector)를 말한다면 그건 자료구조인 셈이다.
그러나 이런 구분이 애매한 녀석들도 존재하기는 한다.
스택(Stack)같은 녀석이 그 정체인데 스택은 추상적 자료형으로 분류되는게 맞으나 사실상 자료구조라고도 볼 수 있다.
왜냐하면 스택을 구현하는 방식이 배열과 연결리스트 두가지가 존재하긴 하지만 사실상 무조건 배열을 쓰는게 이득이기 때문이다.
그래서 필자의 포스팅에서는 추상적 자료형과 자료구조를 엄밀히 구분하지 않고 모두 자료구조라 논하겠다.
참고:
이 사이트의 예제 문제는 백준 사이트(https://www.acmicpc.net/)를 참조합니다.
예제:
백준 스택(10828)
백준 괄호(9012)
백준 쇠막대기(10799)
백준 스택수열(1874)
백준 괄호의 값(2504)
백준 탑(2493)
백준 괄호 제거(2800)
스택 자료구조는 가장 기초적인 자료구조이고 많이 쓰이는 자료구조이다.
스택은 LIFO(Last In First Out)의 자료구조로서 나중에 들어온 자료가 가장 먼저 나가는 사람입장에서 보면 조금 어의 없는 자료구조이다.
우리는 어렸을 때부터 선착순에 익숙해지며 설아왔는데 갑자기 선착순이 아니라 먼저 들어온놈이 나간다는게 조금 이상할 수 있다.
그런데 그렇게 생각할께 아니라 상자같은 것을 생각해 보자.
여러분이 이사같은데를 각거나 물건을 정리해야할 때가 있다.
그러면 물건을 상자에 차곡차곡 담는다.
상자에 물건을 다채우고 가던도중 문득 A라는 물건을 꺼내고 싶을 때가있다.
이때 여러분은 A라는 물건을 꺼내기 위해서 어떻게 해야하는가?
상당히 골치아픈 문제다. 물건이 차곡차곡 쌓여져 있기 때문에 어디있는지는 알 도리가 없다.
결국 처음부터 끝까지 다 꺼내보는 수 밖에 없다는 것이다.
대신 제일 위에 있는 물건은 뭔지 바로 알 수 있다.
이 자료구조가 바로 스택이다.
스택은 그래서 아래와 같은 몇가지 특징을 가진다.
1.제일 위의 데이터만 확인할 수 있다. 또한 제일 위의 데이터만 삭제할 수 있다.
2.경우에 따라서 데이터의 갯수를 확인할 수도, 없을수도 있다. 일반적으로 데이터의 갯수는 중요치 않다.
3.중간의 어떠한 데이터가 있는지 확인할 방법은 없다. 확인하려면 모든데이터를 들어내야한다.
스택의 구현은 배열과 연결리스트를 사용한 방법이 있지만 99.999999%는
배열을 이용해서 만듦으로 연결리스트를 사용한 방법은 없다고 가정해도 무방하다.
필자도 이 부분에서 언급하지 않을 생각이다.
구현시 반드시 필요한 메소드는 아래 5가지이다.
push - 값을 넣는다.
top - 제일 위의 값을 확인한다.
pop - 제일 위의 값을 제거한다.
empty - 스택이 비었는지 확인한다.
size - 스택의 사이즈를 확인한다.
스택을 C언어로 구현하는 일은 매우 간단한 일이다.
아무래도 가장 쉬운 자료구조이기 때문일 것이다.
직관성으로 따지면 연결리스트 보다도 구현이 쉽다고 할 수 있다.
#include <stdio.h>
#include <stdbool.h>
#define MAXSIZE 1000
int stack[MAXSIZE];
int stack_size = 0;
void push(int item) {
stack[stack_size++] = item;
}
int top() {
return stack[stack_size - 1];
}
void pop() {
stack_size--;
}
bool empty() {
return stack_size == 0 ? true : false;
}
int size() {
return stack_size;
}
보통 필수적으로 구현하게 되는 스택의 함수는 5가지이다.
각각의 역활에 대해서 가볍게 이야기 해보도록 하자.
push - 값을 넣는다. 스택에서는 무조건 마지막에 값을 넣기 때문에 제일 마지막 원소에 값이 들어가게 된다.
top - 제일 위의 값을 확인한다. 현재 스택사이즈보다 1개를 작게 해야하는 이유는 배열의 원소를 1개 작게 해야하는 원리와 같다.(배열원소를 0부터 사용하므로)
pop - 제일 위의 값을 삭제한다. 값을 삭제하지않고 번호만 한개 줄여서 의아해 할 수 있는데 어짜피 번호하나를 지우기만해도 그 값에 접근하지 못한다.
empty- 스택이 비어있는지 확인한다.
size - 스택의 크기를 반환한다.
보다시피 모든 부분에서 한줄로 구현이 가능할 정도로 구현은 매우 쉽다.
스택은 C에서는 구현이 되어 있지않으므로 직접 제작해야한다.
그러나 자주쓰는 자료형인 만큼 다른 언어에서는 이미 만들어져 있는 경우가 많다.
그래서 다른 언어에서는 어떻게 사용하는지 보도록하자.
#include <iostream>
#include <stack>
using namespace std;
stack<int> s;
int main(){
for(int i=0;i<=10;i++){
s.push(i);
}
cout<<"top :"<<s.top()<<endl;
cout<<"empty :"<<s.empty()<<endl;
cout<<"size :"<<s.size()<<endl;
s.pop();
cout<<"pop-top :"<<s.top()<<endl;
return 0;
}
이미 주요함수들이 모두 구현되어 있다.
stack 헤더를 선언해야하고 std네임 스페이스로 접근할 수 있다.
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack<>();
for(int i=0;i<=10;i++){
s.push(i);
}
System.out.println("top :"+s.peek());
System.out.println("empty :"+s.empty());
System.out.println("size :"+s.size());
s.pop();
System.out.println("pop-top :"+s.peek());
}
}
마찬가지로 Stack을 임폴트시켜줘야 사용가능하다.
차이점이라면 top이라는 이름을 peek라는 이름으로 사용한다는 점이다.
Java의 Generic은 프리미티브타입은 되지 않으므로 클래스형을 사용해줘야한다.
if __name__ == '__main__':
s = []
for i in range(11):
s.append(i)
print('top :' + str(s[len(s) - 1]))
print('empty :' + str(len(s) is 0))
print('size :' + str(len(s)))
s.pop()
print('pop-top :' + str(s[len(s) - 1]))
파이썬은 stack이 없기 때문에 직접 제작해야한다.
그러나 list에서 지원해주는 함수들이 워낙 stack같은 형태를 띄고있기에 그냥 list를 stack처럼 사용한다.
물론 클래스로 포팅해서 사용하고 싶다면 그래도 상관없지만 보편적으론 그렇게 사용하지는 않는다.
var Stack = require('stackjs');
var s = new Stack();
for(var i=0;i<=10;i++){
s.push(i);
}
console.log('top :'+s.peek());
console.log('empty :'+s.isEmpty());
console.log('size :'+s.size());
s.pop();
console.log('pop-top :'+s.peek());stackjs라는 모듈이 있으므로 이를 설치해서 사용하면된다.
단 알고리즘 테스트에서는 이 과정을 못할 확률이 있으므로 그 경우에는 어쩔수 없이 직접 만들어야한다.
알고리즘 문제에서도 스택문제는 꽤 단골문제 처럼 나온다.
보통의 경우 괄호에 관련된 문제가 나오면 십중 팔구는 스택문제이다.
백준 문제중에서도 유명한 문제들이 있다.
백준 괄호(9012)
백준 쇠막대기(10799)
백준 괄호의 값(2504)
백준 괄호 제거(2800)
여러 문제들중에서 유독 괄호관련된 문제들은 스택과 연결되어있다.
아닌 문제도 있을수야 있겠지만 스택을 사용하지 않는 괄호문제는 매우 적다.
보통 괄호문제를 내는 의도가 스택을 써라는 개념이 크다.
스택을 사용해서 괄호문제를 푸는 이유는 스택의 특성때문이다.
스택은 마지막에 들어온걸 순서대로 지우다보니 쌍을 지우기가 쉽다.
괄호는 보통 쌍으로 나오기 때문에 이를 순서대로 지우는 것이다.
즉 특정 쌍을 손보는 문제에서는 스택이 제격이라는 것이다.
백준 스택(10828)
백준 스택수열(1874)
혹은 노골적으로 스택의 특성을 묻는 문제들 역시 많다.
이런 문제들은 스택에 대해서 이해도만 있다면 굉장히 쉽게 풀 수 있으므로 스택을 이해하는 시점에서 풀어보면 좋을 문제들이다.
백준 탑(2493)
이런 문제들이 스택에서는 조금 껄끄러운 문제다.
이런 문제가 껄끄러운 이유는 이 문제가 스택을 써야하는 문제인지 아닌지를 한눈에 보고 판단하기 힘들기 때문이다.
이 문제가 스택문제라는 생각을 가지고 접근한다면 스택을 이용해서 굉장히 쉽게 풀 수 있는 문제이다.
그러나 그런 생각을 하기 힘들다는게 문제이다.
어쨋던 스택의 성질을 잘 활용한 좋은 문제라고할 수 있다.