자료구조
스택을 간단하게 알아보자
이재빵
2021. 9. 6. 14:49
728x90
스택의 사용 사례
- 재귀 알고리즘
- 웹브라우저 뒤로가기
- 실행취소
- 괄호검사
- 후위표기법
- dfs(깊이우선탐색)
배열
static int[] stack;
static int size = 0;
static void push(int item){
stack[size++] = item;
}
static int pop(){
if(size==0)
return -1;
int res = stack[size-1];
stack[size-1] = 0;
size--;
return res;
}
static int size(){
return size;
}
static int empty(){
if(size==0)
return 1;
return 0;
}
static int top(){
if(size==0)
return -1;
return stack[size-1];
}
연결리스트
import java.util.EmptyStackException;
public class MyStack {
private Node top;
public MyStack() {
this.top = null;
}
public class Node {
private String data;
private Node nextNode;
public Node(String data) {
this.data = data;
this.nextNode = null;
}
}
public String push(String data) {
Node node = new Node(data);
node.nextNode = top;
top = node;
return data;
}
public String pop() {
String data = peek();
top = top.nextNode;
return data;
}
public String peek() {
if (top == null)
throw new EmptyStackException();
return top.data;
}
public boolean empty() {
return top == null;
}
public int search(Object o) {
int index = 1;
Node tempTop = top;
while (tempTop != null) {
if (tempTop.data.equals(o))
return index;
tempTop = tempTop.nextNode;
index++;
}
return -1;
}
}