[DataStructure] Stack(스택)

Stack(스택)

 

Stack은 특정 데이터를 누적해서 쌓아 올린 형태의 구조이다.

스택의 push, pop 

 

스택의 특징

• 같은 구조, 같은 크기의 자료를 정해진 방향으로만 쌓을 수 있다.
• top은 가장 위(마지막)에 쌓여있는 데이터를 가리킨다.
• top을 통해 top위 부분에 삽입하는 연산을 push, top을 삭제하는 연산을 pop이라고 한다.
• LIFO(Last In First Out), 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조
• 스택이 비어있을 때 pop연산을 하게되면 stack underflow가 일어난다.
• 스택이 가득찼을 때 push연산을 하게되면 stack overflow가 일어난다.

 

구현

class My_stack:
    # Constructor
    def __init__(self):
        self.items = list()
        self.top = 0
    # Adds element to the My_stack
    def push(self, item):
        self.items.append(item)
        self.top += 1
        return True
    # Removes element from My_stack
    def pop(self):
        if self.top <= 0:
            return ("stack underflow")
        ret = self.items.pop()
        self.top -= 1
        return ret
    # Peeks element from My_stack
    def peek(self):
        if self.isEmpty():
            return ("stack is empty")
        ret = self.items[self.top - 1]
        return ret
    # Size of the My_stack
    def size(self) -> int:
        return self.top
    # is empty the My_stack
    def isEmpty(self) -> bool:
        return self.top == 0

s = My_stack()
for i in range(9):
    s.push(i)
print(s.items)
print(f"remove item: {s.pop()}")
print(s.items)
for i in range(9):
    print(f"removed item: {s.pop()}")
    print(s.items)
    print(f"top of stack: {s.peek()}")
    print(f"is Empty? {s.isEmpty()}")
    print()