0. 개요
배열과 리스트에 대한 정리가 끝났으니, 다음 자료구조는 스택과 큐이다. 그 중 스택을 먼저 정리하려고 한다.
1. Stack
스택의 구조는 간단하다. LIFO(Last In First Out)가 핵심이다. 이것을 알고 있다면 이미 스택에 대해서 99.9%는 이해했다고 생각해도 무방하다. 스택에서는 push를 할 경우 스택에 데이터가 쌓이고, pop을 할 경우에는 가장 최근에 push된 데이터를 꺼내는 구조이다. 그리고 peek을 하게 되면 스택에 최 상위 top에 있는 데이터의 정보를 읽어올 수 있다.
스택의 기능을 명세한 인터페이스
스택이 가지고 있는 기능의 핵심을 명세했다.
push: data를 스택에 집어 넣는다.
pop: 가장 최근에 넣은 데이터를 스택에서 꺼낸다.
peek: 가장 최근에 넣은 데이터를 꺼내지 않고 읽어온다.
size: 스택의 크기를 int 값으로 반환.
isEmpty: 스택이 비어있는지 boolean 값으로 반환.
public interface IStack<T> {
void push(T data);
T pop();
T peek();
int size();
boolean isEmpty();
}
스택 인터페이스를 바탕으로 구현한 스택
public class MyStack<T> implements IStack<T> {
private int size;
private Node head;
public MyStack() {
this.size = 0;
this.head = new Node(null);
}
@Override
public void push(T data) {
Node node = new Node(data, this.head.next);
head.next=node;
size++;
}
@Override
public T pop() {
if(isEmpty()){
return null;
}
Node curr = head.next;
head.next=curr.next;
curr.next=null;
size--;
return curr.data;
}
@Override
public T peek() {
if(isEmpty()){
return null;
}
return head.next.data;
}
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return head.next==null;
}
private class Node {
T data;
Node next;
Node(T data) {
this.data = data;
}
Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
}
2. 시간복잡도
자료구조 | 접근 | 탐색 | 삽입 | 삭제 | 비고 |
스택 | O(n) | O(n) | O(1) | O(1) | 링크를 타고 순회 |
1) 접근
스택에서 원하는 데이터에 접근한다고 가정했을 때 그 데이터가 맨 처음 넣은 데이터 일 경우 n번 pop을 해야하기 때문에 시간복잡도는 O(n)
2) 탐색
접근과 마찬가지로 탐색 한다고 했을 때 모든 노드를 순회해야할 수 있으므로 시간복잡도는 O(n).
3) 삽입, 삭제
스택은 LIFO이기 때문에 삽입삭제는 맨 마지막에 삽입하거나, 맨 마지막에 들어온 데이터를 삭제하게 된다. 이 경우는 한번만 연산을 실행하면 되므로 시간복잡도는 O(1).
3. 정리
스택은 맨 나중에 들어온 데이터가 맨 처음 나오는 LIFO 구조이며, 재귀를 사용하는 함수나 알고리즘에 사용되며 웹브라우저 방문기록 등에 사용된다.
구현된 push, pop, peek, isEmpty, size 메서드를 잘 이용하기만 한다면 스택을 사용하는 것에는 크게 문제가 없을 듯 하다. 이 스택이라는 자료구조를 이해하고, 어디에 응용할 수 있는지 문제를 풀어보면서 경험을 쌓는 것이 중요할 듯 하다.
참조
면접을 위한 CS 전공지식 노트
야놀자 테크스쿨 패스트캠퍼스 온라인 강의 - 자료구조/알고리즘
'야놀자 테크스쿨 > JAVA 자료구조' 카테고리의 다른 글
[면접을 위한 CS 전공지식 노트][자료구조] Tree(트리) (0) | 2023.08.04 |
---|---|
[면접을 위한 CS 전공지식 노트][자료구조] Queue(큐) (0) | 2023.08.03 |
[면접을 위한 CS 전공지식 노트][자료구조] 연결리스트 LinkedList (0) | 2023.08.02 |
[면접을 위한 CS 전공지식 노트][자료구조] Array(배열)와 ArrayList (0) | 2023.08.02 |
[면접을 위한 CS 전공지식 노트][자료구조] 자료구조에 따른 시간 복잡도 (0) | 2023.07.31 |