자료구조 스터디 week4 - 스택

스택

스택이란 맨 위의 원소만 접근 가능한 자료구조를 말한다.

맨 위의 원소를 스택탑이라고 하며, 새로운 원소를 저장할 때는 스택 탑 바로 위에 원소를 저장하고, 원소를 삭제할 때는 무조건 탑에 있는 원소를 삭제한다.

https://velog.io/@ehddnr7355/%EC%8A%A4%ED%83%9DStack-%ED%81%90Queue

 

스택의 삽입과 삭제의 예시는 다음과 같다. 스택에서 삽입할 때는 아래부터 쌓고 삭제할 때는 맨 위의 원소를 삭제하게 된다.

 

메모리 구조에서의 스택

 

가상 메모리 구조

 

프로그램은 위와 같은 가상 메모리에서 수행된다는 가정하에 컴파일러가 컴파일 하고 물리적인 메모리에는 수행시점에 대응된다.(프로그램이 독립적으로 물리 메모리 크기에 구애받지 않고 실행된다는 뜻)

 

정적 영역에는 컴파일 직후 상대의 위치를 정할 수 있는 모든 정보(수행 코드, 데이터)가 있고, 동적 영역에는 프로그램 수행 중 할당 받는 메모리(힙)와 다른 함수를 호출할 때 정보를 저장하는 스택이 있다. 이때 함수들 중 main()함수는 정적 영역에 저장 된다.

 

<호출이 진행되는 구조>

main() {   ...   A();   ... }

A() {   ...   B();   ... }

B() {   ...   C();   ... }

C() {   ...   ...   ... }

 

 

배열리스트를 이용한 스택 구조

맨 위에서 언급했듯이, 스택의 맨 위쪽 원소를 스택 탑이라고 한다. 배열리스트에서는 이 스택 탑이라는 사실을 정확히 반영하기 위해 초기의 topIndex 값을 -1로 두고 원소가 들어올 때마다 1씩 증가시키는 구조를 띤다.

 

스택 탑 반영

 

스택에서는 ADT(추상 데이터 타입)을 이용하며 stack[], topIndex, 5개의 메소드로 구성된다.

 

스택 객체 구조

stack[] - 스택의 원소들이 저장되는 배열
topIndex - 스택 탑 원소 자리의 인덱스

push(x) - 스택의 맨 위에 원소 x를 삽입한다.
pop() - 스택 맨 위에 있는 원소를 알려주고 삭제한다.
top() - 스택의 맨 위에 있는 원소를 알려준다.
isEmpty() - 스택이 비었는지 알려준다.
popAll() - 스택을 깨끗이 청소한다.

 

스택 코드 구현

인터페이스

추상 데이터 타입 스택을 아래와 같이 인터페이스 기능을 이용하여 구체적으로 정의할 수 있다.

public interface StackInterface<E> {
    public void push(E newItem);
    public E pop();
    public E pop();
    public boolean isEmpty();
    public void popAll();
}

 

 

클래스

public class ArrayStack<E> implements StackInterface<E> {
    private E stack[];
    private int topIndex; // topIndex 선언
    private static final int DEFAULT_CAPACITY = 64; // 스택 용량
    private final E ERROR = null;
    
    // 초기 스택 생성
    public ArrayStack() {
        stack = (E[]) new Object[DEFAULT_CAPACITY];
        topIndex = -1;
    }
    
    // 초기 스택 생성2
    public ArrayStack(int n) {
        stack = (E[]) new Object[n];
        topIndex = -1;
    }
    
    // push
    public void push(E newItem) {
        if (isFull()) { /* ERROR : stackOverFlow */}
        else stack[++topIndex] = newItem;
    }
    
    // pop
    public E pop() {
        if (isEmpty()) return ERROR; // underFlow
        else return stack[topIndex--];
    }
    
    // top
    public E top() {
        if (isEmpty()) return ERROR; // underFlow
        else return stack[topIndex];
    }
    
    // isEmpty
    public boolean isEmpty() {
        return (topIndex < 0);
    }
    
    // isFull
    public boolean isFull() {
        return (topIndex == stack.length - 1);
    }
    
    // popAll
    public void popAll() {
        stack = (E[]) new Object[stack.length]; // 새로운 객체 선언
        topIndex = -1;
    }
}

 

스택 생성자는 2가지로 정의하였다. DEFAULT_CAPACITY라는 필드를 따로 두어, 스택 크기를 지정하지 않는다면, 메모리 사용 제한을 64 크기로 두었고 따로 설정을 하지 않는다면 스택 크기를 동적으로 할당할 수 있다.

 

이후 등장하는 5개의 메소드는 스택의 요소와 관련된 메소드이다.

 

* popAll()을 이용하면 기존의 배열 객체를 덮어쓰게 되는데, 이는 사용하지 않는 객체의 경우 가비지컬렉터에 의해 자동으로 삭제되기 때문에 메모리의 낭비와는 크게 관련이 없다.

---

연결 리스트 스택 구조

 

연결 리스트는 각 데이터의 요소(노드)가 다른 데이터의 주소를 참조한다는 점에서 배열 리스트와 차이가 있다. 메모리가 필요할 때마다 동적으로 할당되기 때문에 연결리스트로 구성할 시에 어느 노드를 스택 탑으로 삼을지 결정하는 과정이 필요하다.

 

 

맨 앞이나 맨 끝을 스택 탑으로 삼고, 레퍼런스 변수(topNode)가 스택 탑을 가리키도록 설정한다. 그리고 빈 스택은 오른쪽 아래 그림과 같이 null로 해둔다.

 

 

스택 객체 구조 

연결 리스트의 메소드 구성은 배열 리스트와 동일하지만, 주소를 참조한다는 점에서 topNode 필드를 둔다.

topNode - 레퍼런스 변수

push(x) - 스택의 맨 위에 원소 x를 삽입한다.
pop() - 스택 맨 위에 있는 원소를 알려주고 삭제한다.
top() - 스택의 맨 위에 있는 원소를 알려준다.
isEmpty() - 스택이 비었는지 알려준다.
popAll() - 스택을 깨끗이 청소한다.

 

 

클래스

import list.Node; // 노드 클래스 사용

public class LinkedStack<E> implements StackInterface<E> {
    private Node<E> topNode;
    private final E ERROR = null; // 임의의 에러 값
    public LinkedStack() {
        topNode = null;
    }
    
    // push
    public void push(E newItem) {
        topNode = new Node<>(newItem, topNode);
    }
    
    // pop
    public E pop() {
        if (isEmpty()) return ERROR; // underFlow
        else {
            Node<E> temp = topNode;
            topNode = topNode.next;
            return temp.item;
        }
    }
    
    // top
    public E top() {
        if (isEmpty()) return ERROR; // underFlow
        else return topNode.item;
    }
    
    // isEmpty
    public boolean isEmpty() {
        return (topNode == null);
    }
    
    // popAll
    public void popAll() {
        topNode = null; // 리스트의 노드에 대한 참조를 끊음
    }
}

 

 

연결 리스트 상속

상속은 부모 클래스 객체를 자식 클래스에서도 사용할 수 있도록 하는 기능이다.
위에서 이미 만들어놓은 연결리스트를 상속받아 재사용하면, 코드 구현에 드는 노력을 훨씬 줄일 수 있다.

public class InheritedStack<E> extends LinkedList<E> implements StackInterface<E> {...}

 

기존의 생성자를 그대로 이용해도 되고 추가로 수정하여 이용할 수 있다.

import list.LinkedList;

public class InheritedStack<E> extends LinkedList<E> implements StackInterface<E> {
    
    public inheritedStack() {
        super();
    } 
    
    public void push(E newItem) {
        add(0, newItem);
    }
    
    public E pop() {
        if (!isEmpty()) {
          return remove(0);
        } else return null;
    }
    
    public E top() {
        return get(0);
    }
    
    public void popAll() {
        clear();
    }
}

 

 

(참고)알고리즘 응용

Postfix 계산

- 문자의 인덱스를 이용하여 조건을 두고 스택에 삽입하는 계산방식

 

1. 문자가 숫자이면 push()를 통해 바로 스택에 삽입한다. 만약 연속된 숫자가 있을 경우 추가적으로 pop()을 진행시켜 계산을 하고 스택에 넣는다.
2. 문자가 연산자일 경우, pop()을 두번 진행하여게산 결과를 스택에 삽입한다. 
3. 공백은 무시하고 넘어간다.