• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

剑指 Offer 09. 用两个栈实现队列

难度:简单

栈A用于加入队列尾操作,栈B用于颠倒元素的顺序,从而删除队列头的元素。

类队列{

LinkedListInteger A,B;

公共CQueue() {

a=new linked listinteger();

b=new linked listinteger();

}

public void appendTail(int value){

A.addLast(值);

}

public int deleteHead() {

如果(!B.isEmpty())返回b . remove last();

if(A.isEmpty())返回-1;

而(!A.isEmpty())

b . add last(a . remove last());

返回b . remove last();

}

}

作者:Krahets

链接:3359 leet code-cn.com/leet book/read/illustration-of-algorithm/5dq0t 5/

资料来源:LeetCode

版权归作者所有。商业转载请联系作者授权,非商业转载请注明出处。

注意Stack继承了Vector接口,Vector底层是Object[]数组,需要考虑空间扩展和位移的问题,是线程安全的,性能不高。可以用LinkedList作为Stack的容器,因为LinkedList实现了Deque接口,所以LinkedList可以做Stack能做的一切,而且它的结构是双向链表,容量扩展消耗较少。

此外,该注释指出,官方建议的创建堆栈的方式如下:

DequeInteger stack=new array deque();

时间复杂度:O(1),空间复杂度O(N)。

剑指 Offer 30. 包含 min 函数的栈

难度:简单

借助辅助堆栈(非严格降序):

分类小册子{

StackInteger A,B;

public MinStack() {

a=new Stack();

b=new Stack();

}

public void push(int x) {

a . add(x);

if(B.empty() || B.peek()=x)

b . add(x);

}

公共void pop() {

if(A.pop()。equals(B.peek()))

b . pop();

}

public int top() {

返回a . peek();

}

public int min() {

返回b . peek();

}

}

作者:Krahets

链接:3359 leet code-cn.com/leet book/read/illustration-of-algorithm/50JE8m/

资料来源:LeetCode

版权归作者所有。商业转载请联系作者授权,非商业转载请注明出处。

为了便于理解,这里仍然使用Stack。其实推荐LinkedList。

时间复杂度:O(1),空间复杂度O(N)。

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now