[알고리즘] 스택 (Stack)

이전 글 : )

[알고리즘] 해시(Hash), 해시 테이블(Hash Table)

---

 스택 stack 

 

스택 stack은 자료의 삽입과 삭제가 데이터 공간의 한쪽 끝에서만 일어나는 자료구조입니다.

구조상 가장 나중에 들어간 자료가 맨 먼저 빠져나가는 자료구조이며 후입 선출 (LIFO : Last In First Out)이라고 합니다.

 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

 

스택은 top이라는 출입구로만 접근이 가능합니다.

top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리킵니다.

삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이며, 자료를 삭제할 때도 top을 통해서만 가능합니다.

스택에서 top을 통해 삽입하는 연산을 push, top을 통한 삭제하는 연산을 pop이라고 합니다.

 

스택이 비어있을 때 원소를 꺼낸다면 stack underflow, 스택의 크기를 넘어선다면 stack overflow라고 합니다.

 

 

 Stack 구현 

 

스택 클래스로 구현해보겠습니다.

class Stack:

자료를 저장할 공간을 myStack으로 할당합니다.

    def __init__(self) :
        self.myStack = []

스택에 값을 넣습니다. (push)

    def push(self, n) :
        self.myStack.append(n)

스택에서 값을 추출합니다. (pop)

   def pop(self) :
        if  self.empty() == 1:
            return
        else :
            self.myStack.pop()

 

리스트 자료형을 이용하므로 leg(), empty()등 함수를 사용할 수 있습니다.

 

---

 

 

[알고리즘] 큐 (Queue)