[자료구조] 선형 자료구조 - 2. 랜덤 접근 불가능 - 스택(Stack)

이진이·2023년 8월 10일

data structure

✅ 자료구조 : 데이터를 저장하는 방식

✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조

랜덤 접근 불가능?

모든 자료에 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) 표기법 연산
문자열의 역순 출력 등