자료구조 - Stack, Queue | 백준 10828 , 10773 Python

1. Stack의 노드 기본 단위 

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

 

2.  Stack의 구성

class Stack:
    def __init__(self):
        self.top = None

    #push, pop, is empty
    def is_empty(self):
        return self.top is None
    
    def push(self, val):
        self.top = Node(val, self.top) # val == item, self.top == next(다음 가리키는 것))
    
    def pop(self):
        if not self.top:
            return None

        node = self.top #가장 최근 추가된 top node
        self.top = self.top.next #다음 노드
        return node.item

 

 

3. 백준 10828 

 

문제 링크 : https://www.acmicpc.net/problem/10828

10828번: 스택

solution

import sys

n = int(sys.stdin.readline())
stack = []

for i in range(n):
    command = sys.stdin.readline().split()

    if command[0] == 'push':
        stack.append(command[1])

    elif command[0] == 'pop':
        if len(stack):
            print(stack.pop())
        else:
            print(-1)

    elif command[0] == 'top':
        if len(stack):
            print(stack[-1])
        else:
            print(-1)

    elif command[0] == 'size':
        print(len(stack))
    
    elif command[0] == 'empty':
        if len(stack):
            print(0)
        else:
            print(1)

 

 

+ ) 백준 10773 제로 Python

문제 링크 : https://www.acmicpc.net/problem/10773

10773번: 제로

solution

n = int(input())

stack = []
for i in range(n):
    num = int(input())
    if num == 0:
        stack.pop()
    else:
        stack.append(num)

print(sum(stack))

 

 

 

4. Queue의 기본 구성 (노드는 스택과 동일)

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

class Stack:
    def __init__(self):
        self.front = None

    #push, pop, is empty
    def is_empty(self):
        return self.front is None
    
    def push(self, val):
        if not self.front:
            self.front = Node(val  ,None)
            return

        node = self.front
        while node.next:
            node = node.next
        node.next = Node(val, None)

    def pop(self):
        if not self.front:
            return None
        
        node = self.front
        self.front = self.front.next
        return node.item