[자료구조]Stack, Queue 구현

가장 기본적인 자료구조인 스택과 큐를 python 코드를 이용해 구현해보겠습니다.

Stack

후입선출 특성의 자료구조(Last In First Out)

1. 배열을 이용한 구현

1. 스택을 위한 배열 선언(최대 크기 설정) / index = 0
2. index가 선언한 배열의 크기 이상이면 stack 꽉 찬 상태 / index = 0 이면 비어있는 상태

• push() : index 자리에 값 추가, index+=1
• pop() : index에 위치한 값 리턴, index-=1
• 모든 연산의 시간 복잡도 : O(1)

class arrayStack:
    def __init__(self):
        self.array  = [] #maxSize 설정. 
        self.top = -1

    def isEmpty(self):
        if self.top==-1:
            return True
        
        else:
            return False

    def push(self, data):
        self.array.append(data)
        self.top+=1
        
    def pop(self):
        if self.isEmpty():
            return -1
        data = self.array[self.top]
        self.top-=1
        return data
    def peek(self):
        if self.isEmpty():
            return -1
        data = self.array[self.top]
        return data

2. 연결 리스트를 이용한 구현

1. 스택의 크기가 고정되어 있지 않게 됨 (python, java에서 제공하는 stack의 구현 방식)
2. 메모리에 값을 위한 공간 할당
3. 메모리 상에 순서와 관계 없이 새로운 값이 추가되면 포인터로 연결(포인터를 위한 공간 추가적으로 필요하다.)

• push() : newNode 추가, newNode의 link에 top 저장→ top = newNode
• pop() : top의 data 반환(다른 변수에 저장 후 반환하면 된다.), top = top의 link → top 앞의 메모리 해제
• 모든 연산의 시간 복잡도 : O(1)

class Node:
    def __init__(self, data=0, link=None):
        self.data = data
        self.link = link
class Stack:
    def __init__(self):
        self.top = None
  
    def push(self, data):
        newNode = Node(data)
        newNode.link = self.top
        self.top = newNode
        
    def pop(self):
        if self.isEmpty():
            return -1
        data = self.top.data
        self.top = self.top.link
        return data
    
    def isEmpty(self):
        if self.top != None:
             return False
        return True
 
    def peek(self):
        if self.isEmpty():
             return -1
        return self.top.data

Queue

선입선출 특성의 자료구조 (First in First Out)

1. 배열을 이용한 일반적인 큐 구현

1. 오버헤드가 발생한다.
2. 데이터의 출구와 입구가 다르기 때문에 push, pop 연산마다 모든 데이터의 위치가 한 칸씩 이동된다.
3. 인덱스만 변경하는 방식도 있지만 이 경우에 공간을 낭비하게 된다. 이를 해결하기 위해 원형 큐를 사용할 수 있다.
4. front에서 pop, rear에서 push

• 연산 속도 : 모든 데이터를 밀어서 관리하는 경우 시간 복잡도 O(N) / pointer를 이용하여 메모리를 낭비하는 경우 시간 복잡도 O(1) 

class arrayQueue:
    def __init__(self):
        self.array = []
        self.front = 0
        self.rear = 0
        self.maxSize = 1000
    def isEmpty(self):
        return self.front == self.rear #0 or 1
    
    def isFull(self):
        return self.rear == self.maxSize
    
    def push(self,data):
        if not self.isFull():
            self.array.append(data)
            self.rear+=1
        
    def pop(self):
        if not self.isEmpty():
            data = self.array[self.front]
            self.front+=1
            return data
        
    def peek(self):
        data = self.array[self.front]
        return data

 

2. 배열을 이용한 원형 큐 구현

1. 큐를 위한 배열 선언(최대 크기 설정) / front, rear = 0
2. front에서 pop, rear에서 push
3. maxSize+1로 배열을 만들어 더미 공간을 만든다( empty와 full의 상태를 구분하기 위함이다.)

• 모든 연산의 시간 복잡도 : O(1)

class circleQueue:
    def __init__(self):
        maxSize = 10
        self.maxSize = maxSize+1 # front의 첫번째 공간부터 데이터를 넣지 않고 더미 공간 -> full / empty 구분
        self.front = 0
        self.rear = 0
        self.array = [None] * maxSize
        
    def isEmpty(self):
        return self.front == self.rear
    
    def isFull(self):
        return self.front == (self.rear+1)%self.maxSize
    
    def push(self,data):
        if not self.isFull():
            self.rear = (self.rear+1)%self.maxSize
            self.array[self.rear] = data

    def pop(self):
        if not self.isEmpty():
            self.front = (self.front+1)%self.maxSize
            return self.array[self.front]
            
    def peek(self):
        if not self.isEmpty():
            return self.array[self.front+1]

3. 연결 리스트를 이용한 구현

1. front에서 pop, rear에서 push
2. 연결 리스트를 이용한 stack과 마찬가지로 queue의 크기가 고정되어 있지 않게 됨.

• 모든 연산의 시간 복잡도 : O(1)

class Node:
    def __init__(self,data=0, link=None):
        self.data = data
        self.link = link
    
class Queue:
    def __init__(self):
        self.front = 0
        self.rear = 0
    
    def isEmpty(self):
        if self.front == 0 and self.rear==0:
            return True
        else:
            return False
    
    def push(self, data):
        newNode = Node(data)
        if self.isEmpty():
            self.front = newNode
            self.rear = newNode
        else:
            self.rear.link = newNode
            self.rear = newNode
    
    def pop(self):
        if not self.isEmpty():
            data = self.front
            self.front = self.front.link
            return data.data
        
    def peek(self):
        if not self.isEmpty():
            return self.front.data