Java栈和队列的实现

一.栈(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) {Stack<Integer>s=new 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.elem=new int[10];}public void push(int val){if(isFull()){//扩容elem= Arrays.copyOf(elem,elem.length*2);}elem[usedSize]=val;usedSize++;}public boolean isFull(){return usedSize==elem.length;}public int pop(){if(empty()){return -1;}int oldVal=elem[usedSize-1];usedSize--;return oldVal;}public int peek(){if(empty()){return -1;}return elem[usedSize-1];}public boolean empty(){return usedSize==0;}
}

二.队列(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) {Queue<Integer>q=new 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.val=val;}}public ListNode head;public ListNode last;public void offer(int val){ListNode node=new ListNode(val);if(head==null){head=last=node;}else{last.next=node;node.prev=last;last=last.next;}}public int poll(){if(head==null){return -1;}int ret=head.val;if(head.next==null){head=last=null;}else{head=head.next;head.prev=null;}return ret;}public int peek(){if(head == null) {return -1;}return head.val;}public boolean isEmpty(){return head==null;}
}