6. 스택(Stack)

1. 스택(Stack) 개념

후입선출(Last-In-First-Out : LIFO)형 자료구조

인터넷 브라우저 뒤로가기 / Ctrl + Z 실행 취소 / 접시 쌓기

 

push() : 데이터를 넣는 작업

pop() : 데이터를 빼오는 작업

top(), peek() : 데이터를 그대로 둔채 데이터만 가져옴

---

2. 스택(Stack) 구현 - JAVA

노드 기반 / Head를 더미 노드로 구현

package stack;

public class MyStack<T> implements IStack<T> {

    private int size;
    private Node head;

    public MyStack() {                                  // 생성자
        this.size = 0;
        this.head = new Node(data:null);
    }

    @Override
    public void push(T data) {          
        Node newNode = new Node(data, this.head.next); // 새로운 노드 생성하고 데이터(t) 넣고, 포인터를 head.next로 향하게 해줌
        this.head.next = newNode;                      // head의 포인터를 새로운 노드로 향하게 해줌
        size++;                                        // size + 1
    }

    @Override
    public T pop() {                 // top node의 데이터를 반환하고 노드는 삭제(꺼내온다)   
        if (isEmpty()) {            // top node 위에 head 더미 노드가 항상 있는 상태이다.
            return null;
        }
        Node curr = this.head.next;                 // head를 제외한 top node를 curr로 지정
        this.head.next = curr.next;                 // 현재 top을 삭제하기 위해 head 포인터를 top node(curr)의 next로 바꿈
        curr.next = null;                           // top node(curr)의 포인터를 끊어줌
        this.size--;                                // size -1
        return curr.data;                           // top node data 반환
    }

    @Override
    public T peek() {           // top node의 데이터만을 가져오고 스택에는 그대로 두는 동작
        if (isEmpty()) {
            return null;
        }
        return head.next.data;
    }

    @Override
    public int size() {
        return this.size;
    }

    private boolean isEmpty() {
        return this.head.next == null;
    }

    private class Node {                        // 노드 만들기 매서드
        Node next;
        T data;

        Node(T data) {this.data = data;}

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

---

3. 스택(Stack) 구현 - Python

class Stack:
    def __init__(self):
        self.head = Node()
        self._size = 0

    def push(self, data):
        new_node = Node()
        new_node.data = data
        new_node.next = self.head.next
        self.head.next = new_node
        self._size += 1

    def pop(self):
        if self.size == 0:
            return None

        ret = self.head.next
        self.head.next = ret.next
        self._size -= 1
        return ret.data

    def peek(self):
        if self._size == 0:
            return None
        return self.head.next.data

    def size(self):
        return self._size


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


if __name__ == "__main__":
    s = Stack()
    print("s.push(3)")
    s.push(3)
    print("s.push(5)")
    s.push(5)
    print("s.push(1)")
    s.push(1)
    print("s.push(9)")
    s.push(9)
    print(f"s.size(): {s.size()}")
    print(f"s.peek(): {s.peek()}")
    print(f"s.pop(): {s.pop()}")
    print(f"s.pop(): {s.pop()}")
    print(f"s.pop(): {s.pop()}")
    print(f"s.pop(): {s.pop()}")