|
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
39
40
41
42
43
44
45
46
47
48
49
50
|
/**
* 1.在Java5中新增加了java.util.Queue接口，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。
*
* Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取
* 或移除的元素。他们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。
* 如果要使用前端而不移除该元素，使用element()或者peek()方法。
*
* 值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当初Queue来用。
*
*/
Queue<String> queue =
new
LinkedList<String>();
queue.offer(
"1"
);
queue.offer(
"2"
);
queue.offer(
"3"
);
System.out.println(
"队列的大小："
+ queue.size());
System.out.println(
"toString : "
+ queue.toString());
//循环队列
for
(String str : queue) {
System.out.println(
"队列内容："
+ str);
}
boolean
offerResult = queue.offer(
"4"
);
System.out.println(
"插入队列的结果："
+ offerResult +
" ,队列的大小："
+ queue.size());
System.out.println(
"toString : "
+ queue.toString());
String e = queue.poll();
System.out.println(
"返回删除的头元素 ： "
+ e);
System.out.println(
"toString : "
+ queue.toString());
e = queue.peek();
System.out.println(
"返回头元素，不删除头元素 ： "
+ e);
System.out.println(
"toString : "
+ queue.toString());
e = queue.element();
System.out.println(
"返回头元素，不删除头元素 ： "
+ e);
System.out.println(
"toString : "
+ queue.toString());
System.out.println(
"是否为空队列 ： "
+ queue.isEmpty());
System.out.println(
"队列的大小 ： "
+ queue.size());
System.out.println(
"是否包含相关的元素："
+ queue.contains(
"1"
));
System.out.println(
"是否包含相关的元素："
+ queue.contains(
"2"
));
queue.clear();
System.out.println(
"是否为空队列 ： "
+ queue.isEmpty());
System.out.println(
"队列的大小 ： "
+ queue.size());
System.out.println(
"toString : "
+ queue.toString());
|
2.2014-08-10-如果用2两个栈实现一个队列
参考：http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
package
com.hanchao.test0810;
import
java.util.Stack;
/***********************
* 2个栈实现一个队列方法1
* @author：han
* @version：1.0
* @created：2014-8-10
***********************
*/
public
class
MyQueue1 {
/**
* 思路： 假设有2个栈s1,s2
* ① 入队时，将元素压入s1
* ② 出队时，将s1的元素逐个“倒入”(弹出并压入)s2,
* 将s2的顶元素弹出作为出队元素，
* 之后再将s2剩下的元素逐个“倒回”s1。
*/
private
Stack<String> s1 =
new
Stack<String>();
private
Stack<String> s2 =
new
Stack<String>();
/**
* 入队操作
* *******************
* @param str
* @return
* *******************
* @author：wind
* 2014-8-10 上午11:26:16
* *******************
*/
public
boolean
offer(String str) {
if
(str !=
null
) {
s1.push(str);
return
true
;
}
else
{
return
false
;
}
}
/**
* 出队操作
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 上午11:27:50
* *******************
*/
public
String poll() {
while
(!s1.empty()) {
//s1不为空,把s1的元素倒入s2
s2.push(s1.pop());
}
//取出s2栈顶的元素
String str = s2.pop();
//把s2的元素“倒回”s1
while
(!s2.empty()) {
s1.push(s2.pop());
}
return
str;
}
/**
* 如果s1,s2同时为空，没有意义
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 上午11:31:24
* *******************
*/
public
boolean
empty() {
if
(s1.empty() && s2.empty()) {
return
true
;
}
return
false
;
}
public
static
void
main(String[] args) {
MyQueue1 queue =
new
MyQueue1();
queue.offer(
"aa"
);
queue.offer(
"bb"
);
queue.offer(
"cc"
);
queue.offer(
"dd"
);
while
(!queue.empty()) {
System.out.println(queue.poll());
}
}
}
|
方法2：
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
package
com.hanchao.test0809;
import
java.util.Stack;
/***********************
* 用两个栈实现一个队列2
* @author：han
* @version：1.0
* @created：2014-8-9
***********************
*/
public
class
MyQueue {
/**
* 思路：：
* ①入队时，要判断s2是否为空，为空表示没有出队元素，元素都在s1，可以直接入队
* 如果s2不为空，我们要把s2中的元素"倒回"s1，再压入入队元素。
* ②出队时，要判断s2是否为空，不为空直接弹出s2的顶元素并出队。
* 如果s2为空，判断s1是否为空，不为空把s1“倒入”s2，再把s2的顶元素取出即可。
*
*/
private
Stack<String> s1 =
new
Stack<String>();
private
Stack<String> s2 =
new
Stack<String>();
/**
* 入队操作
* *******************
* @param str
* @return
* *******************
* @author：wind
* 2014-8-10 上午10:04:23
* *******************
*/
public
boolean
offer(String str) {
if
(s2.isEmpty()) {
//如果s2为空，则可以直接向s1添加元素
s1.push(str);
}
else
{
//如果s2不为空，我们要将s2的元素重新倒入s1中
while
(!s2.isEmpty()) {
s1.push(s2.pop());
}
//再把新元素加入s1中
s1.push(str);
}
return
true
;
}
/**
* 出队操作
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 上午10:11:29
* *******************
*/
public
String poll() {
if
(!s2.empty()) {
//如果s2不为空，可以直接出队
return
s2.pop();
}
else
{
//如果s2为空，要判断s1是否为空，s1不为空时，要把s1的元素“倒入”s2中
/*while(!s1.empty()) {
s2.push(s1.pop());
}
return s2.pop();*/
/**
* 此处优化一下：在出队时，将s1的元素“倒入”s2时，
* 原在s1栈底的元素，不用“倒入”s2(即只“倒”s1.count() - 1)
* 可以直接弹出作为出队元素返回。这样可以减少一次压栈的操作
*/
int size = s1.size();
if(size > 0) {
for(int i = 0; i < size - 1; i++) {
s2.push(s1.pop());
}
}
return s1.pop();
}
}
/**
* 如果s1,s2都为空，没有必要出队和入队
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 上午10:20:11
* *******************
*/
public
boolean
empty() {
if
(s1.empty() && s2.empty()) {
return
true
;
}
return
false
;
}
public
static
void
main(String[] args) {
MyQueue queue =
new
MyQueue();
queue.offer(
"aa"
);
queue.offer(
"bb"
);
queue.offer(
"cc"
);
while
(!queue.empty()) {
System.out.println(queue.poll());
}
}
}
|
方法3:
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
package
com.hanchao.test0810;
import
java.util.Stack;
/***********************
* 两个栈实现一个队列：new
* @author：han
* @version：1.0
* @created：2014-8-10
***********************
*/
public
class
MyQueueNew {
/**
* 思路：s1是入栈的，s2是出栈的。
* 入队列时：直接压入s1即可。
* 出队列时：如果s2不为空，把s2中的栈顶元素直接弹出；
* 否则，把s1的所有元素全部弹出压入s2中，再把弹出的s2的栈顶元素
*/
private
Stack<String> s1 =
new
Stack<String>();
private
Stack<String> s2 =
new
Stack<String>();
/**
* 入队操作
* *******************
* @param str
* @return
* *******************
* @author：wind
* 2014-8-10 上午11:15:12
* *******************
*/
public
boolean
offer(String str) {
s1.push(str);
return
true
;
}
/**
* 出队操作
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 上午11:16:18
* *******************
*/
public
String poll() {
/*if(!s2.empty()) {
//如果s2不为空，直接出队
return s2.pop();
} else {
//如果s2为空，要把s1的元素全部倒入s2中
while(!s1.empty()) {
s2.push(s1.pop());
}
return s2.pop();
}*/
/**
* 优化一下：
*/
if(s2.empty()) {
while(!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
/**
* 如果s1和s2都为空，没有出队的意义
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 上午11:19:51
* *******************
*/
public
boolean
empty() {
if
(s1.empty() && s2.empty()) {
return
true
;
}
return
false
;
}
public
static
void
main(String[] args) {
MyQueueNew queue =
new
MyQueueNew();
queue.offer(
"aa"
);
queue.offer(
"bb"
);
queue.offer(
"cc"
);
queue.offer(
"cc1"
);
while
(!queue.empty()) {
System.out.println(queue.poll());
}
}
}
|
二：用2个队列实现一个栈
参考：http://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
package
com.hanchao.test0809;
import
java.util.LinkedList;
import
java.util.Queue;
/***********************
* 用2个队列实现一个栈1
* @author：han
* @version：1.0
* @created：2014-8-10
***********************
*/
public
class
MyStack1 {
/**
* 思路：队列q1,队列q2
* q1是专职进出栈的，q2只是一个临时中转站
*
* 入栈时：直接入队列q1即可
* 出栈时：把q1的除最后一个元素外全部其他元素转移到队列q2中，
* 然后把刚才剩下q1中的那个元素出队列。
*
* 之后把q2的全部元素转移回q1中。
*/
private
Queue<String> q1 =
new
LinkedList<String>();
private
Queue<String> q2 =
new
LinkedList<String>();
/**
* 入栈操作
* *******************
* @param str
* @return
* *******************
* @author：wind
* 2014-8-10 下午12:08:49
* *******************
*/
public
String push(String str) {
q1.offer(str);
return
str;
}
/**
* 出栈操作
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 下午12:09:53
* *******************
*/
public
String pop() {
if
(!q1.isEmpty()) {
//如果q1不为空,把q1的前n-1个元素倒入q2
while
(q1.size() >
1
) {
q2.offer(q1.poll());
}
//取得q1的最后一个元素
String str = q1.poll();
//把q2的元素重新倒入q1
while
(q2.size() >
0
) {
q1.offer(q2.poll());
}
return
str;
}
return
null
;
}
/**
* 如果q1和q2都为空的话，没有意义
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 下午12:14:29
* *******************
*/
public
boolean
empty() {
if
(q1.isEmpty() && q2.isEmpty()) {
return
true
;
}
return
false
;
}
public
static
void
main(String[] args) {
MyStack1 stack =
new
MyStack1();
stack.push(
"aa"
);
//栈底
stack.push(
"bb"
);
stack.push(
"cc"
);
//栈顶
while
(!stack.empty()) {
System.out.println(stack.pop());
}
}
}
|
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
package
com.hanchao.test0809;
import
java.util.LinkedList;
import
java.util.Queue;
/***********************
* 2个队列实现一个栈：2
* @author：han
* @version：1.0
* @created：2014-8-10
***********************
*/
public
class
MyStack2 {
/**
* 思路：队列q1,q2都可以作为进出栈的队列
*
* 对于两个队列实现一个栈，如果我要把刚放的东西再取出来，
* 对于队列来说，只能是把之前的东西都先出队，
* 才能把刚才的放的东西出队。
*
* 故：那就把之前的那些数据先出队列到队列2中。
* 两个队列来回交换数据即可。
*/
private
Queue<String> q1 =
new
LinkedList<String>();
private
Queue<String> q2 =
new
LinkedList<String>();
/**
* 入栈操作
* *******************
* @param str
* @return
* *******************
* @author：wind
* 2014-8-10 下午12:38:33
* *******************
*/
public
String push(String str) {
if
(q2.isEmpty()) {
//如果q2为空，把元素压入q1中
q1.offer(str);
}
else
if
(q1.isEmpty()) {
//如果q1为空，把元素压入q2中
q2.offer(str);
}
return
str;
}
/**
* 出栈操作
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 下午12:39:05
* *******************
*/
public
String pop() {
if
(!q1.isEmpty()) {
//如果q1不为空，从q1出最后一个元素，并把其他的元素移入q2中
while
(q1.size() >
1
) {
q2.offer(q1.poll());
}
return
q1.poll();
}
else
if
(!q2.isEmpty()) {
//如果q2不为空，从q2出最后一个元素，并把其他的元素移入q1中
while
(q2.size() >
1
) {
q1.offer(q2.poll());
}
return
q2.poll();
}
return
null
;
}
/**
* 如果队列q1,q2都为空，没有必要操作
* *******************
* @return
* *******************
* @author：wind
* 2014-8-10 下午12:45:37
* *******************
*/
public
boolean
empty() {
if
(q1.isEmpty() && q2.isEmpty()) {
return
true
;
}
return
false
;
}
public
static
void
main(String[] args) {
MyStack2 stack =
new
MyStack2();
stack.push(
"aa"
);
stack.push(
"bb"
);
stack.push(
"cc"
);
stack.push(
"dd"
);
while
(!stack.empty()) {
System.out.println(stack.pop());
}
}
}
|
本文转自韩立伟 51CTO博客，原文链接：http://blog.51cto.com/hanchaohan/1426863
，如需转载请自行联系原作者
