预备知识：

栈：   取出栈顶元素: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() 当队列为空时，返回truesize() 返回队列的长度*/ #include "stdafx.h"#include 
     
      #include
      
       using namespace std;//创建两个队列对象(之前没写using namespace std，就一直说deque是未声明的标识符)//一个用于存储当前信息，如果调用pop函数，则会用上另一个队列queue
       
        stack_model_one;queue
        
         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
     
      #include
      
       using namespace std;//入队（无意中get了传递容器的技能，打个码MARK!!!!!!!!!!!!!!!!!!!）void push(stack
       
        &input_stack, int m) {	input_stack.push(m);	cout << "入队成功" << endl;}//出队void pop(stack
        
         &input_stack, stack
         
          &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
          
           input_stack; stack
           
            output_stack; char k='i'; int n = 0, m = 0; cout<<"push操作请输入“1”"<
            
             > 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
     
      #include
      
       using namespace std;template
       
        >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 << "栈顶元素为：" <
        
         << 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 << "最小元素是：" <
         
          << 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
     
      #include"model.h"using namespace std;int main(){	Stack
      
        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<<"请输入要入栈的值"<
       
        > 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
     
      #include
      
       using namespace std;int main(){	cout << "请输入要输入的元素个数" << endl;	int m = 0, temp = 0;	while (cin >> m) {		//创建一个数组，用于存储输入的数字串		int *array;		array = (int *)malloc(sizeof(int)*m);		stack
       
        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<<"数字串不是栈顺序"<
       
      
     

上面自己写的算法的时间复杂度太大，需要修改。

老师讲解的方法：

同时使用一个队列与一个栈来解决该问题

设队列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
     
      & nums, int k) {        sort(nums.begin(),nums.end());        int temp=0;        temp=nums.size()-k;        return nums[temp];    }};
     

方法二，优先队列

LeetCode 295

方法：动态维护一个 最大堆 与一个 最小堆 ，最大堆存储一半数据，最小堆存储

一半数据， 维持 最大堆的堆顶比最小堆的堆顶小，即可解决该问题。