스택(Stack)은 데이터를 임시로 저장하기 위한 자료구조 중 하나이며, 마지막으로 삽입된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last-In-First-Out) 구조를 가지고 있다.
마치 상자에 책을 쌓아서 넣고 빼는 형식과 같다.
스택 기본 연산
스택 시간 복잡도
접근 | 검색 | 삽입 | 삭제 |
---|---|---|---|
O(n) | O(n) | O(1) | O(1) |
스택의 활용
수식계산, 수식괄호검사, 함수 콜 스택, 인터럽트 처리
워드프로세서의 undo/redo, 뒤로가기/앞으로가기 : 스택2개사용하거나 포인터 사용
자바에서 스택 구현 방법
1.클래스 사용
public class Stack {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
System.out.println(stack.peek());
}
}
2.배열 사용 (스택에 효율적)
0 1 2 3 4 로 저장하면 마지막 데이터인 4부터 삭제하게 되니 배열 이동이 필요 없다
class MyStack {
ArrayList list;
MyStack() {this.list = new ArrayList();}
public boolean isEmpty() {
if (this.list.size()==0) {
return true;
}
return false;
}
//Push() 구현
public void push(int data) {
this.list.add(data);
}
//pop() 구현
public Integer pop() {
if (this.isEmpty()) {
System.out.println("Stack is empty");
return null;
}
int data = (int) this.list.get(this.list.size()-1);
this.list.remove(this.list.size()-1);
return data;
}
//peek()구현
public Integer peek() {
if (this.isEmpty()) {
System.out.println("Stack is empty");
return null;
}
int data = (int) this.list.get(this.list.size()-1);
return data;
}
//스택 출력
public void printStack() {
System.out.println(this.list);
}
}
3. 연결 리스트 (큐에 효율적)
0 1 2 3 4로 저장하면 0번부터 삭제하게 되니 만약 배열이라면 0을 삭제 후 뒷 데이터들을 앞으로 이동시켜줘야한다. 하지만 연결 리스트는 연결만 바꿔주면 되기 때문에 편하다.
FIFO(First In First Out) 먼저 들어온 데이터가 먼저 나가게 되는 것
큐의 활용
최근 사용문서 : 최근 사용문서를 보여줌, 새로운 문서를 열면 가장 오래된 문서를 기록에서 지운다.
프린터 대기목록, 버퍼(buffer), BFS(Breath-First Search)
큐의 기본연산
예외발생X
예외발생O
큐의 시간복잡도
접근 | 검색 | 삽입 | 삭제 |
---|---|---|---|
O(n) | O(n) | O(1) | O(1) |
Stack은 클래스라서 객체 생성이 가능하다. 하지만 Queue는 인터페이스 구성이라 객체 생성이 불가능하다.
(⇒ Queue q = new Queue(); 객체 생성 불가)
Queue를 구현한 클래스는 인터페이스 Queue의 추상 메소드를 모두 사용할 수 있기 때문에 이를 찾아서 사용한다.
ex) LinkedList, ArrayDeque
Queue q = new LinkedList();
Queue q = new ArrayDeque();