[자료구조] 스택

1. 스택이란

스택이란 자료구조의 하나로서 마지막에 들어간 자료가 먼저 나오는 구조입니다. 이를 LIFO(Last In First Out)이라고도 하며, 후입선출 방식이라고도 합니다. 

출처: 얄코의 가장 쉬운 자료구조와 알고리즘

 

위 그림을 보면 알 수 있듯이 아래에 막힌 통 형태라고 생각하면 좋습니다.

 

스택에는 3가지 기능이 있습니다. 자료를 넣는 push, 자료를 꺼내는 pop, 그리고 맨위에 무엇이 있는지 확인하는 peek가 있습니다.

3가지의 시간복잡도는 모두 O(1)입니다. 왜냐하면 스택 내부의 데이터를 순회하지 않기 때문입니다. 

이러한 스택은 브라우저나 문서에서 많이 사용합니다. 브라우저를 실행하여 이벤트를 실행할때 스택에 push되고 뒤로가기 버튼을 누르면 pop이 실행된다고 할 수 있습니다. 문서 작업시에도 컨트롤 z가 스택의 pop기능을 하는것이라고 볼 수 있습니다.

 

이를 파이썬과 자바코드로 확인해보겠습니다.

 

1) 배열을 사용한 스택 코드

파이썬

class ArrayStack:
    def __init__(self, capacity):
        self.stack = [None] * capacity # capacity는 수용량 - 파이썬은 기본적으로 동적배열이기 때문에 이러한 방식으로 정적배열처럼 사용가능
        self.capacity = capacity
        self.top = -1

    def push(self, item):
        if self.top + 1 == self.capacity:
            raise Exception("Stack is full")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        item = self.stack[self.top]
        self.top -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        return self.stack[self.top]

    def is_empty(self):
        return self.top == -1

    def size(self):
        return self.top + 1


stack = ArrayStack(5)

stack.push(5)
stack.push(2)
stack.push(8)
stack.push(7)
stack.push(4)

print(stack.pop()) # 4
print(stack.pop()) # 7

print(stack.peek()) # 8

print(stack.size()) # 3
print(stack.is_empty()) # False

## 실무에서는 리스트에서 pop등으로 사용
stack_test= []

stack_test.append(5)
stack_test.append(6)
stack_test.append(8)

print(stack_test) #[5, 6, 8]

data = stack_test.pop()
print(data) # 8
print(stack_test) #[5, 6]

 

자바

public class ArrayStack {
    private int[] stack;
    private int capacity;
    private int top;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.stack = new int[capacity];
        this.top = -1;
    }

    public void push(int item) {
        if (top + 1 == capacity) {
            throw new RuntimeException("Stack is full");
        }
        stack[++top] = item;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }

    public static void main(String[] args) {
        
        ArrayStack stack = new ArrayStack(5);
        
        stack.push(5);
        stack.push(2);
        stack.push(8);
        stack.push(7);
        stack.push(4);
        
        System.out.println(stack.pop()); // 4
        System.out.println(stack.pop()); // 7
        
        System.out.println(stack.peek()); // 8
        
        System.out.println(stack.size()); // 3
        System.out.println(stack.isEmpty()); // false
    }
}

2) 연결리스트를 사용한 스택코드

파이썬

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.head = None
        self.count = 0

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node
        self.count += 1

    def pop(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        item = self.head.data
        self.head = self.head.next
        self.count -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Stack is empty")
        return self.head.data

    def is_empty(self):
        return self.head is None

    def size(self):
        return self.count


stack = LinkedListStack()

stack.push(5)
stack.push(2)
stack.push(8)
stack.push(7)
stack.push(4)

print(stack.pop()) # 4
print(stack.pop()) # 7

print(stack.peek()) # 8

print(stack.size()) # 3
print(stack.is_empty()) # False

 

자바

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListStack {

    private Node head;
    private int count;

    public LinkedListStack() {
        head = null;
        count = 0;
    }

    public void push(int item) {
        Node newNode = new Node(item);
        newNode.next = head;
        head = newNode;
        count++;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int item = head.data;
        head = head.next;
        count--;
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return head.data;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public int size() { return count; }

    public static void main(String[] args) {
        
        LinkedListStack stack = new LinkedListStack();
        
        stack.push(5);
        stack.push(2);
        stack.push(8);
        stack.push(7);
        stack.push(4);
        
        System.out.println(stack.pop()); // 4
        System.out.println(stack.pop()); // 7
        
        System.out.println(stack.peek()); // 8
        
        System.out.println(stack.size()); // 3
        System.out.println(stack.isEmpty()); // false
    }
}

 

2. 콜스택

콜스택은 우리가 함수를 사용할때마다 그와 관련된 정보들이 쌓이는 곳입니다. 콜스택의 콜은 함수의 호출을 의미합니다.

 

F12를 눌러 개발자 모드를 열어서 소스탭에 들어가보면 아래처럼 콜스택이 있는 것을 확인할 수 있습니다.

 

https://showcases.yalco.kr/youtube/call-stack/00/index.html

Document

 이 페이지에서 콜스택이 쌓이고 제거되는것을 테스트 해볼 수 있습니다.

 

콘솔 부분에 브레이크 포인트를 지정한 후 F5를 한번 눌러 디버깅을 실행할 수 있습니다.

 

 

재생버튼을 계속 눌러보면 스택의 형식으로 f1()~f3()까지 콜스택에 쌓였다가 제거될때는 역순으로 되는것을 확인할 수 있습니다.

 

3. 스택오버플로우(StackOverflow)

일반적으로 스택의 공간은 무한하지 않습니다. 따라서 스택의 공간을 초과하게 되면 오류가 발생하는데 이를 스택오버플로우라고합니다. 동적으로 생성된 스택공간이라도 메모리 공간이 무한하지않기 때문에 스택오버플로우가 발생할 수 있습니다.

주로 재귀함수나 무한루프에서 이러한 오류가 발생하게 됩니다. 따라서 이러한 함수를 만들거나 사용할때는 이러한 점을 고려한 후에 사용해야 합니다.

 

참조: 얄코의 가장 쉬운 자료구조와 알고리즘
https://inf.run/Th7xU

얄코의 가장 쉬운 자료구조와 알고리즘| 얄팍한 코딩사전 - 인프런 강의