Stack, Queue

Stack(스택)

Stack은 LIFO(Last In First Out)의 특징을 가지는 자료구조다.
스택은 자료를 저장할 때, 먼저 넣은 데이터를 가장 나중에 꺼내게 된다 반대로 가장나중에 넣은 데이터는 가장 만저 꺼낸다

Stack 구현

Struct Stack<T> {
	private var stack<T> = []
    
    public var count: Int {
    	return stack.count
	}
    
    public var isEmpty: Bool {
    	return stack.isEmpty
   }
   
   	public mutating func push(_ element: T) {
   		stack.append(element)
   }
   
   public mutating func pop() -> T? {
   		return isEmpty ? nil : stack.popLast()
   }
}


var myStack = Stack<Int>()
myStack.push(10)
myStack.pop()

Stack은 마지막에 element가 추가되고 마지막 element가 삭제되기 때문에 시간복잡도는 O(1)이 된다

Queue(큐)

Queue는 FIFO(First In First Out)의 특성을 가지는 자료구조입니다. 가장 먼저 넣은 데이터를 가장 먼저 꺼내고 가장 나중에 넣은 데이터를 마지막에 꺼낸다

Queue구현

struct Queue<T> {
	private var queue: [T] = []
    
    public var count: Int {
    	return queue.count
    }
    
    public var is Empty: Bool {
    	return queue.isEmpty
   	}
   
   	public mutating func enqueue(_ element: T) {
    	queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
    	return isEmpty ? nil : queue.removeFirst()
  	}
}

var myQueue = Queue<Int>()
myQueue.enqueue(10)
myQueue.dequeue()

Queue를 배열로 구현하기 때문에 가장 앞에 있는 element를 삭제하게 되면은 1번인덱스 부터 마지막까지 앞으로 당겨져야하는 과정이 있어 시간복잡도는 O(n)이 돼 효율성이 떨어지게된다...

효율적인 Queue

dequeue시 배열의 앞을 당겨주는 것을 최소화 해보겠다
삭제 해야하는 배열의 원소를 nil로 바꿔주고 배열의 앞부분을 가리키는 head를 옮겨준는 것이다
그 후 dequeue를 하면서 쌓인 nil들을 어느정도 일정 주기에 따라 지워주면 된다.

struct Queue<T> {
	private var queue: [T?] = []
    private var head: Int = 0
    
    public var count: Int {
    	return queue.count
    }
    
    public var isEmpty: Bool {
    	return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
    	queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
    	guard head <= queue.count, let element = queue[head] else {return}
        queue[head] = nil
        head += 1
        
        if head > queue.count / 4 {
        	queue.removeFirst(head)
            head = 0
        }
        return element
    }

}