LIFO(Last-in-first-out) - 후입선출
FIFO(First-in-first-out) - 선입선출
스택의 개념과 원리
- push
- pop
- top
배열을 이용한 스택 객체 구조
- stack[] -> 스택의 원소들이 저장되는 배열
- topIndex -> 스택 탑 원소 자리의 인덱스
- push() -> 스택의 맨 위에 원소 x를 삽입한다
- pop() -> 스택의 맨 위에 있는 원소를 알려주고 삭제한다
- top() -> 스택의 맨 위에 있는 원소를 알려준다
- isEmpty() -> 스택이 비었는지 알려준다
- popAll() -> 스택을 깨끗이 청소한다
package stack;
public interface StackInterface<E> {
public void push(E newItem);
public E pop();
public E top();
public boolean isEmpty();
public void popAll();
}
public class ArrayStack<E> implements StackInterface<E> {
private E stack[];
private int topIndex; // 스택의 탑 인덱스
private static final int DEFAULT_CAPACITY = 64;
private final E ERROR = null; //임의의 에러 값
public ArrayStack() {
stack =(E[]) new Object[DEFAULT_CAPACITY];
topIndex = -1;
} //생성자 1
public ArrayStack(int n) {
stack = (E[]) new Object[n];
topIndex = -1;
} // 생성자 2
// 스텍에 원소 x 삽입하기
public void push(E newItem) {
stack[++topIndex] = newItem;
}
//스택에서 원소 삭제하기
public E pop() {
if (isEmpty()) return ERROR;
else return stack[topIndex--];
}
//스택 탑 원소 알려주기
public E top() {
if (isEmpty()) return ERROR;
else return stack[topIndex];
}
// 스택이 꽉 찼는지 확인하기
public boolean isEmpty() {
return(topIndex<0);
}
// 스택이 비었는지 확인하기
public boolean isFull() {
return (topIndex == stack.length-1);
}
// 스택 비우기
public void popAll() {
stack = (E[]) new Object[stack.length];
topIndex = -1;
}
}
연결리스트 스택 객체 구조
- topNode -> 스택 탑 원소를 가리키는 래퍼런스
- push() -> 스택의 맨 위에 원소 x를 삽입한다
- pop() -> 스택의 맨 위에 있는 원소를 알려주고 삭제한다
- top() -> 스택의 맨 위에 있는 원소를 알려준다
- isEmpty() -> 스택이 비었는지 알려준다
- popAll() -> 스택을 깨끗이 청소한다
배열을 이용한 스택 구조와 다른점: 배열 스택에서는 삽입 시 스택이 꽉 차 있으면 삽입을 못 했는데 연결 리스트 스택에서는 노드를 만들어 붙이므로 삽입을 못 하는 경우는 없다. 새로 만든 노드를 newNode 라고 함.
push(x):
newNode.item <- x
newNode.next <- topNode
topNode <- newNode
스택에서 삽입할때는 항상 맨 앞에서 일어나기에 topNode 로 래퍼런스가 되어있음
package stack;
import list.Node;
public class LinkedStack<E> implements StackInterface<E> {
private Node<E> topNode;
private Final E ERROR = null;
public LinkedStack() {
topNode = null;
}
//스택에 원소 x 삽입하기
public void push(E newItem) {
topNode = new Node<>(newItem, topNode);
}
//스택에서 원소 삭제하기
public E pop() {
Node<E> temp = topNode;
topNode = topNode.next;
return temp.item;
}
//스택 탑 원소 알려주기
public E top() {
return topNode.item;
}
//스택이 비었는지 확인하기
public boolean isEmpty() {
return (topNode ==null);
}
//스택 비우기
public void popAll() {
topNode = null;
}
클래스 '연결 리스트' 상속
5장에서 만들어 놓은 클래스 LinkedList<E>를 상속받아 재사용한다
public class inheritedStack<E> extends LinkedList<E> implements StackInterface<E> {
스택 응용
1. 문자열 뒤집기
- 스택의 특성을 이용해 문자열을 스택에 넣고 반대로 빼면서 나열하면 처음 문자열의 뒤집힌 형태가 나오게 된다.
package stack;
public class ReverseString {
public static void main(String[]args) {
String input = "Test seq 12345";
String t = reverse(input);
System.out.println("input string: " + input);
System.out.println("Reversed string; " + t);
}
private static String reverse(String s) {
ArrayStack<Character> st = new ArrayStack<>(s.length());
for(int i = 0; i< s.length(); i++)
st.push(s.charAt(i)); // s의 i번 문자. 번호는 0부터 시작
String output = "";
while(!st.isEmpty())
output = output + st.pop();
return output;
}
}
Postfix 계산
예시)
47* = 4*7
472+* = 4*(7+2)
47*20-=(4*7)-20
347*2/+ = 3+((4*7) /2)
1. 문자가 숫자 -> push()통해 스택에 삽입
2. 문자가 연산자 -> 스택의 맨 위에 있는 수 2개 pop 계산 후 스택에 push
3. 공백이면 무시
package stack;
public class PostfixEval {
public static void main(String[] args) {
String postfix = "700 3 47 + 6*-4/";
System.out.println("input string: " + postfix);
int answer = evaluate(postfix);
System.out.println("Answer: " + answer);
}
private static int evaluate(String postfix) {
int A, B;
LinkedStack<integer> s = new LinkedStack<>();
boolean digitPreviously = false;
for (int = 0; i < postfix.length(); i++) {
char ch = postfix.charAt(i);
if (Character.isDigit(ch)) {
if (digitPreviously == true) {
int tmp= s.pop();
tmp = 10*tmp + (ch-'0');
s.push(tmp);
} else s.push(ch-'0');
digitPreviously = true;
} else if (isPperator(ch)) {
A = s.pop();
B = s.pop();
int val = operation (A, B, ch);
s.push(val);
digitPreviously = false;
} else digitPreviously = false;
}
return s.pop();
}
private static int operation (int a, int b, char ch) {
int val = 0;
switch (ch) {
case'*':
val = b*a;
break;
case '/':
val = b/a;
break;
case '+':
val = b + a;
break;
case '-':
val = b-a;
break;
}
return val;
}
private static boolean isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch== '/';
}
}