堆栈相关面试题（详解）_c语言面试 堆栈

1. 实现一个栈，要求实现Push（出栈）、Pop(入栈)、Min(返回最小值的操作)时间复杂度为O(1)。

分析：设计两个栈，一个栈用来push 、pop操作，另一个栈用来保存当前最小值Min。当push元素小于等于Min栈顶元素时，将其压入Min栈顶，当pop元素等于Min栈顶元素时，两个栈均要pop出栈顶元素。下图为各种情况的优缺点分析。

class StackWithMin
{
public:
	StackWithMin()
	{}
 
	~StackWithMin()
	{}
 
	void Push(const int& x)
	{
		s1.push(x);
		if(s2.empty() || x <= s2.top())
		{
			s2.push(x);
		}
	}
 
	void Pop()
	{
		assert(s1.size()>0 && s2.size()>0);
		if(s1.top() == s2.top())
		{
			s2.pop();
		}
		s1.pop();
	}
 
	int Min()
	{
		assert(s1.size()>0 && s2.size()>0);
 
		return s2.top();
	}
private:
	stack<int> s1;
	stack<int> s2; //用于保存最下元素
};

2. 使用两个栈实现一个队列。

分析：一个栈用来push数据，一个栈用来pop数据。

图解

实现

//使用两个栈实现一个队列。
class Queue
{
public:
    void push(int node) {
        stack1.push(node);
    }
 
    int pop() {
        if(stack2.empty())
		{
			while(!stack1.empty())
			{
				stack2.push(stack1.top());
				stack1.pop();
			}
		}
 
		int top = stack2.top();
		stack2.pop();
		return top;
    }
 
private:
    stack<int> stack1;
    stack<int> stack2;
};

 

3. 使用两个队列实现一个栈。

分析：使用两个队列不断的倒换元素，实现一个栈。下面为图解，以及代码的实现过程。

图解

#include<iostream>
#include<queue>
using namespace std;
 
template <class T>
class QueueToStack
{
public:
	QueueToStack()
	{}
 
	~QueueToStack()
	{}
 
	void Push(T x)
	{
		if(q1.size()>0)//若q1不为NULL时，在q1中插入
		{
			q1.push(x);
		}
		else if(q2.size()>0)//若q2不为NULL时，在q1中插入
		{
			q2.push(x);
		}
		else
		{
			q1.push(x);//两者均为NULL时，插入到q1
		}
	}
 
	void Pop()
	{
		if(q1.size()==0)//如果queue1为空
		{
			while(q2.size()>1)//保证queue2中有一个元素，将其余元素保存到queue1中
			{
				q1.push(q2.front());
				q2.pop();
			}
			q2.pop();
 
		}
		else//如果queue2为空
		{
			while(q1.size()>1)//保证queue2中有一个元素，将其余元素保存到queue1中
			{
				q2.push(q1.front());
				q1.pop();
			}
			q1.pop();
 
		}
 
	}
 
	T Top()
	{
		if(q1.size()==0)//如果queue1为空
		{
			while(q2.size()>1)//保证queue2中有一个元素，将其余元素保存到queue1中
			{
				q1.push(q2.front());
				q2.pop();
			}
			T& data=q2.front();
			q1.push(q2.front());
			q2.pop();
			return data;
		}
		else//如果queue2为空
		{
			while(q1.size()>1)//保证queue2中有一个元素，将其余元素保存到queue1中
			{
				q2.push(q1.front());
				q1.pop();
			}
			T& data=q1.front();
			q2.push(q1.front());
 
			q1.pop();
			return data;
		}
	}
 
	bool Empty()
	{
		return (q1.empty() && q2.empty());
	}
 
private:
	queue<T> q1;
	queue<T> q2;
};

4. 元素出栈、入栈顺序的合法性。如入栈的序列（1，2，3，4，5），出栈序列为（4，5，3，2，1）。

分析：借助辅助栈，如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，把压栈序列中还没有入栈的数字压人辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

class Solution {
public:
   bool IsPopOrder(vector<int> pushV,vector<int> popV) 
	{
		if(pushV.size() == 0 || popV.size() == 0)
		{
			return false;
		}
 
        if(pushV.size() != popV.size())
		{
			return false;
		}
 
		stack<int> s; //借助辅助栈
		int j=0;
		for(int i=0; i<popV.size(); ++i)
		{
			s.push(pushV[i]);
 
			//当栈顶元素和出栈序列元素相等时，出栈
			while(j<popV.size() && s.top() == popV[j])
			{
				s.pop();
				++j;
			}
		}
 
		return s.empty();
    }
};

5. 一个数组实现两个栈。

   分析：一个数组实现两个栈，分别从数据开始，和数组末端实现。当两个指针相当时，进行扩容。扩容时，需要将原数组的数据写入新数组。

#include <iostream>
#include<assert.h>
using namespace std;
 
template<class T>
class TwoStack
{
public:
	//构造
	TwoStack()
		:_arr(NULL)
		,_top1(0)
		,_top2(0)
		,_capacity(0)
	{
		CheckCapacity();
	}
 
	//析构
	~TwoStack()
	{
		if(NULL != _arr) //_arr不为NULL时，释放_arr
		{
			delete[] _arr;
		}
	}
 
	//拷贝构造
	TwoStack(const TwoStack<T>& ts)
		:_arr(new T[ts._capacity-ts._top2+ts._top1])
		,_top1(ts._top1)
		,_top2(_top1)
		,_capacity(ts._capacity-ts._top2+ts._top1)
	{
		//拷贝数据
		for(size_t i=0; i<_top1; i++)
		{
			_arr[i] = ts._arr[i];
		}
 
		size_t j = ts._capacity-1;
		for(size_t i=_capacity-1; i>_top2;i--,j--)
		{
			_arr[i] = ts._arr[j];
		}
	}
 
	//复制运算符重载
	TwoStack<T>& operator=(TwoStack<T> ts)
	{
		int * tmp = ts._arr;
		_top1 = ts._top1;
		_top2 = ts._top2;
		_capacity = ts._capacity;
		swap(_arr,tmp);
		return *this;
	}
 
	//push 、pop、top、size、empty
	void Push1(const int& x)
	{
		CheckCapacity();
		_arr[_top1++] = x;
	}
 
	void Push2(const int& x)
	{
		CheckCapacity();
		_arr[_top2--] = x;
	}
 
	void Pop1()
	{
		if(Size1() == 0)
		{
			return;
		}
 
		--_top1;
	}
 
	void Pop2()
	{
		if(Size2() == 0)
		{
			return;
		}
 
		--_top2;
	}
 
	int Top1()
	{
		assert(_top1 > 0);
 
		return _arr[_top1-1];
	}
 
	int Top2()
	{
		assert(_top2 < _capacity-1);
 
		return _arr[_top2+1];
	}
 
	size_t Size1()
	{
		return _top1;
	}
 
	size_t Size2()
	{
		return _capacity - _top2 - 1;
	}
 
	bool Empty1()
	{
		if(_top1 == 0)
		{
			return true;
		}
		return false;
	}
 
	bool Empty2()
	{
		if(_top2 == _capacity-1)
		{
			return true;
		}
 
		return false;
	}
 
protected:
	void CheckCapacity()
	{
		//1.开始时扩容  2._top1 == _top2时，扩容
 
		if(NULL == _arr)//开始时，当数组为NULL时，给_arr分配空间
		{
			_capacity += 2;
			_arr = new int[_capacity];
			_top2 = _capacity - 1;
 
			return;
		}
 
		if(_top1 == _top2) //如果_top1==_top2时，应该进行扩容
		{
			size_t newcapacity = _capacity*2;
			int* tmp = new int[newcapacity];
			//拷贝数据
			for(size_t i=0; i<_top1; ++i)
			{
				tmp[i] = _arr[i];
			}
			size_t j = newcapacity - 1;
			for(size_t k=_capacity-1; k>_top2; --k)
			{
				tmp[j] = _arr[k];
				--j;
			}
 
			_top2 = j;
			_capacity = newcapacity;
			_arr = tmp;
		}
	}
 
private:
	T * _arr; //析构时，应销毁数组中的内容
	size_t _top1; //top1、top2分别表示栈的下标
	size_t _top2;
	size_t _capacity;
};