剑指offer(二):关于栈和队列的一些问题

队列的一些问题"/>

剑指offer(二):关于栈和队列的一些问题

目录

题目一:用两个栈实现队列

题目二:用两个队列实现栈

题目三:包含min的最小栈的问题

题目四:从上到下打印二叉树

题目五:栈的压入,弹出序列

题目六:滑动窗口的最大值

题目一:用两个栈实现队列

题目描述:用两个栈实现一个队列,队列的声明如下,请实现appenTail和deleteHead,分别完成队列尾部插入节点和队列头部删除节点的功能

题解:我们都知道队列是先进先出的数据结构,栈式后进先出的数据结构,我现在要将两个栈去实现队列咱们看看怎么去实现

我们看见了这两个图表示我们的两个栈,我们在第一个栈中添加了1,2,3,4其中1是第一开始进栈的,被压到了最下部分,4是最后进栈的在栈顶,我们想去实现一个队列,就是一开始进容器的先出去,我们就可以将上面三个数据放到另一个栈中,然后将最下部分的1  pop掉,因为我们将数据按照4,3,2的顺序放到了下一个栈中,如果pop()的话正好满足我们先进先出的原则,我们就可以将栈2中的数据一个接一个的pop掉,我们看看代码怎么去实现

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
void appendTail(stack<int>& s1, int val)
{s1.push(val);
}
int deleteHead(stack<int>& s1, stack<int>& s2)
{while (!s1.empty()){s2.push(s1.top());s1.pop();}if (s2.empty()){cout << "队列为空" << endl;}int head =  s2.top();s2.pop();return head;
}
int main()
{//我们先去定义两个栈stack<int>s1;stack<int>s2;s1.push(1);s1.push(2);s1.push(3);s1.push(4);s1.push(5);s1.push(6);appendTail(s1,7);int Pop = deleteHead(s1, s2);cout << Pop << endl;return 0;
}

题目二:用两个队列实现栈

我们现在实现了两个队列,我们将1,2,3,4先后进入队列1中,如果我们要实现一个栈,那么4应该是先出去的,我们来看看借助队列2怎么去实现这个过程

我让1,2,3先进入队列2,只剩下一个4的时候给4  pop()出去,这样我们后加入的4,就可以先出队列了,其他后进队列的元素也要通过这样的方式出队列

我们来看看代码

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
void appendtop(queue<int>& q1, queue<int>q2, int val)
{if (!q1.empty()){q1.push(val);}else if (!q2.empty()){q2.push(val);}else {q1.push(val);}
}
void poptop(queue<int>& q1, queue<int>& q2)
{if (!q1.empty()&&q2.empty()){while (q1.size() != 1){q2.push(q1.front());q1.pop();}q1.pop();}else if (!q2.empty() && q1.empty()){while (q2.size() != 1){q1.push(q2.front());q2.pop();}q2.pop();}if (q2.empty() && q1.empty()){return;}
}
void Print(queue<int>q1, queue<int>q2) {if (!q1.empty() && q2.empty()){while (!q1.empty()){cout << q1.front() << " ";q1.pop();}}if (!q2.empty() && q1.empty()){while (!q2.empty()){cout << q2.front() << " ";q2.pop();}}if (q2.empty() && q1.empty()){return;}
}
int main()
{queue<int>q1;queue<int>q2;q1.push(1);q1.push(2);q1.push(3);q1.push(4);int val = 5;appendtop(q1, q2, val);poptop(q1, q2);Print(q1, q2);system("pause");return 0;
}

题目三:包含min的最小栈的问题

题目描述:定义一个栈,请在该类型中实现一个能够得到栈的最小元素的min函数,在该栈中,调用min,push以及pop的时间复杂度都是O(1)

这个涉及到了辅助栈的问题,假如说我们不开辅助栈,我i们只能对原来栈中数据进行排序,将小的数放到栈顶,但是这样我们的数据结构就不是后进先出的了,因为我们打乱了原来栈中的顺序,假如说我现在给了一些数据,1 2 3 4依次放到了栈中,但是我要对他们进行排序,栈中的栈顶放的就是1,然而我们后放进去的是4,应该先出来4才对,虽然说我们找到了最小的数据,但是我们定义的栈已经不叫栈了,

那我们就开一个辅助栈,我们辅助栈的栈顶放到是最小的元素,在原数据栈中加一个元素,这个元素就要和辅助栈中栈顶的元素去进行比较,如果更小,那就直接放到栈顶,如果大,那栈顶再罗上一个最小的元素

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
//MinStack() 初始化堆栈对象。
//void push(int val) 将元素val推入堆栈。
//void pop() 删除堆栈顶部的元素。
//int top() 获取堆栈顶部的元素。
//int getMin() 获取堆栈中的最小元素
class MinStack {
public:stack<int>YUval;stack<int>Minval;MinStack() {}void push(int val) {if (YUval.empty()){YUval.push(val);Minval.push(val);}else {YUval.push(val);if (Minval.top() > val){Minval.push(val);}else {Minval.push(Minval.top());}}}void pop() {if (YUval.empty()){return;}else {YUval.pop();Minval.pop();}}int top() {if (YUval.empty()){return NULL;}else {return YUval.top();}}int getMin() {if (Minval.empty()){return NULL;}else {return Minval.top();}}
};int main()
{MinStack* MIN = new MinStack();MIN->push(5);MIN->push(3);MIN->push(4);MIN->push(2);MIN->pop();MIN->pop();int param_3 = MIN->top();int param_4 = MIN->getMin();cout << param_3 << " " << param_4 << endl;return 0;
}

题目四:从上到下打印二叉树

题目描述:不分行从上到下打印二叉树,从上到下打印出二叉树的每一个节点,同一层的节点按照从左到右的顺序打印

为了验证我们写出的代码能不能对二叉树进行打印,我们先创建一个二叉树

#include<iostream>
#include<stack>
#include<queue>
#include<stdio.h>
#include<vector>
using namespace std;
typedef string DataType;
struct TreeNode {DataType val;TreeNode* left;TreeNode* right;
};//根据前序来创建一个二叉树
TreeNode* CreateTree(vector<string> a, int* pi)
{if (a[*pi] == "#"){(*pi)++;return NULL;}TreeNode* root = new TreeNode;if (root == NULL){cout << "malloc fail" << endl;exit(-1);}root->val = a[*pi];(*pi)++;root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}//二叉树的创建
int main()
{vector<string> str = {"8","6","5","#","#","7","#","#","10","9","#","#","11","#","#"};int i = 0;TreeNode* root = CreateTree(str, &i);PreTree(root);return 0;
}

我们先看看这个二叉树的图示

我们应该这样一层一层的打印这个二叉树

我们先打印这个二叉树的根节点,再去打印他的左孩子和右孩子,这样我们就用一个队列,我打印完这个节点后,如果说这个节点有左孩子就把它的左孩子加入到队列当中待打印,如果有右孩子,我们再将右孩子加入到队列当中待打印,这样就可以从上到下打印这个二叉树了

我们看代码

//层序遍历打印二叉树void PrintTree(TreeNode* root)
{queue<TreeNode*>q1;if (root == NULL){return;}q1.push(root);while (q1.size()){TreeNode* pNode = q1.front();cout << pNode->val << " ";q1.pop();if (pNode->left != NULL){q1.push(pNode->left);}if (pNode->right != NULL){q1.push(pNode->right);}}
}

题目五:栈的压入,弹出序列

题目描述:输入两个整数序列,第一个序列表示栈的压入顺序,请你判断一个序列是不是该栈的弹出序列,假设压入栈的所有数字均不相等,例如序列{1,2,3,4,5}是某栈的压入序列,序列{4,5,3,2,1}是该栈序列对应的一个弹出序列,但{4,3,5,1,2}不是该栈的弹出序列

#include<iostream>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
bool  EqualPushAndPop(vector<int>& pPush, vector<int>& pPop)
{if (pPush.size() != pPop.size())//如果两个数组的大小不一样,肯定返回false{return false;}stack<int>s1;//定义一个栈int j = 0;//pPop[j]表示第j个元素for (int i = 0; i < pPush.size(); i++){s1.push(pPush[i]);while (!s1.empty() && s1.top() == pPop[j]){j++;s1.pop();}}if (s1.empty()) {return true;}
}
int main()
{vector<int>pPush = {1,2,3,4,5};vector<int>pPop = {4,5,3,2,1};cout << EqualPushAndPop(pPush, pPop);return 0;
}

题目六:滑动窗口的最大值

给定一个数组和一个滑动窗口的大小,请找出所有滑动窗口里的最大值,例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小为3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}

如果说我们用暴力来解题,就是我先遍历一遍整个数组,找到所有的滑动窗口,然后在遍历所有滑动窗口中的元素,时间复杂度是O(nk),那我们想一想有没有时间复杂度小一点的方法

我们可以用C++中的双向队列,来实现滑动窗口找到最大值的操作,同时也可以满足当滑动窗口滑动的时候我们也可以将双向队列中的头元素删除,因为我们要找到所有滑动窗口的最大值,我们用一个数组来接收

#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<deque>
using namespace std;
vector<int> EqualPushAndPop(vector<int>& array, int size)
{vector<int>maxInWindows;if (array.size() >= size && size >= 1) //要保证我们数组里面的元素是比滑动窗口的大小要大的{deque<int>index;for (int i = 0; i < size; i++) //我们先找到第一个滑动窗口,因为第一个滑动窗口不用滑动{while (!index.empty() && array[i] >= array[index.back()]){index.pop_back();//将小于下一个数据的元素出队列}index.push_back(i);//将元素较大的放到前面}for (int i = size; i < array.size(); i++){maxInWindows.push_back(array[index.front()]);//将每一回滑动时deque中第一个时最大的放进去while (!index.empty() && array[i] >= array[index.back()]){index.pop_back();}if (!index.empty() && index.front() <= (int)(i - size))//滑动窗口会进行滑动,会将头一个删除{index.pop_front();}index.push_back(i);}maxInWindows.push_back(array[index.front()]);}return maxInWindows;
}
int main()
{vector<int>array = { 2,3,4,2,6,2,5,1 };int size = 3;vector<int>maxi =  EqualPushAndPop(array,size);for (int i = 0; i < maxi.size(); i++){cout << maxi[i] << " ";}return 0;
}

这样作者告诉我们滑动窗口其实上就是一个队列,我们可以对队列进行操作,来实现滑动窗口