预备知识：
栈： 取出栈顶元素:S.top()； 判断栈是否为空 :S.empty()； 将元素x 添加 至栈:S.push(x)
弹出栈顶:S.pop()； 求栈存储元素的 个数 :S.size()
队列：判断队列是否为空 :Q.empty()； 返回队列头部元素:Q.front()； 返回队列尾部元素:Q.back() 弹出 队列头部元素:Q.pop()； 将元素x 添加 至队列:Q.push(x)； 求队列存储元素的个数 :Q.size()
LeetCode 255
一开始想把队列改写了，发现queue的源码是改了deque做的，deque的基础结构我懂，但是以我现在的技术来看，改起来还有点困难，所以就想到用两个队列来实现栈的功能。
以后有机会再写一个改了deque实现栈功能的版本吧，先打个码。
/*Implement the following operations of a stack using queues.
push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.
Notes:
You must use only standard operations of a queue
– which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively.
You may simulate a queue by using a list or deque (double-ended queue),
as long as you use only standard operations of a queue.
You may assume that all operations are valid (有效的)
(for example, no pop or top operations will be called on an empty stack).
队列的一些基本操作
push(x) 将x压入队列的末端
pop() 弹出队列的第一个元素(队顶元素)，注意此函数并不返回任何值
front() 返回第一个元素(队顶元素)
back() 返回最后被压入的元素(队尾元素)
empty() 当队列为空时，返回true
size() 返回队列的长度
*/
#include "stdafx.h"
#include <iostream>
#include<queue>
using namespace std;
//创建两个队列对象(之前没写using namespace std，就一直说deque是未声明的标识符)
//一个用于存储当前信息，如果调用pop函数，则会用上另一个队列
queue<int>stack_model_one;
queue<int>stack_model_two;
//push(x) – Push element x onto stack.
void push(int m) {
//找到当前栈
//如果两个队列都为空，则存入第一个队列，此时应该是首次push
if (stack_model_one.empty()&& stack_model_two.empty()) {
stack_model_one.push(m);
cout << "入栈成功" << endl;
}
//第一个队列为空，第二个队列不为空，此时当前栈是第二个队列
else if (stack_model_one.empty() && !stack_model_two.empty()) {
stack_model_two.push(m);
cout << "入栈成功" << endl;
}
//第二个队列为空，第一个队列不为空，此时当前栈是第一个队列
else if (stack_model_two.empty()&&!stack_model_one.empty()) {
stack_model_one.push(m);
cout << "入栈成功" << endl;
}
else {
cout << "入栈失败" << endl;
}
}
//pop() – Removes the element on top of the stack.
void pop( int length) {
int p = 0;
if (stack_model_one.empty() && stack_model_two.empty()) {
cout << "出栈失败" << endl;
}
//第一个队列为空，第二个队列不为空，此时当前栈是第二个队列
else if (stack_model_one.empty() && !stack_model_two.empty()) {
//将第二队列前length的元素赋值给队列一，然后将队列二制空
for (int i = 0; i < length;i++) {
stack_model_one.push(stack_model_two.front());
stack_model_two.pop();
}
//删除队列二的最后一个元素
stack_model_two.pop();
cout << "出栈成功" << endl;
}
//第二个队列为空，第一个队列不为空，此时当前栈是第一个队列
else if (stack_model_two.empty() && !stack_model_one.empty()) {
//将第一队列前length的元素赋值给队列二，然后将队列一制空
for (int i = 0; i < length; i++) {
stack_model_two.push(stack_model_one.front());
stack_model_one.pop();
}
//删除队列一的最后一个元素
stack_model_one.pop();
cout << "出栈成功" << endl;
}
else {
cout << "入栈失败" << endl;
}
}
//top() – Get the top element.
void top() {
if (stack_model_one.empty() && stack_model_two.empty()) {
cout << "无栈顶元素" << endl;
}
//第一个队列为空，第二个队列不为空，此时当前栈是第二个队列
else if (stack_model_one.empty() && !stack_model_two.empty()) {
cout << "栈顶元素为：" << stack_model_two.back() << endl;
}
//第二个队列为空，第一个队列不为空，此时当前栈是第一个队列
else if (stack_model_two.empty() && !stack_model_one.empty()) {
cout << "栈顶元素为：" << stack_model_one.back() << endl;
}
else {
cout << "栈顶元素获取失败" << endl;
}
}
//empty() – Return whether the stack is empty.
void empty() {
//如果两个队列都为空，则栈为空
if (stack_model_one.empty() && stack_model_two.empty()) {
cout << "当前为空栈" << endl;
}
else if (stack_model_one.empty() && !stack_model_two.empty()) {
cout << "当前栈不为空" << endl;
}
else if (stack_model_two.empty() && !stack_model_one.empty()) {
cout << "当前栈不为空" << endl;
}
else {
cout << "栈是否为空判断失败" << endl;
}
}
int main()
{
cout << "push操作请输入“1”" << endl;
cout << "pop操作请输入“2”" << endl;
cout << "top操作请输入“3”" << endl;
cout << "empty操作请输入“4”" << endl;
//用于记录输入的操作序号
int n = 0;
//用于记录输入的值
int m=0;
//用于记录队列的长度
int length = 0;
while (1) {
cin >> n;
//输入你要运行的操作
switch (n) {
case 1:
cout << "输入要插入的值" << endl;
cin >> m;
push( m);
length++;
break;
case 2:
//传入length-1，直接保留length长度的信息就好
pop( length-1);
length--;
break;
case 3:
top ();
break;
case 4:
empty();
break;
default:
break;
}
}
return 0;
}
老师讲解的方法：
使用队列实现栈——当push元素时，先将存储数据的队列中的元素存入临时队列，push之后再把临时队列中的元素push到存储数据的队列中。
使用栈实现队列——当push元素时，先将存储数据的栈中的元素存入临时栈中，push之后再把临时栈中的元素push到存储数据的栈中。
老师讲解的方法：
双栈法，即用两个栈 ，来实现队列的功能。一个栈为输入栈input_stack，一个栈为输出栈output_stack。
push操作时，将元素压入input_stack。pop操作时，当output_stack不为空时，直接弹出栈顶元素，为空，则将input_stack的元素全部压入output_stack中。 如此，时间复杂度只有O(1)
下面是自己实现的双栈法。
#include "stdafx.h"
#include<iostream>
#include<stack>
using namespace std;
//入队（无意中get了传递容器的技能，打个码MARK!!!!!!!!!!!!!!!!!!!）
void push(stack<int >&input_stack, int m) {
input_stack.push(m);
cout << "入队成功" << endl;
}
//出队
void pop(stack<int >&input_stack, stack<int >&output_stack) {
//当output_stack为空
if (output_stack.empty()) {
//将input_stack元素全部压入output_stack
while (!input_stack.empty()) {
output_stack.push(input_stack.top());
input_stack.pop();
}
output_stack.pop();
cout << "出队成功" << endl;
}
//当output_stack不为空
else {
output_stack.pop();
cout << "出队成功" << endl;
}
}
int main()
{
stack<int>input_stack;
stack<int>output_stack;
char k='i';
int n = 0, m = 0;
cout<<"push操作请输入“1”"<<endl;
cout << "pop操作请输入“2”" << endl;
while (1) {
cin >> n;
switch (n) {
case 1:
cout << "请输入要加入的元素" << endl;
cin >> m;
push(input_stack, m);
break;
case 2:
pop(input_stack, output_stack);
break;
default:break;
}
}
return 0;
}
LeetCode 155
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
model.h文件：改写了queue，写了一个实现要求功能的文件。时间复杂度是O(n)，这个方法不是特别好。
#pragma once
#ifndef _STACK_
#define _STACK_
#include<iostream>
#include<queue>
using namespace std;
template<class T,class Sequence=queue<T>>
class Stack {
protected:
Sequence c;
Sequence d;
private:
int m;
public:
//push(x) --Push element x onto stack.
void push(int m) {
if (c.empty() && d.empty()) {
c.push(m);
cout << "入栈成功" << endl;
}
else if (!c.empty() && d.empty()) {
c.push(m);
cout << "入栈成功" << endl;
}
else if (c.empty() && !d.empty()) {
d.push(m);
cout << "入栈成功" << endl;
}
else {
cout << "入栈失败，特殊原因" << endl;
}
}
//pop() --Removes the element on top of the stack.
void pop() {
if (c.empty() && d.empty()) {
cout << "出栈失败" << endl;
}
else if (!c.empty() && d.empty()) {
c.pop();
cout << "出栈成功" << endl;
}
else if (c.empty() && !d.empty()) {
d.pop();
cout << "出栈成功" << endl;
}
else {
cout << "出栈失败，特殊原因" << endl;
}
}
//top() --Get the top element.
void top() {
if (c.empty() && d.empty()) {
cout << "获取栈顶元素失败" << endl;
}
else if (!c.empty() && d.empty()) {
while (c.size() > 1) {
d.push(c.front());
c.pop();
}
//获取栈顶元素
m=c.front();
d.push(c.front());
//排空c中的元素
c.pop();
cout << "栈顶元素为：" <<m<< endl;
}
else if (c.empty() && !d.empty()) {
while (d.size() > 1) {
c.push(d.front());
d.pop();
}
//获取栈顶元素
m = d.front();
c.push(d.front());
//排空c中的元素
d.pop();
cout << "栈顶元素为：" << m << endl;
}
else {
cout << "获取栈顶元素失败，特殊原因" << endl;
}
}
//getMin() --Retrieve the minimum element in the stack.
void getMin() {
if (c.empty() && d.empty()) {
cout << "无最小元素" << endl;
}
else if (!c.empty() && d.empty()) {
m = c.front();
d.push(c.front());
c.pop();
while (c.size() > 0) {
if (m > c.front()) {
m = c.front();
}
d.push(c.front());
c.pop();
}
cout << "最小元素是：" <<m<< endl;
}
else if (c.empty() && !d.empty()) {
m = d.front();
c.push(d.front());
d.pop();
while (d.size() > 0) {
if (m > d.front()) {
m = d.front();
}
c.push(d.front());
d.pop();
}
cout << "最小元素是：" << m << endl;
}
else {
cout << "获取最小元素失败，特殊原因" << endl;
}
}
};
#endif.cpp文件，调用函数
#include "stdafx.h"
#include<iostream>
#include"model.h"
using namespace std;
int main()
{
Stack<int> stack_model;
int n=0,m = 0;
cout << "push操作请输入“1”" << endl;
cout << "pop操作请输入“2”" << endl;
cout << "top操作请输入“3”" << endl;
cout << "getMin操作请输入“4”" << endl;
while (1) {
cin >> n;
switch (n) {
case 1:
cout<<"请输入要入栈的值"<<endl;
cin >> m;
stack_model.push(m);
break;
case 2:
stack_model.pop();
break;
case 3:
stack_model.top();
break;
case 4:
stack_model.getMin();
break;
}
}
return 0;
}老师讲解的方法： 时间复杂度是O(1)
设置两个栈， 数据栈data_stack 与 最小值栈min_stack ，这两个栈对于添加元素push与弹出栈
顶元素pop都是 同步进行 的:
1.push(x) : 将元素x直接压入数据栈data_stack中，若x小于最小值栈栈顶，则将 x 压入 最小值栈中，否则将 最小值栈栈顶压入最小值栈。
2.pop() : 同时弹出( 移除) 数据栈栈顶与最小值栈顶元素。
3.top() : 返回 数据栈data_stack 栈顶元素。
4.getMin() : 返回 最小值栈min_stack 栈顶元素。
POJ 1363
/*
题目大意：
已知火车要从A入站，然后从C出站。火车进站的顺序为1~N，现在给你出站的顺序。
问：能不能通过站台改变火车出站顺序来实现按所给顺序出站。
解题思路：
把站台看做是一个栈，按1~N的顺序遍历火车原先顺序，先入栈，
如果栈顶的火车编号和所给出站顺序将要出站的编号一样。
那么火车就出栈，直到栈里边所有满足出站顺序的火车都出站，否则就一直入栈。
最后判断所有火车是否都出站了。若都出站，输出Yes，否则输出No。
*/
#include"stdafx.h"
#include<iostream>
#include<stack>
using namespace std;
int main()
{
cout << "请输入要输入的元素个数" << endl;
int m = 0, temp = 0;
while (cin >> m) {
//创建一个数组，用于存储输入的数字串
int *array;
array = (int *)malloc(sizeof(int)*m);
stack<int>stack_model;
cout << "请输入需要判断的数字串" << endl;
//将输入的数字串存入数组
for (int i = 0; i < m; i++) {
cin >> temp;
array[i] = temp;
}
//对比元素，值在1~m之间
int flag = 1;
for (int i = 0; i < m; i++) {
//当前值小于等于输入的数字串中需要对比的值时，入栈
while (flag <= array[i]) {
stack_model.push(flag);
flag++;
}
//此时栈顶元素等于array[i]
int cur = stack_model.top();
//如果输入的数字串符合栈，则一共会弹出m次
stack_model.pop();
if (cur != array[i]) {
cout<<"数字串不是栈顺序"<<endl;
break;
}
}
if (stack_model.size() == 0) {
cout<<"数字串是栈顺序"<<endl;
}
}
return 0;
}
上面自己写的算法的时间复杂度太大，需要修改。
老师讲解的方法：
同时使用一个队列与一个栈来解决该问题
设队列order与栈为S。队列order存储待判断是否合法的出栈序列 ，使用栈S用来模拟出栈与入栈的过程。
按照1-n的顺序，将元素 push 进入栈S 中：每push一个元素，即检查栈顶 S.top()是否与队列头部元素order.front()相同。
如果相同则同时弹出栈顶元素与队列头部元素， 直到栈空或栈顶与队列头部元素不同 。
若最终栈为空 ，则说明序列合法 ，否则不合法。
预备知识：堆
我们一般使用二叉堆来实现优先级队列 ，它的内部调整算法复杂度为log(N)， 标准STL 的优先级队列包括如下5 种操作，设堆H:
1.取出堆顶元素:H.top()； 2.判断堆是否为空 :H.empty()； 3.将元素x添加 至堆:H.push(x)
4. 弹出堆顶:H.pop()； 5.求堆存储元素的个数 :H.size()
优先队列根据权值，将入队元素进行排序。只允许一端入队另一端出队。底层容器是vector。
LeetCode 215
思路：快排的时间复杂度是nlogn。感觉这题不是中等难度的题，是easy题。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int temp=0;
temp=nums.size()-k;
return nums[temp];
}
};方法二，优先队列
LeetCode 295
方法：动态维护一个 最大堆 与一个 最小堆 ，最大堆存储一半数据，最小堆存储
一半数据， 维持 最大堆的堆顶比最小堆的堆顶小，即可解决该问题。