스택 Stack

Top이라고 하는 한쪽 끝에서 모든 삽입(Push)과 삭제(Pop)가 일어나는 순서 리스트

스택 $S=(a_0, ...., a_{n-1})$: $a_0$는 bottom, $a_{n-1}$은 top 원소

$a_i$는 원소 $a_{i-1} (0<i<n)$의 위에 있음

후입선출(LIFO, Last-In-First-Out)리스트

 

https://commons.wikimedia.org/wiki/File:Data_stack.svg

스택의 한 예: 시스템 스택

프로그램 실행 시 함수 호출을 처리

함수 호출시 활성 레코드(activation record) 또는 스택 프레임(stack frame) 구조 생성

이전의 스택 프레임에 대한 포인터

복귀 주소

지역 변수

매개 변수

 

함수가 자기자신을 호출하는 순환 호출도 마찬가지로 처리

순환 호출시마다 새로운 스택 프레임 생성

최악의 경우 가용 메모리 전부 소모 

 

시스템 스택

주 함수(main function)가 함수 func1을 호출하는 예

http://tcpschool.com/c/c_memory_stackframe

 

스택 구현

일차원 배열 stack 사용

i 번째 원소 stack[i-1]에 저장

변수 top은 스택의 최상위 원소를 가리킴

 

The Stack Abstract Data Type

class Stack <T> {

    private T[] stack; // array for stack elements

    private int top; // array position of top element

    private int capacity; // capacity of stack array

 

    Stack(int stackCapacity) throws Exception {

        capacity = stackCapacity;

         if(capacity < 1) throw new Exception ("Stack capacity must be > 0");

       

        stack = (T []) new Object [capacity];

        top = -1;

    }

 

    boolean IsEmpty(){

        return (top == -1);    

    }

 

    // Return top element of stack

    T Top() throws Exception {

        if(IsEmpty()) throw new Exception("Stack is empty");

        return stack[top];

    }

    

    /** * Insert item into the top of the stack */

    void Push(T item) throws Exception {

        if (top == capacity -1) {

           throw new Exception("Stack is full")

        }

        stack[++top] = item;         

    }

 

    void Pop() throws Exception {

        if (IsEmpty()) {

            throw new Exception("Stack is empty. Cannot delete.");   

    }

    top--;

};