[medium]用栈实现队列

难度: 中等 标题:用栈实现队列

正如标题所述,你需要使用两个栈来实现队列的一些操作。

队列应支持push(element),pop() 和 top(),其中pop是弹出队列中的第一个(最前面的)元素。

pop和top方法都应该返回第一个元素的值。

思路

两个栈,stack1与stack2.stack2中元素顺序和入栈顺序完全相反。每次插入时把stack2里所有数据插入到stack1,然后插入元素到stack1末尾,再倒回stack2.

代码

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
public class Queue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;

public Queue() {
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
}

public void push(int element) {
if (stack2.empty()){
stack2.push(element);
} else {
while (!stack2.empty()){
stack1.push(stack2.pop());
}
stack1.push(element);
while (!stack1.empty()){
stack2.push(stack1.pop());
}
}
}

public int pop() {
return stack2.pop();
}

public int top() {
return stack2.peek();
}
}

链接

http://www.lintcode.com/zh-cn/problem/implement-queue-by-two-stacks/

[easy]链表倒数第n个节点

难度: 简单 标题:链表倒数第n个节点

找到单链表倒数第n个节点,保证链表中节点的最少数量为n。

思路

可以选择两个指针,指向第一个(first)和第N个(end)。然后每次first前进一格,则end也前进一格,知道end == null时,first指向的就是倒数第n个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
ListNode nthToLast(ListNode head, int n) {
ListNode first = head;
ListNode end = head;
for (int i=0;i<n;i++){
end = end.next;
}
while(end != null){
end = end.next;
first = first.next;
}
return first;
}
}

链接

http://www.lintcode.com/zh-cn/problem/nth-to-last-node-in-list/

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×