스택(Stack)

스택(Stack) : To put things in a pile.

스택의 예시

Top : 모든 추가 및 삭제는 위 그림처럼 한쪽(Top)에서만 가능합니다.

          (* Queue는 two ends에서 사용가능)

LIFO(Last In First Out)

- Data Series를 스택에 삽입한 후, 제거하려고 한다면 제거되는 순서는 삽입한 순서의 반대가 됩니다.

ex) 데이터 입력 순서 : {5, 10, 15, 20}

      데이터 제거 순서 : {20, 15, 10, 5}

 

스택의 기본 용어

- Bottom : 가장 밑에 있는 데이터

- Top : 가장 위에 있는 데이터

- Capacity : 스택에 담을 수 있는 데이터의 총 용량

- Size : 현재 스택에 담겨있는 데이터의 개수

Basic Stack Operations

- Push : Data를 Stack에 넣습니다.

- Pop : Stack에서 Data를 제거합니다. (일반적으로, 유저에게 데이터를 반환한다.)

- (Stack)Top : Stack의 제일 위에 해당하는 데이터를 반환합니다. (without deleting it)

 

Note : Push 및 Pop의 반환 값은 코드 구현에 따라 달라질 수 있습니다.

    ex) 작업 상태, 데이터 참조, 스택의 크기

 

 

Push

New Item을 넣을 공간이 있는지 먼저 확인해야합니다.

  If NOT -> 스택이 overflow 상태이므로, 추가할 수 없습니다.

Push 예시

 

Pop

스택에서 Top 바로 밑에 있는 Item이 Top이 됩니다.

Empty State : 스택의 마지막 항목이 삭제된 경우입니다.

스택이 Empty인경우, Pop을 호출하면 underflow가 발생합니다.

Pop 예시

(Stack)Top

스택의 상단의 요소를 반환합니다.

데이터는 삭제되지 않습니다.

스택이 비어 있는 경우 -> underflow가 발생할 수도 있습니다.

(Stack)Top 예시

 

Example

Stack Operation Example

 

 

 

Stack 메소드

push(E item): 스택에 요소(item)를 추가합니다. 

pop(): 스택의 가장 위에 있는 요소를 제거하고 반환합니다.

peek(): 스택의 가장 위에 있는 요소를 반환하지만 제거하지는 않습니다. 

isEmpty(): 스택이 비어있는지 여부를 반환합니다. 

clear() : 스택의 모든 요소를 제거하는 메소드입니다. 스택이 비어있게 됩니다.

size(): 스택의 현재 크기(요소의 개수)를 반환합니다.

search(Object o): 스택에서 특정 요소(o)의 인덱스를 반환합니다.

contains(num) : 주어진 객체(o)가 스택에 있는지 여부를 확인하는 메소드입니다. -> 있으면 True, 없으면 False

indexOf(num) : 주어진 객체(o)가 스택의 어느 위치에 있는지 확인하는 메소드입니다.  스택의 맨 위(가장 최근)부터 검색하며, 객체를 찾으면 해당 객체의 인덱스를 반환합니다. 찾지 못할 경우 -1을 반환합니다.

 

 

 

시간 복잡도(Time Complexity)

삽입(Insertion) = O(1)

삭제(Deletion) = O(1)

검색(Search) = O(n)

 

 

 

 

 

 

References

- Chapter 3. Stacks, Data Structures: A Pseudocode Approach with C, Second Edition, Richard F. Gilberg Behrouz A. Forouzan.