자료구조(3) - Stack

Stack 

Stack

 

 

 

 

< 개념 > 

Stack : List의 자료구조와 비슷하며 데이터를 정렬할 때 사용하기보단 FILO (First In, Last Out)를 활용한 문제가 있을 때  사용된다. 구조는 위의 그림처럼 아래가 막혀 있는 바구니를 생각하면된다. 

위의 그림처럼 색깔 순으로 Stack에 넣는다면 

처음부터 넣은 남색부터 데이터가 쌓이고 마지막으로 보라색이 넣어진다.

나올때는 반대로 마지막에 넣었던 보라색부터 나오고 맨처음 들어간 남색이 마지막에 나오므로 First In Last Out이 된다.

 

 

 

 

 

<특징>

• FILO ( First In Last Out )
• 넣은 순서를 기억해야 하는 알고리즘 문제 풀 때 유용 Ex) 되돌리기기능, 짝맞추기 기능 등등

 

 

 

 

<구현>

 

#Stack 기본메소드

Stack	메소드	설명	Return
	Push(value)	Value 값을 Node에 담아 Stack에 추가함	True / Fasle
	pop()	Staack의 맨 위의 값을 꺼냄	value
	peek()	Stack의 맨 위의 데이터를 확인함	value
	is_empty()	Stack이 비웠는지 확인함	True / False

 

 

<구현 과정1 - Linked List 이용>

Push(value) : LinkedList 의 head에 새로운 노드 추가 한다 
1. New Node 생성
2. 새로운 노드의 next를 현재 head로 지정
3. head를 새로운 노드로 재 지정

 

Pop() : LinkedList의 head를 출력한다.
1. head노드를 따로 저장
2. head를 저장한 노드의 next로 지정
3. 저장한 노드의 next를 제거 
4. 저장한 노드 Return

*Stack이 비였을 경우는 Head가 없기 때문에 예외처리를 해야함 (is_empty()함수 이용)

Peek() : LinkedList의 head 대이터를 조회한다

*Stack이 비였을 경우는 Head가 없기 때문에 예외처리를 해야함 (is_empty()함수 이용)

is_empty() : LinkedList의 head데이터의 유무를 판단

 

 

#python Code - Stack by Linked List

class Node:                      # LinkedList를 이용한 Stack
    def __init__(self, data):  
        self.data = data        	# data : data를 담을 부분
        self.next = None			# next : 다음 노드를 가리킴


class Stack:
    def __init__(self):				# Stack 정의
        self.head = None			# head : 처음 head 지정

    def push(self, value):			# push() : Stack에 데이터 넣기
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        return print('성공!')

    def pop(self):					# pop() : Stack에서 데이터 꺼내기
        if self.is_empty():
            return "Stack is Empty"
        curr = self.head
        self.head = self.head.next
        curr.next = None
        return curr

    def peek(self):					# peek() : Staack의 가장 윗 부분 데이터 엿보기
        if self.is_empty():
            return 'Stack is Empty'
        return self.head.data

    # isEmpty 기능 구현				# isEmpty() : Stack이 비였는지 확인
    def is_empty(self):
        return self.head is None

 

---

 

<구현 과정2 - List 이용> 

Stack를 간단히 구현을 하려면 python의 내장 함수인  List를 이용해도 좋다.

각 기능을 보여주려고 class를 정의하였지만 사실은 그냥 다음과 같이 대체하여 사용하면된다.

#list = '리스트를 정의한 변수

push() -> append()
pop() -> pop()
peek() -> list[0]     
is_empty -> len(list) == 0 

 

 

#python Code - Stack by List

class Stack:						# list를 이용한 Stack
    def __init__(self):
        self.items = []

    def push(self, value):
        self.items.append(value)
        return True

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

 

 

 

Stack을 이용한 문제 

• 추후 연결에정!

 

 

---