[자료구조] Stack(스택)
이번 시간에는 Stack 자료구조에 대해서 배워 볼 것이다.
스택(Stack)이란?
stack은 후입선출(Last-In-First-Out - LIFO)의 대표적인 선형 자료구조 중의 하나이다.
후입선출이란 ‘Last-In-First-Out’이라는 뜻 그대로 ‘나중에 들어온 데이터가 가장 먼저 나간다’ 의 의미를 가지고 있다.
그 예로 인터넷 브라우저에서 뒤로 가기 기능같은 경우 그 버튼을 눌렀을 때 가장 최근의 페이지가 나오는데 이 역시 가장 나중에 들어간 페이지가 가장 먼저 나오는 것이기 때문에 스택 구조라고 할 수 있다.
또한, Ctrl + z 와 같은 실행 취소 기능역시 제일 나중에 했던 동작을 취소하는 것이므로 스택 구조라고 볼 수 있습니다.
위 그림은 스택의 구조를 시각화한 자료이다.
흔히 스택은 접시쌓기를 생각하면 이해하기 편하다. 가장 마지막에 내려놓은 접시를 가장 먼저 빼야지 쌓아놓은 접시들이 무너지지 않겠지 않는가?
이때, 접시(데이터)를 넣는 작업을 Push, 접시를 빼는 작업을 Pop이라고 한다.
또한 스택은 완전히 꽉 찼을 때 Overflow상태라고 하고, 완전히 비어 있으면 Underflow상태라고 한다.
그럼 연산 메소드에 대해 자세히 알아 보자.
연산 메소드, 추상 자료형(ADT)
스택은 아래와 같은 연산 메소드들로 추상화할 수 있다.
- push() - 데이터를 가장 위에 추가하는 작업
- pop() -가장 위의 데이터를 삭제하면서 그 데이터를 읽어오는 작업
- top(), peek() - 구조는 그대로 둔 채 가장 위의 데이터를 읽어오는 작업
- isEmpty() - 스택이 비어있는 지 확인하는 작업
- isFull() - 스택이 꽉 차있는 지 확인하는 작업
- size(), getSize() - 스택에 있는 요소(element)의 수를 반환하는 작업(크기를 반환)
스택의 과정
Push(데이터 삽입)
push는 스택 구조에 데이터를 넣는 작업을 말한다. push는 다음 과정으로 진행된다.
- 스택이 꽉차 있는지 확인
- 스택이 꽉차 있다면 오류 발생 후 종료
- 2번의 경우가 아니라면 Top을 증가
- Top이 가리키는 스택 위치에 데이터 삽입
위 의 그림처럼 Top은 항상 스택구조에서 위에 위치한 데이터를 가리키는 변수로 데이터를 뺄 때는 top이 빠지는 것이다.
pop(데이터 꺼내오기, 추출)
많은 사람들이 pop을 데이터를 제거하는 과정이라고 하는데 그것도 틀리지는 않지만 더 정확히 말하자면 추출에 좀 더 가깝다. 실제로 pop메소드 실행시 제거한 데이터를 반환까지 하기 때문에 제거라고만 하기엔 뭔가 허전하다.
그렇다면 데이터를 꺼내서 가져오는 pop과정에 대해서 알아보자. 기본적으로 pop은 스택에 있는 데이터를 추출하여 가져오는 것으로 다음 과정을 거친다.
- 스택이 비어 있는지 확인
- 스택이 비어 있으면 오류 발생 후 종료
- 2번의 경우가 아니라면 Top이 가리키고 있는 데이터를 스택에서 제거
- Top 값을 바로 아래 위치로 가도록 감소
- 제대로 이루어 졌다면 해당 데이터 반환
시간 복잡도
| 연산 | 평균 소모 시간 | 최악 소모 시간 |
|---|---|---|
| Access | O(n) | O(n) |
| Search | O(n) | O(n) |
| Push(Insert) | O(1) | O(1) |
| Pop(Delete) | O(1) | O(1) |
스택에서 데이터의 삽입, 삭제, isEmpty, peek 연산은 모두 O(1)의 시간 복잡도를 갖는다.
- 삽입, 삭제와 같은 것들은 항상 Top에서만 일어나기 때문(특정 index를 찾아 들어가야 할 필요가 없음)
Stack 구현
스택을 구현하는 방법에는 배열을 사용하는 방법과 LinkedList를 사용하는 방법이 있다.
-
배열 사용:
장점
- 구현하기가 쉽다.(logic 상으로)
- 자료를 넣고 뺄 때 기존의 자료들의 위치를 변경할 필요가 없다.
- 삽입/추출 시 O(1)의 시간 복잡도만을 요구한다.
단점
크기가 동적으로 할당되는 것이 아니고 런타임 시 필요에 따라 늘어나거나 줄어들지 않는다.
-
연결 리스트 사용:
장점
- 크기가 동적이다.
- 런타임 시 필요에 따라 크기가 확장 되거나 축소 될 수 있다.
- 마지막에 넣은 자료를 삽입 혹은 추출 시, 기존의 마지막에 넣어져 있던 자료(tail)와의 상호 연결된 prev/ next pointer의 연결만 바꾸어 주면 되기 때문에 삽입/추출 시 O(1)의 시간 복잡도를 요구한다.
단점
포인터(노드)를 위한 추가 메모리 공간이 필요하다.
배열로 구현 시 순서가 중요하기 때문에 top이란 변수가 굉장히 중요하게 작용하지만 연결리스트로 구현 시 이 변수가 그렇게 중요하지 않다.
나는 자바의 강점을 살려 노드로 구현을 해 보도록 할 것이다.
IStack.java
package stack;
public interface IStack<T> {
void push(T data);
T pop();
T peak();
int size();
}
IStack이라는 interface에 push(), pop(), peak(), size() 메소드들을 정의하였음.
MyStack.java
package stack;
public class MyStack<T> implements IStack<T> {
...
}
MyStack 클래스에서 IStack을 구현상속 할 것이다.
노드 클래스
private class Node {
T data;
Node next;
Node(T data) { this.data = data; }
Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
먼저 stack도 마찬가지로 노드를 기반으로 하여 구현할 것이기 때문에 지난 시간에 만들었던 Node 클래스를 가져온다.
**지난 시간 포스팅 참조
멤버변수
스택의 크기 변수와 head 노드를 멤버 변수로 선언한다.
private int size;
private Node head;
생성자
위에서 선언한 멤버변수의 값을 초기화 시켜준다.
head 노드를 null로 초기화 시키는 것도 가능하지만 그렇게 되면 코드가 나중에 복잡해 질 가능성이 있기 때문에 새로운 null 노드 객체를 생성시켜 대입하였다.
public MyStack() {
this.size = size();
this.head = new Node(null);
// this.head = null; 코드가 복잡해 질 수 있다.
}
push
새로 push할 노드를 생성하는데 이 노드의 next pointer가 가리키고 있는 노드는 head노드의 next pointer가 가리키고 있던 노드를 가리키게 된다.
그 후 head 노드의 next pointer는 새로운 노드를 가리키게 해 주고, 스택의 크기를 1 증가시키면 된다.
이로써 head next pointer는 항상 새로 들어온 노드를 가리키는 것을 알 수 있다.
@Override
public void push(T data) {
Node node = new Node(data, this.head.next);
this.head.next = node;
this.size++;
}
pop
head노드의 next pointer가 가리키는 노드는 항상 스택 맨 위에 있는 노드(Top)이기 때문에 이를 curr 노드로 지정하고 head 노드의 next pointer를 curr 노드의 다음 노드와 연결한다.
그 이후 curr 노드의 next pointer 연결을 null로 초기화 시켜 끊어주고 스택의 size를 1 감소 시킨다.
pop()연산은 스택의 데이터를 삭제하면서 그 삭제한 데이터를 가져오는 것이기 때문에 curr의 데이터를 반환한다.
단, 스택이 비어있는 경우 가져올 데이터 혹은 노드가 없기 때문에 반환할 객체가 없으므로 null 객체를 리턴한다.
@Override public T pop() {
if (this.isEmpty()) {
return null;
}
Node curr = this.head.next;
this.head.next = curr.next;
curr.next = null;
this.size--;
return curr.data;
}
peak
peak() 연산은 스택의 구조를 건들이지 않고 가장 꼭대기의 값을 가져오는 것이기 때문에 head 노드의 next pointer가 가리키고 있는 노드(Top)의 data만을 그대로 return 하면 된다.
이 역시도 스택이 비어있는 경우에는 리턴할 객체가 없기 때문에 null을 반환해 줍니다.
@Override
public T peek() {
if (this.isEmpty()) {
return null;
}
return this.head.next.data;
}
size
@Override
public int size() {
return this.size;
}
size()는 언제나 그랬듯이 간단하게 멤버변수 size를 리턴해 주면 됩니다.
이렇게 스택의 각 연산에 대해서 알아 보았다. 이 역시도 노드를 통해 이루어진 자료구조이지만 일반적인 연결리스트와는 데이터의 삽입, 삭제 방식(코드 구현)이 더 간편하다고 볼 수도 있다.
관련된 문제
챕터 3에서 배운 스택과 관련된 풀어 볼 만한 문제는 백준 사이트의 9012번 괄호 문제가 있다.
이상 스택 자료구조에 대한 내용이었습니다.
자료구조 시간 복잡도 비교
- 평균 시간 복잡도(Average)
| 자료구조 | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Singly Linked List | O(n) | O(n) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) |
| Hash Table | O(1) | O(1) | O(1) | O(1) |
| Binary Search Tree | O(log2n) | O(log2n) | O(log2n) | O(log2n) |
| AVL Tree | O(log2n) | O(log2n) | O(log2n) | O(log2n) |
| B Tree | O(log2n) | O(log2n) | O(log2n) | O(log2n) |
- 최악의 경우 시간 복잡도(Worst)
| 자료구조 | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Singly Linked List | O(n) | O(n) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) |
| Hash Table | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(n) | O(n) | O(n) | O(n) |
| AVL Tree | O(log2n) | O(log2n) | O(log2n) | O(log2n) |
| Binary Tree | O(n) | O(n) | O(n) | O(n) |
| B Tree | O(log2n) | O(log2n) | O(log2n) | O(log2n) |
댓글남기기