栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出 LIFO(Last In First Out)的原则。 333后进,最先出去。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈:栈的删除操作叫做出栈。出数据在栈顶。
顺序栈:(数组实现的栈)
import java.util.Arrays;
public class MyStack {
public int[] elem;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public MyStack(){
this.elem = new int[DEFAULT_SIZE];
}
public int push(int val){
if(isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
this.elem[usedSize] = val;
usedSize++;
return val;
}
public boolean isFull(){
if(usedSize == elem.length){
return true;
}
return false;
}
public int pop(){
if(isEmpty()){
throw new IsEmptyExpection("栈为空!");
}
int ret = elem[usedSize-1];
usedSize--;
return ret;
}
public boolean isEmpty(){
return usedSize == 0;
}
public int peek(){
if(isEmpty()){
throw new IsEmptyExpection("栈为空!");
}
return elem[usedSize-1];
}
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(11);
myStack.push(22);
myStack.push(33);
myStack.push(44);
System.out.println(myStack.peek());
System.out.println(myStack.pop());
System.out.println(myStack.peek());
}
}
栈的实现可以有多种方式,比如顺序栈,链式栈。双向链表实现的链式栈可以实现多种方向的先进后出。较为方便。
栈,虚拟机栈,栈帧有什么区别? 栈:是一种先进后出的数据结构。 虚拟机栈:是JVM的一块内存空间。 栈帧:是在调用函数的过程中,在Java虚拟机栈上开辟的一块内存。
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstIn First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头(Head/Front)
在Java中,Queue是个接口,底层是通过链表实现的。
注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。(接口不能被实例化!)
public class MyQueue {
static class ListNode{
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
public int usedSize;
public void offer(int val){
//尾插法
ListNode node = new ListNode(val);
if(head == null){
head = node;
tail = node;
}else {
tail.next = node;
tail = tail.next;
}
usedSize ++;
}
public int poll(){
//头删法
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
int ret = head.val;
head = head.next;
if(head == null){
tail = null;
}
usedSize--;
return ret;
}
public boolean isEmpty(){
return usedSize == 0;
}
public int peek(){
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
return head.val;
}
public int getUsedSize(){
return usedSize;
}
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
myQueue.offer(11);
myQueue.offer(22);
myQueue.offer(33);
myQueue.offer(44);
System.out.println(myQueue.peek());
System.out.println(myQueue.poll());
System.out.println(myQueue.peek());
System.out.println(myQueue.getUsedSize());
}
}
实际中我们有时还会使用一种队列叫循环队列。环形队列通常使用数组实现。
public class MyCirleQueue {
public int[] elem;
public int front;//队头
public int rear;//队尾
public MyCirleQueue(int k){
this.elem = new int[k];
}
public boolean enQueue(int val){
if(isFull()){
return false;
}
elem[rear] = val;
rear = (rear+1) % elem.length;
return true;
}
public boolean isFull(){
return (rear+1) % elem.length == front;
}
public boolean deQueue(){
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
front = (front+1) % elem.length;
return true;
}
public boolean isEmpty(){
return front == rear;
}
public int Front(){
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
return elem[front];
}
public int Rear(){
if(isEmpty()){
throw new IsEmptyExpection("队列为空!");
}
int index = rear == 0 ? elem.length-1 : rear-1;
return elem[index];
}
}
双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。 Deque是一个接口,使用时必须创建LinkedList的对象。