(本文参考《剑指offer》总结笔记,供学习使用)
栈是一种常见的数据结构,在操作系统中会给每个进程创建一个栈来存储函数调用时各个函数的参数、返回地址以及临时变量等。栈的特点是后进先出。
队列是另外一种很重要的数据结构,队列的特点是先进先出。
例:用两个栈实现队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
队列声明:
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>
void
CQueue<T>::appendTail(
const
T& element)
{
stack1.push(element);
}
template
<
typename
T> T CQueue<T>::deleteHead()
{
if
(stack2.size()<=0)
{
while
(stack1.size()>0)
{
T& data=stack1.top();
stack1.pop();
stack2.push(data);
}
}
if
(stack2.size()==0)
throw
new
exception(
"queue is empty"
);
T head=stack2.top();
stack2.pop();
return
head;
}
|
本文转自 叫我北北 51CTO博客,原文链接:http://blog.51cto.com/qinbin/1919903