[자료구조] 2-1. 스택(Stack)

스택(Stack)

스택 자료구조는 탄창에 총알을 넣고 빼듯,

먼저 넣은 데이터를 늦게 꺼내는 선입후출(先入後出,  FILO(First in Last out)), 후입선출(後入先出, LIFO(Last in First Out))을 따른다. 

스택의 연산

스택의 연산은 다음 4가지가 있다:

• isEmpty() : 스택이 비어있는지를 판단한다.
• push(data) : 스택의 맨 위에 데이터를 쌓는다
• pop() : 스택의 맨 위 데이터를 스택에서 뺀다.
• top() : 스택의 맨 위의 값을 확인한다.

스택의 구현 - 배열을 이용한 구현(Python)

class stack():        #스택 선언
    def __init__(self):
        self.arr = []
    
    def _len_(self):
        return len(self.arr)
    
    def isEmpty(self):    #스택이 비어있는지 확인
        if len(self.arr) == 0:
            return True
        else:
            return False
        
    def push(self, data):    #스택에 데이터 맨 위에 추가
        self.arr.append(data)
    
    def pop(self):    #스택의 맨 위 값 삭제 및 반환
        if self.isEmpty():
            print("Stack is Empty")
        else:
            return(self.arr.pop())
        
    def top(self):    #스택의 맨 위 값 반환
        if self.isEmpty():
            print("Stack is Empty")
        else:
            return(self.arr[-1])

예시

s = stack()
print(s.isEmpty())
s.push(5)
s.push(7)
s.push(2)
s.push(3)
s.push(9)
print(s.isEmpty())
print(s.pop())
print(s.pop())
print(s.pop())
print(s.top())

 

True
False
9
3
2
7

class Node():    #노드 선언
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
class Stack():    #스택 선언
    def __init__(self):
        self.head = None
        
    def isEmpty(self):    #스택이 비어있는지
        if self.head == None:
            return True
        else:
            return False
        
    def push(self,data):    #스택의 head에 값 추가
        if self.isEmpty():
            self.head = Node(data)
        else:
            self.head = Node(data, self.head)
            
    def pop(self):    #스택의 head제거
        if self.isEmpty():
            print("stack is Empty!")
        else:
            headNode = self.head
            self.head = self.head.next
            headNode.next = None
            return headNode.data
    
    def top(self):    #스택의 head값 출력
        if self.isEmpty():
            print("Stack is Empty!")
        else:
            return self.head.data

s = Stack()
print(s.isEmpty())
s.push(7)
s.push(5)
s.push(3)
s.push(1)
print(s.isEmpty())
print(s.pop())
print(s.pop())
print(s.pop())
print(s.top())

True
False
1
3
5
7