데이터 구조 및 알고리즘: 스택

빈 유리잔에 몇 개의 그릇을 추가해 봅시다.


하나 추가....

또 하나 추가...


하나 더 추가..


이제 문제는 우리가 한 그릇을 밖에 가져가서 어떤 그릇을 먼저 가져갈지 추측할 수 있다는 것입니다.

3번째인가요? 두 번째? 아니면 1위?

예, 세 번째이며 LIFO(Last In First Out)를 따릅니다.


그럼 이렇게 제거해보겠습니다







따라서 연결된 목록을 사용하여

아이템 팝

또한 앞에 붙일 수 있습니다


스택은 다음과 같습니다.


건설자
먼저 노드 생성


첫 번째 노드 만들기


다음과 같이 상단 및 하단을 설정합니다.


우리는 바닥에 신경쓰지 않고 따라서 바닥을 제거할 것입니다.





따라서 전체적으로 생성자는 다음과 같습니다.


이에 대한 코드:

#Node class : Creates node
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

#Creates a stack class
class Stack:
    def __init__(self, value):
        #creates a node by calling the Node class
        new_node = Node(value)
        #pointing the top to that node
        self.top = new_node
        #adding the length to 1
        self.height = 1
    #Prints the stack untill it finds None
    def print_stack(self):
        temp = self.top
        while temp is not None:
            print(temp.value)
            temp = temp.next

#Creating a stack with node 4
my_stack = Stack(4)

#Printing the stack
my_stack.print_stack()

푸시
사례 1:
스택이 비어 있으면 노드를 추가하고 맨 위에 할당합니다.



사례 2:
이전 스택에 노드를 추가합니다.







이에 대한 코드:

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


class Stack:
    def __init__(self, value):
        new_node = Node(value)
        self.top = new_node
        self.height = 1

    def print_stack(self):
        temp = self.top
        while temp is not None:
            print(temp.value)
            temp = temp.next
    #push method
    def push(self, value):
        new_node = Node(value)
        #When there are no nodes in the stack
        if self.height == 0:
            self.top = new_node
        #When there are nodes in the stack   
        else:
            new_node.next = self.top
            self.top = new_node
        self.height += 1

#Creates a stack of 2
my_stack = Stack(2)

#pushing 1 to the stack
my_stack.push(1)

my_stack.print_stack()

팝
사례: 1
스택에 아무 ​​것도 없으면 아무 것도 반환하지 않습니다.


사례 2:
스택이 있고 마지막으로 입력한 값을 반환할 때.
먼저 온도를 설정합니다.


그 다음에

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


class Stack:
    def __init__(self, value):
        new_node = Node(value)
        self.top = new_node
        self.height = 1

    def print_stack(self):
        temp = self.top
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def push(self, value):
        new_node = Node(value)
        if self.height == 0:
            self.top = new_node
        else:
            new_node.next = self.top
            self.top = new_node
        self.height += 1
        return True

    def pop(self):
        #when we have no nodes in the stack
        if self.height == 0:
            return None
        #when we have nodes in the stack
        temp = self.top
        self.top = self.top.next
        temp.next = None
        self.height -= 1
        return temp

#A stack of nodes 7,23,3,11

my_stack = Stack(7)
my_stack.push(23)
my_stack.push(3)
my_stack.push(11)

#poping a node from the stack. Note: pop returns the last value intered into the stack[last in first out]
print(my_stack.pop(), '\n')

my_stack.print_stack()