✅ 자료구조 : 데이터를 저장하는 방식
✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조
랜덤 접근 불가능?
모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들
스택 (Stack)
먼저 들어간 자료가 나중에 나오는 LIFO(Last In First Out) 자료구조. 즉, 한 쪽 끝에서만 자료를 넣고 뺄 수 있음
스택의 추상화 연산
- push(item) : item 하나를 스택의 가장 윗부분에 추가
- pop() : 스택에서 가장 위에 있는 항목 제거
- peek() | top(): 스택의 가장 위에 있는 항목을 반환
- isEmpty() : 스택이 비어 있을 때 true 반환
- isFull() : 스택이 가득 차 있을 때 true 반환
- getSize() : 스택에 있는 요소 수 반환
스택의 구현
1. 배열을 이용한 구현(기본)
#define STACK_SIZE 500
int arr[STACK_SIZE]; //스택의 최대 크기는 500
int top = 0; //스택의 현재 크기는 0
int push(int n)
{
if (top>=STACK_SIZE) return -1;
arr[top++] = n;
return 0;
}
int pop()
{
if (top<=0) return -1;
return arr[--top];
}
2. LinkedList로 구현
LinkedList로 스택을 구현하려면 Node를 만들어야 한다.
Node : 데이터와 다음 데이터를 가르키는 주소로 구성
Node Manager : 노드를 관리하여 스택을 구현하는 클래스. push, pop, peek의 역할을 함.
public class Node {
private int item;
private Node node;
public Node(int item) {
this.item = item;
this.node = null;
}
protected void linkNode(Node node) {//나를 가르킬 노드를 지정
this.node = node;
}
protected int getData() {
return this.item;
}
protected Node getNextNode() { //다음 노드를 리턴
return this.node;
}
}
//LinkedListStack을 관리하는 클래스
public class NodeManager {
Node top; //가장 최근에 들어온 노드를 가리킴
public NodeManager() {
this.top = null;
}
public void push(int data) {
Node node = new Node(data); //노드 생성
node.linkNode(top); //새로 생성된 노드가 top이 가르키는 노드를 링크로 연결
top = node; //top의 값을 가장 최근에 생성된 node로 바꿈
}
public void pop() {
top = top.getNextNode(); // 현재 top이 가리키고 있는 노드를 가리키게 함
}
public int peek() {
return top.getData();
}
}
3. 배열과 리스트 구현의 차이
| 배열 스택 | LinkedList 스택 | |
| 장점 | 구현이 빠르고, 데이터의 접근 속도가 빨라서 조회가 빠르다. |
크기(데이터의 양)가 한정되어 있지 않고, 삽입 및 삭제가 용이하다. |
| 단점 | 배열의 크기가 정해져 있다. 실제 프로젝트에서 사용하기에 좋지 않다. |
구현이 어렵고, 조회가 힘들다. 포인터를 위한 추가 메모리 공간이 필요하다. |
4. java 라이브러리 스택(Stack) 관련 메서드
- push(E item)
- 해당 item을 Stack의 top에 삽입
- Vector의 addElement(item)과 동일
- pop()
- Stack의 top에 있는 item을 삭제하고 해당 item을 반환
- peek()
- Stack의 top에 있는 item을 삭제하지않고 해당 item을 반환
- empty()
- Stack이 비어있으면 true를 반환 그렇지않으면 false를 반환
- search(Object o)
- 해당 Object의 위치를 반환
- Stack의 top 위치는 1, 해당 Object가 없으면 -1을 반환
스택의 사용 사례
- 재귀 알고리즘을 반복문을 통해서 구현할 수 있게 해줌
- 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
- 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
- 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
- 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
- 실행 취소 (undo)
- 웹 브라우저 뒤로가기
- 구문분석
- 후위(postfix) 표기법 연산
- 문자열의 역순 출력 등
참고
- https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html
- https://go-coding.tistory.com/5
- https://librewiki.net/wiki/%EC%8B%9C%EB%A6%AC%EC%A6%88:%EC%88%98%ED%95%99%EC%9D%B8%EB%93%AF_%EA%B3%BC%ED%95%99%EC%95%84%EB%8B%8C_%EA%B3%B5%ED%95%99%EA%B0%99%EC%9D%80_%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B3%BC%ED%95%99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B8%B0%EC%B4%88
- https://yoongrammer.tistory.com/45
