스택, 큐, 데큐, 힙

스택

C++

int stack[MAX_SIZE];
int stack_size;

void stack_init() {
    stack_size = 0;
}

bool stack_push(int val) {
    if (stack_size == MAX_SIZE) return false;
    stack[stack_size++] = val;
    return true;
}

int stack_pop() {
    return stack[--stack_size];
}

bool stack_empty() {
    return stack_size == 0;
}

Swift

struct Stack<Element> {
  private var storage = Array<Element>()
  var stackPointer: Int {
    storage.count
  }
  mutating func push(_ element: Element) {
    storage.append(element)
  }
  mutating func pop() -> Element? {
    storage.popLast()
  }
}

큐

C++

int queue[MAX_SIZE];
int queue_front;
int queue_rear;

void queue_init() {
    queue_front = 0;
    queue_rear = 0;
}

bool queue_push(int val) {
    if ((queue_rear + 1) % MAX_SIZE == queue_front) {
        return false;
    }
    queue[queue_rear] = val;
    queue_rear = (queue_rear + 1) % MAX_SIZE;
    return true;
}

int queue_pop() {
    int val = queue[queue_front];
    queue_front = (queue_front + 1) % MAX_SIZE;
    return val;
}

bool queue_empty() {
    return queue_front == queue_rear;
}

Swift

import Foundation

protocol Queue {
  associatedtype Element
  var isEmpty: Bool { get }
  mutating func enqueue(_ element: Element)
  mutating func dequeue() -> Element?
}

struct SimpleQueue<Element>: Queue {
  private var storage = Array<Element>()
  var isEmpty: Bool {
    storage.isEmpty
  }
  mutating func enqueue(_ element: Element) {
    storage.append(element)
  }
  mutating func dequeue() -> Element? {
    storage.isEmpty ? nil : storage.removeFirst()
  }
}

struct FastQueue<T>: Queue {
  private static var initialCapacity: Int { 3 }
  private var storage = Array<T?>(repeating: nil, count: FastQueue.initialCapacity)
  private var capacity = FastQueue.initialCapacity
  private var dequeuingIndex = 0
  private var enqueuingIndex = 0
  private var isFull: Bool {
    dequeuingIndex == enqueuingIndex && storage[dequeuingIndex] != nil
  }
  var isEmpty: Bool {
    dequeuingIndex == enqueuingIndex && storage[dequeuingIndex] == nil
  }
  
  mutating func enqueue(_ element: T) {
    if isFull {
      let copy = storage
      storage = Array<T?>(repeating: nil, count: capacity * 2)
      enqueuingIndex = dequeuingIndex + capacity
      for newIndex in dequeuingIndex..<enqueuingIndex {
        let oldIndex = newIndex % capacity
        storage[newIndex] = copy[oldIndex]
      }
      capacity *= 2
    }
    storage[enqueuingIndex] = element
    enqueuingIndex = (enqueuingIndex + 1) % capacity
  }
  
  mutating func dequeue() -> T? {
    guard let value = storage[dequeuingIndex] else { return nil }
    storage[dequeuingIndex] = nil
    dequeuingIndex = (dequeuingIndex + 1) % capacity
    return value
  }
}

데큐

int deque[MAX_SIZE];
int front;
int rear;

void init() {
    front = 0;
    rear = 0;
}

bool push_back(int val) {
    if ((rear + 1) % MAX_SIZE == front) {
        return false;
    }
    deque[rear] = val;
    rear = (rear + 1) % MAX_SIZE;
    return true;
}

bool push_front(int val) {
    if ((front - 1) % MAX_SIZE == rear) {
        return false;
    }
    front = (front - 1 + MAX_SIZE) % MAX_SIZE;
    deque[front] = val;
    return true;
}

int pop_back() {
    rear = (rear - 1 + MAX_SIZE) % MAX_SIZE;
    return deque[rear];
}

int pop_front() {
    int val = deque[front];
    front = (front + 1) % MAX_SIZE;
    return val;
}

bool empty() {
    return front == rear;
}

힙(우선순위 큐) - min heap

C++

int heap[MAX_SIZE];
int size = 0;

void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

void push(int x) {
    if (size == sizeof(heap)) return;
    int pos = size + 1;
    heap[pos] = x;
    while (pos > 1) {
        if (heap[pos / 2] > heap[pos]) {
            swap(heap[pos], heap[pos/2]);
        }
        else break;
        pos /= 2;
    }
    size++;
}

int top() {
    return heap[1];
}

int pop() {
    int min = heap[1];
    swap(heap[1], heap[size]);
    size--;
    int pos = 1;
    while (pos * 2 <= size) {
        int smaller_child = pos * 2;
        if (pos * 2 + 1 <= size && heap[pos * 2] > heap[pos * 2 +1]) {
            smaller_child++;
        }
        if (heap[pos] > heap[smaller_child]) {
            swap(heap[pos], heap[smaller_child]);
            pos = smaller_child;
        } else {
            break;
        }
    }
    return min;
}

Swift

import Foundation

struct Heap<Element> {
  private var storage: Array<Element?>
  private var firstIsCloseToIdeal: (Element, Element) -> Bool
  
  init(capacity: Int, firstIsCloseToIdeal: @escaping (Element, Element) -> Bool) {
    storage = Array<Element?>(repeating: nil, count: capacity + 1)
    self.firstIsCloseToIdeal = firstIsCloseToIdeal
  }
  var size: Int = 0
  func top() -> Element? {
    storage[1]
  }
  mutating func push(_ element: Element) -> Bool {
    guard size < storage.count - 1 else { return false }
    var index = size + 1
    storage[index] = element
    while index > 1 {
      guard let parent = storage[index / 2], let current = storage[index], firstIsCloseToIdeal(parent, current) == false else { break }
      storage.swapAt(index / 2, index)
      index /= 2
    }
    size += 1
    return true
  }
  mutating func pop() -> Element? {
    guard let top = self.top() else { return nil }
    storage.swapAt(1, size)
    storage[size] = nil
    size -= 1
    var index = 1
    while index * 2 <= size, let leftChild = storage[index * 2] {
      var idealChildIndex = index * 2
      if index * 2 + 1 <= size, let rightChild = storage[index * 2 + 1], firstIsCloseToIdeal(rightChild, leftChild) {
        idealChildIndex += 1
      }
      guard let current = storage[index], let idealChild = storage[idealChildIndex], firstIsCloseToIdeal(idealChild, current) else { break }
      storage.swapAt(idealChildIndex, index)
      index = idealChildIndex
    }
    return top
  }
}