스택의 정의와 연산
- 스택은 선입후출(FILO) 또는 후입선출(LIFO)의 특징을 가지는 자료구조로 나중에 들어온 데이터가 먼저 나가는 특징이 존재하는 자료구조이다.
- 이를 다른 말로 하면 한 곳(Tail)에서만 삽입과 삭제 연산이 일어나는 자료구조이다.
- 일반적으로 들어온 인풋의 역순으로 연산이 진행되어야 하는 경우 스택을 사용할 수 있다.
- 스택의 연산은 일반적으로 다음과 같이 나열할 수 있다.
- 데이터의 추가
- 데이터의 제거
- 데이터의 조회
- 스택의 상태(비어있는지)
스택의 구현 방법
- 스택은 배열과 리스트로 구현할 수 있다. 배열과 리스트의 장 단점은 각각 다른데 배열의 초기 길이를 변경하지 못한다는 크리티컬한 단점으로 인해 일반적으로 연결 리스트를 이용하여 구현하게 된다.
- 이번에도 Node Pool을 이용한다. Node 클래스의 경우 연결 리스트 구현에서도 적은 적이 있는 만큼 생략하고 넘어가도록 한다.
- 그리고 우리가 구현할 연산들을 메서드 형태로 구현해놓는다.
class Stack{
private static final int MAX_NODE = 10001;
int nodeCnt;
Node[] nodePool;
Node head;
Stack(){
nodePool = new Node[MAX_NODE];
nodeCnt = 0;
head = new Node(-1);
}
Node getNode(int data){
nodePool[nodeCnt] = new Node(data);
return nodePool[nodeCnt++];
}
void addLast(int data){
}
int pop(){
}
int peek(){
}
boolean isEmpty(){
}
int size(){
}
}
스택의 구현 - 데이터 삽입
- 스택에서 데이터의 삽입과 삭제는 연결 리스트의 끝 부분에서 일어난다. 즉 데이터의 삽입은 연결 리스트에서 맨 마지막 노드 뒤에 데이터를 삽입하는 연산과 완벽히 동일하다.
void addLast(int data){
Node newNode = getNode(data);
Node start = head;
while(start.next != null){
start = start.next;
}
start.next = newNode;
}
- 동작 원리와 구현이 완벽히 동일하므로 이 이상의 설명은 하지 않겠다.
스택의 구현 - 데이터 삭제
- 데이터의 삭제 역시 연결 리스트의 끝 부분에서만 일어난다.
- 우리는 이전에 데이터를 입력받아 그 데이터와 동일한 데이터를 가진 노드를 삭제하는 연산을 구현했지만 이번에는 리스트의 맨 마지막 노드를 삭제하는 것만 구현하면 된다.
- 이는 리스트의 순회를 이용해 마지막 노드 바로 이전의 노드를 가리키도록 위치를 잡고 이전 노드의 next를 null로 바꿔줌으로서 완료된다.
int pop(){
if(isEmpty()){
return -1;
}
Node start = head;
Integer ret = null;
while(start.next.next != null){
start = start.next;
}
ret = start.next.data;
start.next = null;
nodeCnt--;
return ret;
}
- 이번에는 어떤 제약조건 없이 구현하는 것이기 때문에 스택이 비어있을 때 pop 연산이 실행될 상황도 고려해야 한다.
스택의 구현 - 데이터의 조회
- 데이터의 조회 연산은 값만 가져오고 해당 데이터를 삭제하지 않는 것을 의미하며 리스트의 순회를 통해 마지막에 있는 값을 가져오는 것으로 구현이 가능하다.
int peek(){
if (isEmpty()){
return -1;
}
Node start = head;
while(start.next != null){
start = start.next;
}
return start.data;
}
스택의 구현 - 스택의 상태 조회
- 스택이 비어있는지와 그 크기는 우리가 Stack 클래스에 포함시킨 nodeCnt를 사용하여 손쉽게 구현이 가능하다.
boolean isEmpty(){
return this.nodeCnt == 0;
}
int size(){
return this.nodeCnt;
}
정리
- Stack의 구현은 연결 리스트의 구현만 제대로 마쳐놓는다면 매우 쉬운 일이 될 것이다. 지금은 단방향 연결 리스트를 사용하여 구현하였기 때문에 리스트의 맨 끝까지 순회하여 가는데 걸리는 시간만큼 손해를 보게 된다.
- 이는 양방향 연결 리스트를 통해 해결이 가능하다. 사실 양방향을 구현하지 않더라도 맨 끝을 계속 가리키고 있는 포인터 peek만 잡아 주어도 순회와 관련된 연산이 제거될 것이다. 이것을 사용하여 구현하는 것은 여러분의 몫으로 남기도록 하겠다.
- Java에서 Stack은 Stack클래스가 존재하며 이를 이용해 구현할 수 있지만 Stack 클래스는 Vector클래스를 상속받아 확장한 형태이며 Vector 클래스 자체가 문제가 많은 컬렉션 클래스이기 때문에 잘 사용되지 않는다. 이후에 우리가 배울 Deque클래스를 사용해 일반적으로 구현한다.
- 전체적인 코드와 테스트 코드는 다음과 같다.
class Node{
int data;
Node next;
Node(int data){
this.data = data;
this.next = null;
}
}
class Stack{
private static final int MAX_NODE = 10001;
int nodeCnt;
Node[] nodePool;
Node head;
Stack(){
nodePool = new Node[MAX_NODE];
nodeCnt = 0;
head = new Node(-1);
}
Node getNode(int data){
nodePool[nodeCnt] = new Node(data);
return nodePool[nodeCnt++];
}
void addFirst(int data){
Node newNode = getNode(data);
newNode.next = head.next;
head.next = newNode;
}
void addLast(int data){
Node newNode = getNode(data);
Node start = head;
while(start.next != null){
start = start.next;
}
start.next = newNode;
}
int pop(){
if(isEmpty()){
return -1;
}
Node start = head;
Integer ret = null;
while(start.next.next != null){
start = start.next;
}
ret = start.next.data;
start.next = null;
nodeCnt--;
return ret;
}
int peek(){
if (isEmpty()){
return -1;
}
Node start = head;
while(start.next != null){
start = start.next;
}
return start.data;
}
boolean isEmpty(){
return this.nodeCnt == 0;
}
int size(){
return this.nodeCnt;
}
}
public class UserSolution{
public static void main(String[] args){
Stack stack = new Stack();
stack.addLast(1);
stack.addLast(2);
stack.addLast(3);
stack.addLast(4);
stack.addLast(5);
System.out.println(stack.peek());
System.out.println(stack.size());
System.out.println(stack.isEmpty());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.size());
System.out.println(stack.peek());
stack.pop();
stack.pop();
System.out.println(stack.isEmpty());
}
}