Stack은 LIFO(Last In First Out) 형태의 자료 구조로, 마지막에 들어간 데이터가 먼져 출력되도록 하는 자료구조체이다. Array 나 Linked List로 구현 가능하다. 다음은 그 구현 코드이다.
[Array를 이용한 Stack 구현] public class ArrayStack { private Object[] mStackArray; private int mTop=0; private int mStackSize=0; public ArrayStack(int inStackSize){ mStackArray=new Object[inStackSize]; mStackSize=inStackSize; } public boolean push(Object inObject){ if(mTop==mStackSize-1) return false; else { mStackArray[mTop++]=inObject; return true; } } public Object pop(){ if(mTop==0) return null; else return mStackArray[--mTop]; } public int getStackSize(){ return mTop; } public static void main(String[] args) { ArrayStack stackExample=new ArrayStack(10); stackExample.push(new Integer(9)); stackExample.push(new Integer(8)); stackExample.push(new Integer(2)); stackExample.push(new Integer(4)); stackExample.push(new Integer(3)); stackExample.push(new Integer(5)); while(stackExample.getStackSize()>0){ System.out.println(stackExample.pop()); } } } |
[Linked List를 이용한 Stack] public class LinkedListStack { private class Node { Object mNodeData; Node mNextNode; public Node(Object inData){ mNodeData=inData; } } private Node mLastNode; private Node mTopNode; private int mStackSize=0; public LinkedListStack(){ mLastNode=null; } public void push(Object inObject){ Node newNode=new Node(inObject); if(mTopNode==null) { mLastNode=newNode; mTopNode=mLastNode; } else { mTopNode.mNextNode=newNode; mTopNode=newNode; } mStackSize++; } public Object pop(){ if(mLastNode==null) return null; else { Object returnObject=mLastNode.mNodeData; mLastNode=mLastNode.mNextNode; mStackSize--; return returnObject; } } public int getStackSize(){ return mStackSize; } } |
Stack은 컴퓨터에서 여러 용도로 사용된다. 대표적으로 후위 사직 연산에 사용 된다. 일반적으로 사칙 연산은 중위 표현, 다시 말해 연산자가 피연산자 가운데 위치한다. 예를 들어 1 + 5 * 3 - 2 와 같다. 후위 표기법은 연산자를 피연산자 뒤에 위치시키는 것이다. 1 + 5 * 3 - 2 는 후위표현하게 되면 1 5 3 * + 2 - 가 된다. Stack을 이용해서 이를 계산하는 방법은 피연산자를 만나면 스택에 집어 넣고 연산자를 만나면 스택에서 두 피연산자를 꺼내어 연산을 하고 다시 스택에 넣는 방법이다. 위의 예는 다음과 같이 연산된다.
문제는 중위 표현식을 후위 표현식으로 바꿔주는 것이 필요한데, Edsger Dijkstra가 고안한 다음의 알고리즘을 이용하면 된다.
1) 입력받은 중위 표기식에서 토큰을 읽는다.
2) 토큰이 피연산자이면 토큰을 결과에 출력한다.
3) 토큰이 연산자(괄호 포함)일 때, 이 토큰이 스택의 최상위 노드에 저장되어 있는 연산자보다 우선순위가 높으면(왼쪽괄호는 무조건 스택에 삽입) 스택에 삽입하고 그렇지 않으면 결과에 출력한다.
4) 토은이 오른쪽 괄호 이면 최상위 노드에 왼쪽 괄호가 올 때까지 스택에 제거 연산을 수행하고 제거한 노드에 담긴 연산자를 출력한다. 이떄 왼쪽 괄호를 만나면 제거만 하고 출력하지 않는다.
5) 중위 표기식에 더 읽을 것이 없다면 스택을 제거하여 출력하고, 더 읽을 것이 있으면 1부터 반복한다.
(1+3)*4 는 다음과 같이 처리 된다.
1) 왼쪽 괄호이므로 스택에 입력 (스택 상태: [(])
2) 1은 출력 (출력 상태: [1])
3) + 연산자이므로 스택에 삽입 (스택상태: [( + ])
4) 3은 출력 (출력 상태: [1 3])
5) 오른쪽 괄호 이므로 왼쪽 괄호가 올때까지 스택에서 제거하여 출력, 단 왼쪽 괄호는 출력하지 않음 (출력상태: [1 3 + ], 스택상태: [])
6) * 연산자이므로 스택에 삽입 (스택상태: [ * ])
7) 4는 연산자이므로 출력 (출력상태 [1 3 + 4 ])
8) 더이상 읽을 것이 없으므로 스택 제거하면서 출력 (출력 상태 [ 1 3 + 4 * ]
