# 1.栈实现队列 2.队列实现栈 3.带min的栈 4.数组中第k大的数 5.中位数

``````class Queue {
public:
stack stk1;    // push
stack stk2;    // pop
// Push element x to the back of queue.
void push(int x) {
stk1.push(x);
}
// Removes the element from in front of queue.
void pop(void) {
if(stk2.empty())
{
while(!stk1.empty())
{
int top = stk1.top();
stk1.pop();
stk2.push(top);
}
}
stk2.pop();
}
// Get the front element.
int peek(void) {
if(stk2.empty())
{
while(!stk1.empty())
{
int top = stk1.top();
stk1.pop();
stk2.push(top);
}
}
return stk2.top();
}
// Return whether the queue is empty.
bool empty(void) {
return stk1.empty()&&stk2.empty();
}
};
``````
``````class Stack {
public:
// Push element x onto stack.
queue queue1;
queue queue2;
void push(int x) {
if (queue1.empty())
{
queue1.push(x);
while(!queue2.empty()){
int tmp = queue2.front();
queue2.pop();
queue1.push(tmp);
}
}else{
queue2.push(x);
while(!queue1.empty()){
int tmp = queue1.front();
queue1.pop();
queue2.push(tmp);
}
}
}

// Removes the element on top of the stack.
void pop() {
if (!queue1.empty())
queue1.pop();
if (!queue2.empty())
queue2.pop();
}

// Get the top element.
int top() {
if (!queue1.empty())
return queue1.front();
if (!queue2.empty())
return queue2.front();
}

// Return whether the stack is empty.
bool empty() {
return queue1.empty() && queue2.empty();
}
};
``````
``````class MinStack {
public:
stack allStack;
stack minSta;

void push(int x) {
if (allStack.empty()) {
allStack.push(x);
minSta.push(x);
}
else {
allStack.push(x);
if (x <= minSta.top()) minSta.push(x);
}
}

void pop() {
if (allStack.top() == minSta.top()) {
minSta.pop();
}
allStack.pop();
}

int top() {
return allStack.top();
}

int getMin() {
return minSta.top();
}
};
``````
``````//第一种
class Solution {
public:
int findKthLargest(vector& nums, int k) {
//max heap method
//min heap method
//order statistics
make_heap(nums.begin(), nums.end());
int result;
for(int i=0; i& nums, int k) {
int high = nums.size();
int low = 0;
while (low < high) {
int i = low;
int j = high-1;
int pivot = nums[low];
while (i <= j) {
while (i <= j && nums[i] >= pivot)
i++;
while (i <= j && nums[j] < pivot)
j--;
if (i < j)
swap(nums[i++],nums[j--]);
}
swap(nums[low],nums[j]);

if (j == k-1)
return nums[j];
else if (j < k-1)
low = j+1;
else
high = j;
}
}
};
``````
``````class MedianFinder {
private:
priority_queue ,less> maxHeap;           // 保存较小数
priority_queue,greater> minHeap;        // 保存较大数
public:

// Adds a number into the data structure.
maxHeap.push(num);//往较小的数中添加
int t = maxHeap.top(); //返回较小数中的最大数
maxHeap.pop();
minHeap.push(t);//并将其添加到较大数中
int maxLen = maxHeap.size();
int minLen = minHeap.size();
if (minLen - maxLen > 0)
{
int t = minHeap.top();
maxHeap.push(t);
minHeap.pop();
}
}

// Returns the median of current data stream
double findMedian() {
if (maxHeap.size() > minHeap.size())
return maxHeap.top()*1.0;
else if (maxHeap.size() < minHeap.size())
return minHeap.top()*1.0;
else
return (minHeap.top() + maxHeap.top()) / 2.0;
}
};
``````