（说明：本博客中的题目、题目详细说明及参考代码均摘自 “何海涛《剑指Offer：名企面试官精讲典型编程题》2012年”）
题目
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点功能。
template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void); void appendTail(const T& node);
T deleteHead();
};
进一步详细说明：
在上述队列的声明中可以看出，一个队列包含两个栈 stack1 和 stack2，因此这道题的意图是要求我们操作这两个 “先进后出” 的栈实现一个 “先进先出” 的队列 CQueue。
算法设计思想
因为栈是后进先出的数据结构，当将数据依次压入第一个栈后，再依次从这个栈弹出，压入第二个栈，如果此时从第二个栈中获取数据，表现正好像一个 “先进先出” 的队列数据结构。
具体来说，使用两个栈实现一个队列，可以考虑用第一个栈（stack1）存放输入的元素（队尾元素），从第二个栈（stack2）获取队头元素。当第一栈（stack1）为空时，将第二个栈（stack2）中的全部元素依次弹出，再依次压入第一个栈中。其过程如图 2.8 所示，
C++ 实现
#include <iostream>
#include <stack>
#include <exception> template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void); void appendTail(const T& node);
T deleteHead(); private:
std::stack<T> stack1;
std::stack<T> stack2;
}; // Declare queue empty exception when try to pop when the queue is empty.
class QEmptyException: public std::exception {
virtual const char* what() const throw()
{
return "Error: Queue is empty!";
}
} popException; // stack1 as input stack, stack2 as output stack
template <typename T>
void CQueue<T>::appendTail(const T& node)
{
stack1.push(node);
} template <class T>
T CQueue<T>::deleteHead()
{
// Check if there are elements in stack2
if (stack2.empty())
{
// Pop all the elements from stack1, then push them onto stack2
if (stack1.size() > )
{
while (!stack1.empty())
{
T elem = stack1.top();
stack1.pop();
stack2.push(elem);
}
}
else
throw popException;
} // Get the top element from stack2, then delete it from stack2
T elem = stack2.top();
stack2.pop(); return elem;
} template <typename T>
CQueue<T>::CQueue(void)
{
} template <typename T>
CQueue<T>::~CQueue(void)
{
} void unitest()
{
CQueue<int> que; std::cout << "Push 1, 2, 3 successively into CQueue." << std::endl;
que.appendTail();
que.appendTail();
que.appendTail();
std::cout << "Pop the head of the queue: " << que.deleteHead() << std::endl;
std::cout << "Pop the head of the queue: " << que.deleteHead() << std::endl;
std::cout << "Push 4, 5, 6 successively into CQueue." << std::endl;
que.appendTail();
que.appendTail();
que.appendTail();
// Pop the rest elements in the queue, until the queue empty exception happens
for (int i = ; i < ; ++i)
{
std::cout << "Pop the head of the queue: " << que.deleteHead() << std::endl;
} } int main()
{
unitest(); return ;
}
Python 实现
#!/usr/bin/python
# -*- coding: utf8 -*- class CQueue:
def __init__(self):
self.stack1 = []
self.stack2 = [] def append_tail(self, elem):
self.stack1.append(elem) def delete_head(self):
if not self.stack2:
if self.stack1:
while self.stack1:
elem = self.stack1.pop()
self.stack2.append(elem)
else:
raise Exception("Queue is empty.") elem = self.stack2.pop()
return elem def unitest():
# Create an instance of class CQueue
que = CQueue()
print "Push 1, 2, 3 successively into CQueue."
for i in range(1, 4):
que.append_tail(i)
print "Pop the head of the queue:", que.delete_head()
print "Pop the head of the queue:", que.delete_head()
print "Push 4, 5, 6 successively into CQueue."
for i in range(4, 7):
que.append_tail(i)
# Pop the rest elements in the queue
for i in range(4):
print "Pop the head of the queue:", que.delete_head() if __name__ == '__main__':
unitest()
参考代码
1. targetver.h
#pragma once // The following macros define the minimum required platform. The minimum required platform
// is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run
// your application. The macros work by enabling all features available on platform versions up to and
// including the version specified. // Modify the following defines if you have to target a platform prior to the ones specified below.
// Refer to MSDN for the latest info on corresponding values for different platforms.
#ifndef _WIN32_WINNT // Specifies that the minimum required platform is Windows Vista.
#define _WIN32_WINNT 0x0600 // Change this to the appropriate value to target other versions of Windows.
#endif
2. stdafx.h
// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
// #pragma once #include "targetver.h" #include <stdio.h>
#include <tchar.h> // TODO: reference additional headers your program requires here
3. stdafx.cpp
// stdafx.cpp : source file that includes just the standard includes
// QueueWithTwoStacks.pch will be the pre-compiled header
// stdafx.obj will contain the pre-compiled type information #include "stdafx.h" // TODO: reference any additional headers you need in STDAFX.H
// and not in this file
4. Queue.h
#pragma once
#include <stack>
#include <exception> using namespace std; template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void); // 在队列末尾添加一个结点
void appendTail(const T& node); // 删除队列的头结点
T deleteHead(); private:
stack<T> stack1;
stack<T> stack2;
}; template <typename T> CQueue<T>::CQueue(void)
{
} template <typename T> CQueue<T>::~CQueue(void)
{
} template<typename T> void CQueue<T>::appendTail(const T& element)
{
stack1.push(element);
} template<typename T> T CQueue<T>::deleteHead()
{
if(stack2.size()<= )
{
while(stack1.size()>)
{
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
} if(stack2.size() == )
throw new exception("queue is empty"); T head = stack2.top();
stack2.pop(); return head;
}
5. Queue.cpp
#include "StdAfx.h"
#include "Queue.h"
#include <queue>
6. QueueWithTwoStacks.cpp
// QueueWithTwoStacks.cpp : Defines the entry point for the console application.
// // 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者：何海涛 #include "stdafx.h"
#include "Queue.h" void Test(char actual, char expected)
{
if(actual == expected)
printf("Test passed.\n");
else
printf("Test failed.\n");
} int _tmain(int argc, _TCHAR* argv[])
{
CQueue<char> queue; queue.appendTail('a');
queue.appendTail('b');
queue.appendTail('c'); char head = queue.deleteHead();
Test(head, 'a'); head = queue.deleteHead();
Test(head, 'b'); queue.appendTail('d');
head = queue.deleteHead();
Test(head, 'c'); queue.appendTail('e');
head = queue.deleteHead();
Test(head, 'd'); head = queue.deleteHead();
Test(head, 'e'); return ;
}
7. 参考代码下载
项目 07_QueueWithTwoStacks 下载： 百度网盘
何海涛《剑指Offer：名企面试官精讲典型编程题》 所有参考代码下载：百度网盘
参考资料
[1] 何海涛. 剑指 Offer：名企面试官精讲典型编程题 [M]. 北京：电子工业出版社，2012. 58-62.