스택(Stack)

1. 스택이란

■ 스택은 자료를 밑에서부터 저장하고 자료를 꺼낼 때 위에서부터 꺼내기 때문에 가장 최근에 들어온 자료가 가장 먼저 나가는 후입선출(LIFO: Last - In First Out)의 자료구조이다.

■ 이렇게 스택은 한쪽 방향으로만 삽입, 삭제가 되므로 연산이 간단하다.

■ 스택은 스택 중간에서 삽입, 삭제가 불가능하고 스택의 상단에서 데이터의 삽입, 삭제가 발생하는데, 이 스택 상단을 top이라 한다.

■ 숫자, 문자열, 리스트 클래스의 객체 등 어떤 자료든지 스택에 저장할 수 있다.

[출처] https://www.geeksforgeeks.org/stack-meaning-in-dsa/

 

2. 스택 구현

■ 스택은 리스트처럼 기본적으로 배열 구조와 연결된 구조로 구현할 수 있다.

2.1 배열 구조(단순 리스트)로 스택 구현

 

Stack ADT – Data structures (inflibnet.ac.in)

Stack ADT – Data structures

[출처] Stack ADT – Data structures (inflibnet.ac.in)

■ 위와 같은 스택 ADT 연산들을 파이썬의 단순 리스트를 이용해 다음과 같이 구현할 수 있다.

■ isEmpty는 리스트의 길이가 0이면 True, 그렇지 않으면 False를 반환해야 한다.

class ArrayStack:
    def __init__(self, data):
        self.data = []
        
    def StackIsEmpty(self):
        return len(self.data) == 0

■ 스택의 삽입, 삭제 연산은 스택 상단에 데이터를 추가하거나 꺼내는 것이므로 리스트의 맨 뒤를 스택 상단으로 하는 것이 좋다.

- 다음 그림처럼 리스트 후단에서 삽입, 삭제를 하면 삽입과 삭제 연산의 시간 복잡도는 \( O(1) \)로  리스트 전단에서의 삽입, 삭제 연산의 최악의 경우 시간 복잡도 \( O(n) \)에 비해 효율적이다.

■ 따라서 삽입은 다음과 같이 리스트의 append 함수를 사용하여 data를 리스트 후단에 삽입하면 된다.

def StackPush(self, new_item):
    self.data.append(new_item)

■ 삭제 연산도 리스트 후단에서 삭제하기 위해 리스트의 pop( ) 함수를 사용하여 리스트의 맨 마지막 항목을 꺼내면 된다.

- 단, 삭제 연산은 먼저 자료가 비어 있는지 확인해야 한다. 

- 리스트에 어떠한 항목도 없는 상태에서 리스트의 pop( ) 함수를 실행하면 IndexError이 발생하기 때문이다.

def StackPop(self):
    if self.StackIsEmpty():
        return None
    else:
        return self.data.pop()

 

■ 스택 삽입, 삭제가 리스트의 후단에서 발생하므로 스택 상단의 data는 항상 리스트 맨 마지막의 항목이다. 따라서 현재 스택 상단의 data가 무엇인지 확인하려면 리스트의 마지막 원소만 확인하면 된다.

- 만약 스택의 data가 모두 비어 있다면, 이 연산도 삭제 연산처럼 None을 반환하면 된다.

def StackTop(self):
    if self.StackIsEmpty():
        return None
    else:
        return self.data[-1]

 

■ 스택의 size를 확인하고 싶으면, 리스트의 길이를 반환하고, 스택의 data들을 모두 비우고 싶으면 비어 있는 리스트 형태로 만들어 주면 된다.

def StackSize(self):
    return len(self.data)

def StackClear(self):
    self.data = []

■ 만약, 스택의 size를 사전에 지정하여 스택 삽입, 삭제 연산을 하다가 현재 스택이 꽉 찼는지 확인하고 싶으면, 다음과 같이 클래스 생성자 메소드의 매개변수에 max_size를 넣어, 클래스로부터 객체를 생성할 때, 사전에 스택의 max size를 설정하고

class ArrayStack2:
    def __init__(self, max_size):
        self.data = []
        self.max_size = max_size

- 이를 검사하는 클래스의 메소드는 사용자가 설정한 size와 스택의 현재 size를 비교해서 두 값이 동일하면 스택이 모두 찬 것으로 판단할 수 있도록 다음과 같이 정의하면 된다.

def StackIsFull(self):
    if self.max_size == self.StackSize():
        print('stack is full')
        return True
    else:
        print('stack is not full')
        return False

- 그리고 스택이 꽉 차면, 더 이상 삽입을 할 수 없으므로 스택 삽입 메소드를 수정해, StackIsFull( )이 True이면 예외를 발생시켜 삽입을 막을 수 있다. 만약 반환 값이 False라면 새로운 항목을 스택에 추가한다.

def StackPush2(self, new_item):
    if self.StackIsFull() == True:
        raise Exception('Could not insert data, stack is full')
    else:
        self.data.append(new_item)

■ 따라서 사전에 스택의 크기를 지정하지 않을 것 이라면 배열 구조로 스택을 다음과 같이 구현할 수 있고

class ArrayStack:
    def __init__(self):
        self.data = []
        
    def StackIsEmpty(self):
        return len(self.data) == 0
    
    def StackPush(self, new_item):
        self.data.append(new_item)
        
    def StackPop(self):
        if self.StackIsEmpty():
            return None
        else:
            return self.data.pop()
        
    def StackTop(self):
        if self.StackIsEmpty():
            return None
        else:
            return self.data[-1]
    
    def StackSize(self):
        return len(self.data)

    def StackClear(self):
        self.data = []

지정할 것이라면 다음과 같이 스택을 구현할 수 있다.

class ArrayStack2:
    def __init__(self, max_size):
        self.data = []
        self.max_size = max_size
        
    def StackIsEmpty(self):
        return len(self.data) == 0
    
    def StackIsFull(self):
        if self.max_size == self.StackSize():
            print('stack is full')
            return True
        else:
            print('stack is not full')
            return False    
        
    def StackPush2(self, new_item):
        if self.StackIsFull() == True:
            raise Exception('Could not insert data, stack is full')
        else:
            self.data.append(new_item)
        
    def StackPop(self):
        if self.StackIsEmpty():
            return None
        else:
            return self.data.pop()
        
    def StackTop(self):
        if self.StackIsEmpty():
            return None
        else:
            return self.data[-1]
    
    def StackSize(self):
        return len(self.data)

    def StackClear(self):
        self.data = []

a = ArrayStack2(6)

print(a.StackIsEmpty())
```#결과#```
True
````````````

a.StackPush2(1); a.StackPush2(20); a.StackPush2(5); a.StackPush2(8); a.StackPush2(10); a.StackPush2(13)
```#결과#```
stack is not full
stack is not full
stack is not full
stack is not full
stack is not full
stack is not full
````````````

print(a.data) # 삽입 연산이 리스트 후단에서 발생
```#결과#```
[1, 20, 5, 8, 10, 13]
````````````

a.StackPush2(99) # 예외 발생
```#결과#```
stack is full

---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
Cell In[39], line 1
----> 1 a.StackPush2(99)

Cell In[9], line 19, in ArrayStack2.StackPush2(self, new_item)
     17 def StackPush2(self, new_item):
     18     if self.StackIsFull() == True:
---> 19         raise Exception('Could not insert data, stack is full')
     20     else:
     21         self.data.append(new_item)

Exception: Could not insert data, stack is full
````````````````

print(a.StackSize()); print(a.StackIsFull())
```#결과#```
6
stack is full
True
`````````````

print(a.data, a.StackTop()) # 스택 상단(top)이 리스트 후단
```#결과#```
[1, 20, 5, 8, 10, 13] 13
````````````

print(a.data); print(a.StackPop(), a.data) # 삭제 연산이 리스트 후단에서 발생
```#결과#```
[1, 20, 5, 8, 10, 13]
13 [1, 20, 5, 8, 10]
````````````

print(a.StackIsFull())
```#결과#```
stack is not full
False
```````````

print(a.data); a.StackPush2(100); print( a.data) # 삽입 연산이 리스트 후단에서 발생
```#결과#```
[1, 20, 5, 8, 10]
stack is not full
[1, 20, 5, 8, 10, 100]
`````````````

a.StackClear()
print(a.StackSize()); print(a.StackIsEmpty())
```#결과#```
0
True
````````````

 

2.2 연결 구조(링크드 리스트)로 스택 구현

■ 단순연결리스트로 구현한 스택을 연결된 스택(linked stack)이라고 한다.

■ 배열 구조로 스택을 구현할 때는 스택의 상단을 리스트 후단으로 두고 삽입, 삭제 연산을 구현하였다.

- 연결된 스택은 이와 유사하게 스택 상단을 헤드 포인터로 설정한다.

■ 연결 리스트의 구조이므로 노드 클래스와 연결된 스택 클래스를 구현해야 한다. 먼저 노드는 링크드 리스트의 노드 클래스와 동일하게 작성한다.

class Node:
    def __init__(self, data, link = None):
        self.data = data
        self.next_node = link
        
    def set_next(self, node):
        self.next_node = node
        
    def get_next(self):
        return self.next_node
    
    def get_data(self):
        return self.data

■ 링크드 스택은 첫 번째 노드(시작 노드)를 스택 상단 top으로 사용한다. 스택이 비어 있으면 헤드는 None을 가리키므로, 링크드 스택 클래스의 생성자는 다음과 같이 구현할 수 있다.

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

■ 스택이 비어 있다면, 링크드 리스트 구조이므로 top은 None을 가리키고 있어야 한다.

이와 비슷하게 스택을 초기화시키는 연산은 top을 None을 만들어 주면 되므로, 스택 공백을 검사하는 메소드와 스택 초기화 메소드는 다음과 같이 구현할 수 있다.

def StackIsEmpty(self):
    return self.top == None

def StackClear(self):
    self.top = None

■ 링크드 리스트 구조이므로 삽입의 경우, 배열의 구조처럼 삽입할 data를 직접 스택에 넣을 수 없고, 첫 번째 노드인 top의 자리에 새로운 노드를 위치시켜야 새로운 노드가 새로운 top이 되어 스택 상단에 위치하게 된다.

■ 즉, 다음과 같이 새로운 노드를 E라고 하면, 이 노드를 스택의 top에 추가해야 한다. 새로 생성된 노드는 top을 가리켜야 하며, 새로운 노드 E가 top, 즉 스택 상단에 있어야 한다.

- 예를 들어 Stack (top -> 10 -> None)에 데이터가 20인 새 노드를 삽입한다고 했을 때, 새 노드의 링크는 현재 top을 가리키고, 새로운 스택의 top은 이 새 노드로 업데이트해야 한다.

- 그러면 새로 삽입된 노드가 맨 앞에 위치한다.  Stack (top -> 20 -> 10 -> None)

def StackPush(self, new_item):
    new_node = Node(new_item, self.top)
    self.top = new_node

■ 삭제 연산은 스택 상단의 data를 꺼내서 반환해야 하며, 새로운 top은 기존의 top이 가리키고 있던 두 번째 노드가 되야 한다. 또한, 스택이 비어 있는 경우 top은 None을 가리켜야 하므로

def StackPop(self):
    if self.StackIsEmpty():
        return None
    else:
        pop_node = self.top.get_data() # 삭제 시 top을 삭제 및 반환
        self.top = self.top.get_next() # 기존 top이 삭제되면 새로운 top은 기존 top이 가리키고 있던 두 번째 노드이다.
        return pop_node # 삭제되는 top 노드 반환

- 위의 코드에서 별도로 노드를 삭제하는 코드가 없는 이유는, 파이썬에서는 어떤 객체를 참조하는 변수가 하나도 없으면 그 객체는 자동으로 삭제되기 때문에 별도로 삭제 코드를 넣을 필요가 없다.

- self.top = self.top.get_next( )에서, 기존의 top을 top 노드의 다음 노드로 변경하여, 더 이상 기존의 top 노드를 참조하는 변수가 없어지므로 자동으로 메모리에서 해제, 즉 삭제되는 것이다.

■ 스택이 공백이 아닌 상태에서, 현재 스택의 top이 무엇인지 확인하려면 self.top의 데이터를 반환시키면 된다.

def StackTop():
    if self.StackIsEmpty():
        return None
    else:
        return self.top.get_data()

■ 연결 구조로 구현할 경우 스택의 항목 수, 그리고 스택의 모든 항목을 출력하는 방법은 첫 노드에서 순서대로 마지막 노드까지 방문해야 하므로, 링크드 리스트의 항목 수를 계산하는 방법 그리고 링크드 리스트의 모든 항목을 출력하는 방법과 같은 방법을 사용하면 된다.

def StackSize(self):
    node = self.top
    count = 0
    while True:
        if node == None:
            break
        count += 1
        node = node.get_next()
    return count

def StackShow(self):
    curr = self.top
    while curr is not None:
        print(curr.data, end = " ")
        curr = curr.next_node

■ 최종적으로 연결 구조로 구현한 스택 클래스는 다음과 같다.

class LinkedStack:
    def __init__(self):
        self.top = None
        
    def StackIsEmpty(self):
        return self.top == None

    def StackClear(self):
        self.top = None
    
    def StackPush(self, new_item):
        new_node = Node(new_item, self.top)
        self.top = new_node
        
    def StackPop(self):
        if self.StackIsEmpty():
            return None
        else:
            pop_node = self.top.get_data()
            self.top = self.top.get_next() 
            return pop_node 
        
    def StackTop():
        if self.StackIsEmpty():
            return None
        else:
            return self.top.get_data()
        
    def StackSize(self):
        node = self.top
        count = 0
        while True:
            if node == None:
                break
            count += 1
            node = node.get_next()
        return count

    def StackShow(self):
        curr = self.top
        while curr is not None:
            print(curr.data, end = " ")
            curr = curr.next_node

b = LinkedStack()

print(b.top); print(b.StackIsEmpty()); print(b.StackSize())
```#결과#```
None
True
0
````````````

for i in [3, 2, 5, 9, 13]:
    b.StackPush(i)
    
print(b.StackShow()) # 연결 구조로 구현 시, 삽입 연산은 리스트 전단에서 발생
print(b.top.get_data()) # 따라서 현재 top은 13
```#결과#```
13 9 5 2 3 None
13
````````````

print(b.StackShow())
print(b.StackPop()) # 연결 구조로 구현 시, 삭제 연산도 리스트 전단에서 발생
print(b.StackShow())
print(b.top.get_data()) # 삭제 후, 새로운 top은 9

```#결과#```
13 9 5 2 3 None
13
9 5 2 3 None
9
````````````

print(b.StackShow()); print(b.StackSize())
```#결과#```
9 5 2 3 None
4
````````````

b.StackClear()

print(b.top); print(b.StackIsEmpty()); print(b.StackSize())
```#결과#```
None
True
0
````````````

 

■ 위와 같이 스택을 단순 리스트로 구현하든, 링크드 리스트로 구현하든 삽입, 삭제, 스택 상단(top)의 데이터를 반환하는 연산 등, 시간 복잡도가 \( O(1) \)이 된다.

- 왜냐하면 단순 리스트로 구현할 경우 스택 상단을 리스트 후단에, 링크드 리스트로 구현할 경우 스택 상단을 리스트 전단에 설정했기 때문에 데이터를 넣고, 빼고 등의 연산이 n 번이 발생하는 것이 아닌 상수 시간이 소요되기 때문이다.

■ 따라서 스택은 단순 리스트를 이용하든지 링크드 리스트를 이용하든지, 사실상 모든 연산을 데이터 크기 n에 무관한 \( O(1) \)로 처리할 수 있다.