1.栈和队列常见方法
(1)栈：
stack.push()//压栈
stack.pop()//弹栈
stack.empty()==true//栈为空
stack.peek()//返回栈顶元素（只返回不删除）（2）队列：
queue.add()：往队尾添加元素
queue.remove()：删除队头元素（并且返回队头元素）
queue.peek():返回队头元素（只返回不删除）Queue queue=new LinkedList();
queue.add(1)
queue.add(2)
queue.add(3)
queue.add(4)
queue.add(5)
int size=queue.szie();
for(int i=0;
i双端队列：
（1）队列只能在队尾添加元素，在队头删除元素，而双端队列在队头队尾都可以进行添加和删除操作
（2）双端队列Deque的常见方法：（在队列的add，peek，remove方法基础上进行改造）
//创建双端队列
Deque queue=new LinkedList();
//First表示队首，Last表示队尾//在队首添加元素
queue.addFirst();
//在队尾增加元素
queue.addLast();
//获取队首元素
queue.peekFirst();
//获取队尾元素
queue.peekLast();
//移除并且返回队首元素
queue.removeFirst();
queue.removeLast();
【leetcode|leetcode栈和队列】
2.用两个栈实现队列：力扣（剑指offer09）
把栈和队列都想象成一个黑箱子
将1，2，3依次输入到这个黑箱子，如果这个黑箱子是栈，就依次返回3，2，1
如果这个黑箱子是队列，就依次返回1，2，3
加入元素的时候直接加入到stack1里面就行
主要是弹出元素时：弹出元素肯定是弹出stack2中的元素
如果stack2中有元素，就直接stack2.pop()
stack2为空的时候（即stack2中没有元素可以弹出的时候），把stack1中的元素全部转移到stack2中，然后再stack2.pop()
将stack1内的元素全部转移到stack2内 ：
class CQueue
{
Stack stack1;
Stack stack2;
public CQueue()
{
stack1=new Stack();
stack2=new Stack();
}
//往你创建的队列中添加元素
public void appendTail(int value)
{
stack1.push(value);
}
//往你创建的队列中弹出元素
public int deleteHead()
{
//要弹出元素，肯定是弹出stack2这个栈里面的栈顶元素//如果stack2栈内元素为空，stack1内也没元素，那就返回-1
//如果stack2栈内元素为空，stack1内有元素，就把stack1内所有元素转移到stack2里面去/*比如stack1里面添加了四个元素1，2，3，4，现在显然是想要打印出1，2，3，4
所以要把1，2，3，4全部从stack1中压入stack2中，这样不断stack2.pop()才能得到1，2，3，4*/
if(stack2.empty()==true)
{
if(stack1.empty()==true)return -1;
else//如果stack1不为空
{
while(stack1.empty()==false)
{
stack2.push(stack1.pop());
}
}
}
return stack2.pop();
}
}
//创建队列（调用构造方法）
CQueue obj = new CQueue();
//添加一个元素进队列队尾
obj.appendTail(value);
//删除队头元素并且返回这个队头元素
int param_2 = obj.deleteHead();
另外一道跟这个也很相似力扣（leetcode232）
class MyQueue
{
Stack stack1;
Stack stack2;
//调用构造方法创建两个栈
public MyQueue()
{
stack1=new Stack();
stack2=new Stack();
}public void push(int x)
{
stack1.push(x);
}public int pop()
{
//肯定是弹出stack2中的元素
//stack2为空的时候（即stack2中没有元素可以弹出的时候），把stack1中的元素全部转移到stack2中
if(stack2.empty()==true)
{
while(stack1.empty()==false)
{
stack2.push(stack1.pop());
}
}
returnstack2.pop();
}public int peek()
{
if(stack2.empty()==true)
{
while(stack1.empty()==false)
{
stack2.push(stack1.pop());
}
}
return stack2.peek();
}public boolean empty()
{
if(stack1.empty()==true&&stack2.empty()==true)
{
return true;
}
return false;
}
} 3.用两个队列实现栈
力扣225
定义两个队列，其中queue1队列用来加入元素，queue2队列用来peek和pop弹出元素
文章图片
class MyStack
{
Queue queue1;
Queue queue2;
public MyStack()
{
queue1=new LinkedList();
queue2=new LinkedList();
}public void push(int x)
{
//step1:先把元素添加到queue1里面
queue1.add(x);
//step2：只要队列queue2里面还有元素，就要把它转移到队列queue1里面
while(queue2.size()!=0)
{
queue1.add(queue2.remove());
}
//step3:此时元素就全部在队列queue1里面了，再交换queue1和queue2即可
Queue temp=queue1;
queue1=queue2;
queue2=temp;
}public int pop()
{
return queue2.remove();
}public int top()
{
return queue2.peek();
}public boolean empty()
{
return queue2.size()==0;
}
} 4.最小栈
力扣155
最小栈其实就是在栈的基础上多了一个获取最小元素的功能
这道题进行测试时
minStack minstack=new MinStack();
minstack(-2);
minstack(0);
ninstack(-3);
//先压三个元素进栈
//然后调用getMin()方法来获取栈内最小元素是多少
minstack.getMin();
暴力方法：
class MinStack
{
Stackstack;
public MinStack()
{
stack=new Stack();
}public void push(int val)
{
stack.push(val);
}public void pop()
{
stack.pop();
}public int top()
{
return stack.peek();
}public int getMin()
{
ArrayList a=new ArrayList();
for(int i:stack)
{
a.add(i);
}
int temp=Integer.MAX_VALUE;
for(int j:a)
{
temp=Math.min(temp,j);
}
return temp;
}
显然暴力法时间复杂度为O(n)，因为遍历栈的时间复杂度为O(n)
题目规定要用常数时间内找到最小元素肯定是满足不了的
双栈法：用两个栈，一个栈是正常的栈，元素进栈和出栈都是正常的
另一个栈是特殊的栈，一个元素要想进这个栈必须小于这个栈的栈顶元素，
当正常栈弹出栈顶元素时，特殊栈要不要也弹出栈顶元素呢？当正常栈要弹出的栈顶元素等于特殊栈的栈顶元素时，特殊栈的栈顶元素也要弹出，不相等时，特殊栈的栈顶元素就不用弹出
class MinStack
{
Stack stack1;
Stack stack2;
public MinStack()//初始化两个栈，一个正常栈，一个特殊栈
{
stack1=new Stack();
stack2=new Stack();
}
public void push(int x)
{
//stack1正常栈，入栈时正常入栈就行
stack1.push(x);
if(stack2.empty())stack2.push(x);
else
{
if(x<=stack2.peek())stack2.push(x);
}
}
public void pop()
{
int temp=stack1.peek();
stack1.pop();
if(!stack2.empty()&&stack2.peek()==temp)stack2.pop();
}
public int top()
{
return stack1.peek();
}
public int getMin()
{
return stack2.peek();
}
} 推荐阅读
- Linux|7.【刷爆LeetCode】把字符串转换成整数（多方法、多思路）
- golang|LeetCode26 删除有序数组中的重复项 Go语言
- 面试|力扣刷题记录
- 记录|leetcode刷题计划和每日刷题记录
- leetcode周赛记录|第一次打leetcode周赛复盘——第286场周赛
- leetcode刷题|LeetCode 第63场双周赛复盘
- Leetcode|leetcode:第260场周赛复盘
- Leetcode复盘|LeetCode 第 298 场周赛
- 《力扣周赛题解》|【周赛复盘】LeetCode第298场单周赛