Stack

Stack

What is the Stack?

• Homogeneous한 Item이 순서를 갖고 쌓이는 것
• 한쪽 방향으로만의 추가와 제거가 가능
• LIFO: Last In, First Out

Stack ADT Operation

• Transformer
  • MakeEmpty
  • Push
  • Pop
• Observe
  • IsEmpty
  • IsFull
  • Top

Array Stack

Array

• Stack의 크기를 처음부터 정해 두고 시작해야 함
• 안 쓰는 메모리가 있을 경우에 낭비적인 방식
• Item에 pointer가 없기 때문에 Item 하나가 차지하는 메모리는 작음
• top 이라는 변수를 사용하여 stack의 가장 끝을 나타내는 위치 저장소 역할을 하도록 함

Static Stack with C++

• StackTypeStatic.h

  • Stack이 가지는 함수들을 선언해 놓은 헤더 파일

    #include "ItemType.h"
    
    class FullStack {
    };
    
    class EmptyStack {
    };
    
    class StackType {
    public:
    	StackType(); //생성자
    	void MakeEmpty();
    	void Push(ItemType item);
    	void Pop();
    	bool IsEmpty() const;
    	bool IsFull() const;
    	ItemType Top();
    private:
    	int top; // Stack의 마지막 요소가 저장된 index를 저장하는 값
    	ItemType items[MAX_ITEMS];
    };

• StackTypeStatic.cpp

  • Stack이 가지는 함수들의 기능을 실제로 구현해 놓은 파일

    #include "StackTypeStatic.h"
    
    StackType::StackType() {
    	top = -1;
    }
    
    void StackType::MakeEmpty() {
    	top = -1;
    }
    
    bool StackType::IsFull() const {
    	//마지막 요소의 index가 최대 개수 - 1 과 동일하다면 true 반환
    	return (top == MAX_ITEMS - 1);
    }
    
    bool StackType::IsEmpty() const {
    	//마지막 요소의 index가 없다면 true 반환
    	return (top == -1);
    }
    
    void StackType::Push(ItemType item) {
    	if (IsFull()) {
    		throw FullStack();
    	}
    	else {
    		//마지막 요소 index 하나 올리고 그 자리에 item 삽입
    		top++;
    		items[top] = item;
    	}
    }
    
    void StackType::Pop() {
    	if (IsEmpty()) {
    		throw EmptyStack();
    	}
    	else {
    		//요소를 삭제하지 않은 채 index만 내림
    		//어차피 새로 push할 때 새 값을 할당할 것이기 때문
    		//실제로 데이터는 삭제되지 않음
    		top--;
    	}
    }
    
    ItemType StackType::Top() {
    	if (IsEmpty()) {
    		//비어 있다면 EmptyStack 반환
    		throw EmptyStack();
    	}
    	else {
    		//빈 Stack이 아니라면 가장 꼭대기에 있는 item 반환
    		return items[top];
    	}
    }

• Time Complexity

  Function	Time Complexity
  MakeEmpty	O(1)
  IsFull	O(1)
  IsEmpty	O(1)
  Push	O(1)
  Pop	O(1)
  Top	O(1)

Dynamic Stack with C++

• StackTypeDynamic.h

  • Stack이 가지는 함수들을 선언해 놓은 헤더 파일

    #include "ItemType.h"
    
    class FullStack {
    };
    
    class EmptyStack {
    };
    
    template <class ItemType>
    class StackType {
    public:
    	StackType(); //생성자
    	StackType(int max); //최대 크기가 정해져 있을 때의 생성자
    	~StackType(); //동적 할당이기 때문에 소멸자 필요
    	void MakeEmpty();
    	void Push(ItemType item);
    	void Pop();
    	bool IsEmpty() const;
    	bool IsFull() const;
    	ItemType Top();
    private:
    	int top;
    	int maxStack;
    	// 동적 메모리를 할당받을 Array Stack
    	ItemType* items;
    };

• StackTypeDynamic.cpp

  • Stack이 가지는 함수들의 기능을 실제로 구현해 놓은 파일

    #include "StackTypeDynamic.h"
    
    template <class ItemType>
    StackType<ItemType>::StackType() {
    	//최대 크기 지정 안 해 주면 500으로 설정
    	maxStack = 500; 
    	top = -1;
    	items = new ItemType[maxStack];
    }
    
    template<class ItemType>
    StackType<ItemType>::StackType(int max) {
    	maxStack = max;
    	top = -1;
    	items = new ItemType[maxStack];
    }
    
    template<class ItemType>
    void StackType<ItemType>::MakeEmpty() {
    	top = -1;
    	//동적 메모리 해제
    	delete[] items;
    }
    
    template<class ItemType>
    bool StackType<ItemType>::IsEmpty() const {
    	return (top == -1);
    }
    
    template<class ItemType>
    bool StackType<ItemType>::IsFull() const {
    	return (top == maxStack - 1);
    }
    
    template<class ItemType>
    void StackType<ItemType>::Push(ItemType item) {
    	if (IsFull()) {
    		throw FullStack();
    	}
    	else {
    		top++;
    		items[top] = item;
    	}
    }
    
    template<class ItemType>
    void StackType<ItemType>::Pop() {
    	if (IsEmpty()) {
    		throw EmptyStack();
    	}
    	else {
    		top--;
    	}
    }
    
    template<class ItemType>
    ItemType StackType<ItemType>::Top() {
    	if (IsEmpty()) {
    		throw EmptyStack();
    	}
    	else {
    		return items[top];
    	}
    }
    
    template<class ItemType>
    StackType<ItemType>::~StackType() {
    	delete[] items;
    }

• Time Complexity

  Function	Time Complexity
  MakeEmpty	O(1)
  IsFull	O(1)
  IsEmpty	O(1)
  Push	O(1)
  Pop	O(1)
  Top	O(1)

Stack with Python

class Stack:
    #리스트를 이용한 스택 구현
    def __init__(self):
        self.stack = []
    #스택 크기 반환
    def __len__(self) -> bool :
        return len(self.stack)
    #스택에 원소 삽입
    def push(self, item):
        self.stack.append(item)
    #스택 가장 위에 있는 원소를 삭제하고 반환   
    def pop(self):
        if not self.isEmpty():
            return self.stack.pop(-1)
        else:
            print("Stack underflow")
            exit()
    #스택 가장 위에 있는 원소를 반환
    def peek(self):
        if not self.isEmpty():
            return self.stack[-1]
        else:
            print("Stack underflow")
            exit()
    #스택이 비어있는 지를 bool값으로 반환
    def isEmpty(self) -> bool :
        return len(self.stack)==0

• Python 내장 Library에서는 따로 Stack을 제공하지 않는다
• 보통 deque Library를 import해서 많이 사용한다
• 공식 문서 collections — Container datatypes — Python 3.8.16 documentation
  

from collections import deque

# 스택 기능 구현을 위해 필요한 함수
dq = deque() # 덱 생성
dq.append(item) # 덱의 가장 오른쪽에 원소 삽입
# dq.appendleft(item) # 덱의 가장 왼쪽에 원소 삽입
# dq.pop() # 덱의 가장 왼쪽 원소 반환
dq.popleft() # 가장 왼쪽 원소 반환
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) #x와 같은 원소의 개수를 계산

# 이외의 함수들
dq.insert(i, item) # i번째에 item 삽입
dq.remove(item) # item 삭제
dq.reverse() # 역방향으로 뒤집기
dq.extend(iterable) # iterable item 오른쪽에 이어붙이기
dq.extendleft(iterable) # iterable item 왼쪽에 이어붙이기