栈与队列
队列
队列的定义
其实队列这个数据结构就是计算机模拟现实生活中的体现,就跟一个人排队一样,先排上就先走,拿最新很火的梨泰院的例子来说:走在前面的人就应该尽快出去,不然就会产生问题,产生了碾压的大问题。
环形队列(取模的巅峰)
栈
栈的定义
栈与队列正好相反,栈是先入后出的有序列表,有入栈和出栈的概念。
栈的操作
Java中栈的操作说明
初始化
Stack<T> sk = new Stack<>();
常用方法
pop();//出栈
push(object);//入栈
size();//栈尺寸
search(Object);//寻找栈中元素的位置
empty();//判断是否栈空
peek();//返回栈顶元素
两个栈模拟队列
class CQueue {
//两个栈,一个出栈,一个入栈
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(!stack2.isEmpty()){
return stack2.pop();
}else{
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.isEmpty() ? -1 : stack2.pop();
}
}
}
栈的定义
剑指offer:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中
思考:其实就是困难在栈是如何遍历的。
//第一思路就是递归遍历,但是如果只是用于比较,递归遍历的复杂度就太高了,就没有美感
public void dfs(MyLinkedStack<String> myStack){
if(myStack.length() == 0){
return 0;
}
System.out.print(myStack.pop()+" ")
dfs(myStack);
}
://解法1:辅助栈
classMinStack{Stack<Integer> s1;
Stack<Integer> s2;
/** initialize your data structure here. */publicMinStack(){
s1 = newStack<>();
s2 = newStack<>();
}
publicvoidpush(intx){
s1.push(x);
if(s2.isEmpty()) s2.push(x);
elses2.push(Math.min(x, s2.peek()));
}
publicvoidpop(){
s1.pop();
s2.pop();
}
publicinttop(){
returns1.peek();
}
publicintmin(){
returns2.peek();
}
}
//解法2:链表(在节点里输入数据,真的很强)
class MinStack {
private Node head;
public MinStack() {
}
public void push(int x) {
if (head == null)
head = new Node(x, x, null);
else
head = new Node(x, Math.min(head.min, x), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int min() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
public Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
标签:head,min,队列,pop,Stack,int,算法,数据结构,public
From: https://www.cnblogs.com/robyn2022/p/16846052.html