东光网站制作,温州市建设工程管理网站,专业旅游培训网站建设,网站怎么做淘宝客目录 一.栈(Stack)
1.1栈的概念
1.2栈的实现及模拟
二.队列(Queue)
2.1队列的概念
2.2队列的实现及模拟 2.3循环队列
2.4双端队列#xff08;Deque#xff09; 一.栈(Stack)
1.1栈的概念 栈:一种特殊的线性表#xff0c;其 只允许在固定的一端进行插入和删除元素操作…目录 一.栈(Stack)
1.1栈的概念
1.2栈的实现及模拟
二.队列(Queue)
2.1队列的概念
2.2队列的实现及模拟 2.3循环队列
2.4双端队列Deque 一.栈(Stack)
1.1栈的概念 栈:一种特殊的线性表其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFO Last In First Out 的原则 压栈栈的插入操作叫做进栈 / 压栈 / 入栈 入数据在栈顶 。 出栈栈的删除操作叫做出栈。 出数据在栈顶 1.2栈的实现及模拟 public class Test {public static void main(String[] args) {StackIntegersnew Stack();//创建一个空栈s.push(1);//往栈中存入1s.push(2);//2s.push(3);//3s.push(4);//4s.push(5);//5System.out.println(s.size());//有效个数5System.out.println(s.peek());//获取栈顶元素5s.pop();//5出栈System.out.println(s.peek());//此时栈顶元素变为4System.out.println(s.empty());//判断是否为空栈,此时不为空 返回false}
}这里我们用自己的方法来模拟实现上述的方法
public class MyStack {int[] elem;int usedSize;public MyStack(){this.elemnew int[10];}public void push(int val){if(isFull()){//扩容elem Arrays.copyOf(elem,elem.length*2);}elem[usedSize]val;usedSize;}public boolean isFull(){return usedSizeelem.length;}public int pop(){if(empty()){return -1;}int oldValelem[usedSize-1];usedSize--;return oldVal;}public int peek(){if(empty()){return -1;}return elem[usedSize-1];}public boolean empty(){return usedSize0;}
}
二.队列(Queue)
2.1队列的概念 队列:只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头Head/Front 2.2队列的实现及模拟
在Java中Queue是个接口底层是通过链表实现的
注意Queue是个接口在实例化时必须实例化LinkedList的对象因为LinkedList实现了Queue接口。 public class Test{public static void main(String[] args) {QueueIntegerqnew LinkedList();q.offer(1);//从队尾入q.offer(2);q.offer(3);q.offer(4);System.out.println(q.size());//有效个数 4System.out.println(q.peek());//获取头元素 1q.poll();//1从队列中出System.out.println(q.peek());//2System.out.println(q.isEmpty());//此时队列不为空所以返回 false}
}
这里我们进行模拟实现上述方法
public class MyQueue {static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.valval;}}public ListNode head;public ListNode last;public void offer(int val){ListNode nodenew ListNode(val);if(headnull){headlastnode;}else{last.nextnode;node.prevlast;lastlast.next;}}public int poll(){if(headnull){return -1;}int rethead.val;if(head.nextnull){headlastnull;}else{headhead.next;head.prevnull;}return ret;}public int peek(){if(head null) {return -1;}return head.val;}public boolean isEmpty(){return headnull;}
}2.3循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。 2.4双端队列Deque
双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队也可以从队尾出队和入队 Deque是一个接口使用时必须创建LinkedList的对象 DequeInteger stack new ArrayDeque();//双端队列的线性实现 DequeInteger queue new LinkedList();//双端队列的链式实现 我将在下篇文章详细讲解这两种队列的使用以及相关OJ题 如果上述内容对您有帮助希望给个三连谢谢
