Stack

자료구조

STACK

$DELETE$연산에 의해 집합에서 삭제되는 원소가 미리 결정되어 있는 동적 집합이다. 자료구조에서 입력은 수열로 한정한다. 가장 최근에 삽입된 원소가 삭제된다. 후입선출^LIFO 정책을 구현한 것이다.
데이터가 들어오는 입구와 나가는 출구가 같으며, 반대편은 막혀있는 상자라고 생각하면 된다. 스택은 뷔페에 쌓여있는 접시를 보고 가져온 단어이다.

속성
$S[1,…,n]$ : 최대 n개의 원소를 가지는 스택
$S.top$ : 가장 최근에 삽입된 원소
$S[S.top]$ : 제일 위에 있는 원소

연산
스택의 동작을 생각해본다면, $INSERT,DELETE, EMPTY$ 세 가지 연산이 있다. 그리고 데이터가 없을 때 $PUSH$하는 것(underflow), 데이터가 다 찼을 때 $POP$하는 것(overflow)에 대해서도 고려해야 한다.

$STACK-EMPTY(S)$

if S.top == 0
    return TRUE
else return FALSE

STACK-EMPTY 연산을 통해 스택이 비었는지를 검사할 수 있다.
STACK-EMPTY 출력은 boolean 값이다.

$Insert - PUSH$

PUSH(S,x)
S.top = S.top + 1 // S.top가 원소의 개수 n을 초과하는 경우    
S[S.top] = x

$Delete - POP(S)$

POP(S)
if STACK-EMPTY(S) // 빈 스택에서 원소를 추출하려는 경우
    error "underflow"
else S.top = S.top - 1
   return S[S.top+1]

위 세가지 스택 연산은 $O\left(1\right)$ 수행시간을 갖는다.

Python 구현

랜덤한 수 10,000개의 데이터를 CSV file로 만들고, 그 파일을 리스트로 만든다.
그리고 그 리스트롤 STACK-PUSH 연산의 입력값으로 넣는다. 스택이 된 자료구조에서 Pop, IsEmpty 등의 연산도 시행해본다. 그렇게 만들어진 리스트를 다시 CSV 파일로 만든다.

• 추가 구현해야할 것
  • class listcsv
    1. makeRandomCsv() : 입력 파라미터값으로 리스트 개수 정의, 랜덤옵션, 파일이름 설정 가능하도록. 입력값이 없을 경우엔 클래스 내부 변수 가져다 쓰기.
  • class stack
    1. Push() : input type으로 수열, 숫자형의 데이터만 받고 싶음.
    2. 지금은 stack에 원소의 개수 제한은 없지만, 추후엔 n개의 원소배열만 가지도록 하기. 왜냐하면 스택은 최대 n개의 원소를 가지는 의 조건이 있기 때문이다. 이 조건이 없다면 무한히 push 가 가능하다.

# CSV와 List 간 왔다 갔다리
# 데이터 개수 정의, 파일이름, 숫자 배열 랜덤하게 가능하도록
class listcsv:
    def __init__(self):
        self.__fn = 'output.csv'
        self.__n = 10000
        self.__op = 'r'

    def makeRandomCsv(self):
        '''
        if isinstance(n, int):
            pass
        else:
            ValueError("The type of n must be intager")

        if op in ('r','o'):
            pass
        else:
            ValueError("op must be either 'r' or 'o'")

        if n is None:
            n = self.__n
        numarr = np.arange(n)

        if name:
            self.__fn = name

        if op is None:
            op = self.__op
        elif op is 'r':
            numarr=np.random.choice(numarr,n)
        elif op is 'o':
            numarr=np.arange(n)
        else:
            ValueError("plz input your op")

        '''
        import csv
        import numpy as np
        numarr = np.arange(self.__n)
        numarr=np.random.choice(numarr,self.__n)
        f=open(self.__fn,'w',encoding='utf-8')
        wr=csv.writer(f)
        wr.writerow(numarr)

    def tolist(self):
        f=open(self.__fn,'r',encoding='utf-8')
        alist=[]
        while True:
            line=f.readline().rstrip("\n")
            if line:
                line=line.split(",")
                for i in line:
                    alist.append(int(i))
            else:
                break
        return alist

    def toCsv(self,args):
        import csv

        if isinstance(args, list):
            pass
        else:
            ValueError("The type of input must be a list")


        with open('listfile.csv','w',newline='') as f:
            writer = csv.writer(f)
            writer.writerow(args)

    def csvlist(self):
        self.makeRandomCsv()
        return self.tolist()

# 수열 list만 들어온다고 가정함, n개의 제한이 없음
# todo : 1) input type 으로 수열, 숫자형의 데이터만 받고 싶음
# 2) n개의 원소만 가진다는 것을 확인해야 함..
class Stack:
    def __init__(self):
        self.__top = 0
        self.__arr = []

    def IsEmpty(self):
        if self.__top == 0:
            return True
        else:
            return False

    def Push(self,x):
        if isinstance(x, list):
            for i in x:
                if isinstance(i, (int, float)):
                    self.__top = self.__top + 1
                    self.__arr.append(i)
                else:
                    print(type(i))
                    raise ValueError("The Elementry in list is not a number")
        else:
            raise ValueError("Input type must be a number or number list")

    def Pop(self):
        if self.IsEmpty():
            raise ValueError("underflow")
        else:
            print(self.__arr[self.__top-1])
            self.__top = self.__top -1
            del self.__arr[self.__top]

    def Peek(self):
        return self.__top

    def nowStack(self):
        return self.__arr

(colab 확인)[https://colab.research.google.com/drive/1M2stfq7hshpvYZoEdrEPZWuQ6Jk4PnKy?usp=sharing]