1 class FreqStack {
 2     var freq:[Int:Int]
 3     var m:[Int:[Int]]
 4     var maxfreq:Int
 5     init() {
 6         freq = [Int:Int]()
 7         m = [Int:[Int]]()
 8         maxfreq = 0        
 9     }
10     
11     func push(_ x: Int) {
12         var f:Int = freq[x,default:0] + 1
13         freq[x] = f
14         maxfreq = max(maxfreq, f)
15         m[f,default:[Int]()].append(x)      
16     }
17     
18     func pop() -> Int {
19         var x:Int = m[maxfreq,default:[Int]()].popLast() ?? 0
20         freq[x] = maxfreq - 1
21         if m[maxfreq,default:[Int]()].count == 0 {maxfreq -= 1}
22         return x     
23     }
24 }
25 
26 /**
27  * Your FreqStack object will be instantiated and called as such:
28  * let obj = FreqStack()
29  * obj.push(x)
30  * let ret_2: Int = obj.pop()
31  */
32  

 1 class FreqStack {
 2     
 3     var appearancesByValues = [Int: Int]()
 4     var valuesByAppearances = [Int: [Int]]()
 5 
 6     var maxAppearances = 1
 7     let emptySet = Set<Int>()
 8 
 9     init() {
10 
11     }
12 
13     func push(_ x: Int) {
14 
15         let appearances = self.appearancesByValues[x, default: 0] + 1
16         self.appearancesByValues[x] = appearances
17 
18         if appearances > self.maxAppearances {
19             self.maxAppearances = appearances
20         }
21         self.valuesByAppearances[appearances, default: []].append(x)
22 
23     }
24 
25     func pop() -> Int {
26 
27         let value = (self.valuesByAppearances[self.maxAppearances]?.popLast())!
28 
29         self.appearancesByValues[value]! -= 1
30 
31         if self.valuesByAppearances[self.maxAppearances]?.count == 0 {
32             self.maxAppearances -= 1
33         }
34 
35         return value
36     }
37 }

 1 class FreqStack {
 2     
 3     var freq: [Int: Int] // num: freq
 4     var group: [Int: [Int]] // freq: stack of elements w/ same freq
 5     var maxFreq: Int
 6 
 7     init() {
 8         self.freq = [Int: Int]()
 9         self.group = [Int: [Int]]()
10         self.maxFreq = 0
11     }
12     
13     func push(_ x: Int) {
14         let f = (freq[x] ?? 0) + 1
15         freq[x] = f
16         if var stack = group[f] {
17             stack.append(x)
18             group[f] = stack
19         } else {
20             group[f] = [x]
21         }
22         if f > maxFreq {
23             maxFreq = f
24         }
25     }
26     
27     func pop() -> Int {
28         var stack = group[maxFreq]!
29         let result = stack.removeLast()
30         freq[result] = maxFreq - 1
31         group[maxFreq] = stack
32         if stack.count == 0 {
33             maxFreq -= 1
34         }
35         return result
36     }
37 }

 1 class FreqStack {
 2 
 3     init() {
 4         
 5     }
 6     
 7     func push(_ x: Int) {
 8         let f = elem2Freq[x, default: 0] + 1
 9         elem2Freq[x] = f
10         let sz = subStacks.count
11         if f >= sz {
12             subStacks.append([x])
13         } else {
14             subStacks[f].append(x)
15         }
16     }
17     
18     func pop() -> Int {
19         let sz = subStacks.count
20         let x = subStacks[sz - 1].popLast()!
21         if subStacks[sz - 1].isEmpty {
22             subStacks.removeLast()
23         }
24         elem2Freq[x, default: 0] -= 1
25         return x
26     }
27     
28     var elem2Freq = [Int: Int]()
29     var subStacks = [[Int]()]
30 }

  1 public struct PriorityQueue<T: Comparable> {    
  2     fileprivate var heap = [T]()
  3     private let ordered: (T, T) -> Bool
  4     
  5     public init(ascending: Bool = false, startingValues: [T] = []) {
  6         self.init(order: ascending ? { $0 > $1 } : { $0 < $1 }, startingValues: startingValues)
  7     }
  8     
  9     // Creates a new PriorityQueue with the given ordering.
 10     // - parameter order: A function that specifies whether its first argument should
 11     //   come after the second argument in the PriorityQueue.
 12     // - parameter startingValues: An array of elements to initialize the PriorityQueue with.
 13     public init(order: @escaping (T, T) -> Bool, startingValues: [T] = []) {
 14         ordered = order
 15         
 16         //Based on "Heap construction" from Sedgewick p 323
 17         heap = startingValues
 18         var i = heap.count/2 - 1
 19         while i >= 0 {
 20             sink(i)
 21             i -= 1
 22         }
 23     }
 24     
 25     // How many elements the Priority Queue stores
 26     public var count: Int { return heap.count }
 27     
 28     // true if and only if the Priority Queue is empty
 29     public var isEmpty: Bool { return heap.isEmpty }
 30     
 31     // Add a new element onto the Priority Queue. O(lg n)
 32     // - parameter element: The element to be inserted into the Priority Queue.
 33     public mutating func push(_ element: T) {
 34         heap.append(element)
 35         swim(heap.count - 1)
 36     }
 37     
 38     // Remove and return the element with the highest priority (or lowest if ascending). O(lg n)
 39     // - returns: The element with the highest priority in the Priority Queue, or nil if the PriorityQueue is empty.
 40     public mutating func pop() -> T? {
 41         
 42         if heap.isEmpty { return nil }
 43         // added for Swift 2 compatibility
 44         if heap.count == 1 { return heap.removeFirst() } 
 45         // so as not to call swap() with two instances of the same location
 46         heap.swapAt(0, heap.count - 1)
 47         let temp = heap.removeLast()
 48         sink(0)
 49         
 50         return temp
 51     }
 52     
 53     private mutating func sink(_ index: Int) {
 54         var index = index
 55         while 2 * index + 1 < heap.count {            
 56             var j = 2 * index + 1            
 57             if j < (heap.count - 1) && ordered(heap[j], heap[j + 1]) { j += 1 }
 58             if !ordered(heap[index], heap[j]) { break }            
 59             heap.swapAt(index, j)
 60             index = j
 61         }
 62     }
 63     
 64     // Based on example from Sedgewick p 316
 65     private mutating func swim(_ index: Int) {
 66         var index = index
 67         while index > 0 && ordered(heap[(index - 1) / 2], heap[index]) {
 68             heap.swapAt((index - 1) / 2, index)
 69             index = (index - 1) / 2
 70         }
 71     }
 72 }
 73 
 74 struct Entry: Comparable {
 75     let x: Int
 76     let priority: Int
 77     
 78     static func == (lhs: Entry, rhs: Entry) -> Bool {
 79         return lhs.priority == rhs.priority
 80     }
 81     
 82     static func < (lhs: Entry, rhs: Entry) -> Bool {
 83         return lhs.priority < rhs.priority
 84     }
 85     
 86     static func <= (lhs: Entry, rhs: Entry) -> Bool {
 87         return lhs.priority <= rhs.priority
 88     }
 89 
 90     static func > (lhs: Entry, rhs: Entry) -> Bool {
 91         return lhs.priority > rhs.priority
 92     }
 93     
 94     static func >= (lhs: Entry, rhs: Entry) -> Bool {
 95         return lhs.priority >= rhs.priority
 96     }
 97 }
 98 
 99 class FreqStack {
100     
101     var pq: PriorityQueue<Entry>
102     var freq: [Int: Int] = [:]
103     
104     init() {
105         pq = PriorityQueue<Entry>(ascending: false, startingValues: [])
106     }
107     
108     let maxN = 10000
109     var pushCount = 0
110     func push(_ x: Int) {
111         let count = freq[x, default: 0] + 1
112         freq[x] = count
113         pushCount += 1
114         pq.push(Entry(x: x, priority:  count * maxN + pushCount))
115     }
116     
117     func pop() -> Int {
118         let entry = pq.pop()!
119         freq[entry.x] = freq[entry.x]! - 1
120         return entry.x
121     }
122 }
123 
124 /**
125  * Your FreqStack object will be instantiated and called as such:
126  * let obj = FreqStack()
127  * obj.push(x)
128  * let ret_2: Int = obj.pop()
129  */