【数据结构】(面试题)使用两个栈实现一个队列(详细介绍)
使用两个栈实现一个队列
创新互联建站是一家以网络技术公司,为中小企业提供网站维护、网站建设、成都网站设计、网站备案、服务器租用、域名注册、软件开发、重庆小程序开发等企业互联网相关业务,是一家有着丰富的互联网运营推广经验的科技公司,有着多年的网站建站经验,致力于帮助中小企业在互联网让打出自已的品牌和口碑,让企业在互联网上打开一个面向全国乃至全球的业务窗口:建站咨询电话:028-86922220
思路一:
我们设定s1是入栈的,s2是出栈的。
入队列,直接压到s1即可
出队列,先把s1中的元素倒入到s2中,弹出s2中的栈顶元素;再把s2的剩余元素全部倒回s1中。
缺点:
每次只要出栈一个元素就要将元素倒来倒去,麻烦!!!
思路2:
入队列时:
如果s1为空,把s2中所有的元素倒出压到s1中。否则直接压入s1
出队列时:
如果s2不为空,把s2中的栈顶元素直接弹出。否则,把s1的所有元素全部弹出压入s2中,再弹出s2的栈顶元素
思路1无条件地每次都要将元素倒来倒去,思路2出队时较思路1简单
思路3:
我们设定s1是入栈的,s2是出栈的
入队列:直接压入元素至s1即可
出队列:如果s2不为空,把s2中的栈顶元素直接弹出。否则,把s1的所有元素全部弹出压入s2中,再弹出s2的栈顶元素
相比于方法2,入队直接压入即可~
那么,我们可以看出,思路三最简单,我们下面看下代码。
代码实现:
1)我们直接调用库里的stack来实现。(一般调用库里的就行了)
#define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; //两个栈实现一个队列 #include template class Queue { public: void appendTail(const T& x) { s1.push(x); } void deleteHead() { if (s2.empty()) { while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } cout << s2.top() << " "; s2.pop(); } else { cout << s2.top() << " "; s2.pop(); } } private: stack s1; stack s2; }; void Test() { Queue q; q.appendTail(1); q.appendTail(2); q.appendTail(3); q.appendTail(4); q.deleteHead(); q.deleteHead(); q.deleteHead(); q.deleteHead(); } int main() { Test(); system("pause"); return 0; }
2)自己实现栈实现。
#define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; #include //直接实现Stack,也可以用适配器实现栈,或者用库。 //将Stack基本功能实现如下: template class Stack { public: Stack() :_array(NULL) , _size(0) , _capacity(0) {} Stack (const Stack & s) : _array(new T[s._capacity]) { swap(_array, s._array); swap(_size, s._size); swap(_capacity, s._capacity); } Stack & operator=(const Stack & s) { if (&s != this) { swap(_array, s._array); swap(_size, s._size); swap(_capacity, s._capacity); } return *this; } ~Stack() { if (_array) { delete[] _array; _array = NULL; } } void _CheckCapacity() { if (_size == 0) { _capacity = 3; _array = new T[_capacity]; } if (_size >= _capacity) { _capacity *= 2; T* tmp = new T[_capacity]; for (int index = 0; index < _size; index++) { tmp[index] = _array[index]; } delete[] _array; _array = tmp; } } void Push(const T& x) { _CheckCapacity(); _array[_size++] = x; } void Pop() { if (_size == 0) { return; } --_size; } size_t Size() { return _size; } bool Empty() { return Size() == 0; } T& Top() { assert(_size > 0); return _array[_size - 1]; } private: T* _array; size_t _size; size_t _capacity; }; template class Queue { public: void InQueue(const T& x) { s1.Push(x); } void OutQueue() { //栈s2为空,则将栈s1的元素全部倒入s2中,再弹出最上面的那个元素 if (s2.Empty()) { while (!s1.Empty()) { s2.Push(s1.Top()); s1.Pop(); } s2.Pop(); } //栈s2不为空,直接弹出元素 else { s2.Pop(); } } void Print() //打印队列元素,分四种情况。 { if (s1.Empty() && s2.Empty()) { cout << "The Queue is Empty!"; } else if (!s1.Empty() && s2.Empty()) { while (!s1.Empty()) { s2.Push(s1.Top()); s1.Pop(); } while (!s2.Empty()) { cout << s2.Top() << " "; s2.Pop(); } } else if (s1.Empty() && !s2.Empty()) { while (!s2.Empty()) { cout << s2.Top() << " "; s2.Pop(); } } else { while (!s2.Empty()) { cout << s2.Top() << " "; s2.Pop(); } while (!s1.Empty()) { s2.Push(s1.Top()); s1.Pop(); } while (!s2.Empty()) { cout << s2.Top() << " "; s2.Pop(); } } cout << endl; } private: Stack s1; //入队 Stack s2; //出队 }; //测试两个栈实现一个队列 void Test1() { Queue q1; q1.InQueue(1); q1.InQueue(2); q1.InQueue(3); q1.InQueue(4); /*q1.Print();*/ q1.OutQueue(); /*q1.Print();*/ q1.InQueue(5); q1.InQueue(6); q1.InQueue(7); q1.Print(); } int main() { Test1(); system("pause"); return 0; }
(1个细节):
注意再将元素倒入另一个栈时,代码并不是先pop,再push。因为这样push后元素就找不到了。因此要先访问到栈顶元素top,再push,而后pop。
文章名称:【数据结构】(面试题)使用两个栈实现一个队列(详细介绍)
网站地址:http://pwwzsj.com/article/isjijg.html