【Java数据结构】线性表之栈和队列_业界新闻

发布时间:2024-08-08 07:50

阅读量:0

栈（Stack）

简单描述

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

使用栈的一些常见的方法

压栈、出栈、获取栈顶元素、获取栈中元素个数、检查栈是否为空

public class Main {     public static void main(String[] args) {         Stack<Integer> stack = new Stack<>();         stack.push(1);//压栈         stack.push(2);         stack.push(3);         stack.peek();//获取栈顶元素         stack.pop();//删除栈顶元素         stack.size();//获取栈中元素的个数         stack.empty();//判断栈是否为空     } }

使用数组模拟实现栈

public class MyStack {     private int[] elem;     private int usedSize;     private static final int DEFAULT_CAPACITY = 10;      public MyStack() {         this.elem = new int[DEFAULT_CAPACITY];     }      public MyStack(int capacity){         this.elem = new int[capacity];     }      private boolean checkCapacity(){         if(this.usedSize == elem.length){             return true;         }         return false;     }      public void push(int val){         if(this.checkCapacity()){             this.elem = Arrays.copyOf(this.elem,2*this.elem.length);         }         this.elem[this.usedSize] = val;         this.usedSize++;     }      public int pop() throws EmptyException {         if(this.usedSize == 0){             //throw new EmptyException("栈为空！");             return -1;         }         int tmp = this.elem[this.usedSize-1];         this.usedSize--;         return tmp;     }      public int peek() throws EmptyException {         if(this.usedSize == 0){             //throw new EmptyException("栈为空！");             return -1;         }         int tmp = this.elem[this.usedSize-1];         return tmp;     }          public int size(){         return this.usedSize;     }          public boolean empty(){         return this.usedSize == 0;     } }

我们使用 usedSize 来记录栈中元素的个数，压栈的时候就在 elem[usedSize] 输入元素，出栈的时候 usedSize 减一就可以了。

为什么用数组来实现栈？因为用数组来实现栈的时间复杂度为 O(1) 比较高效。

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

逆序输出链表

我们知道栈的一个特点是先进后出，那么先放进去的元素最后出栈。因此我们就可以达到一个目的：逆序

我们知道一个逆序的方法：递归

void printList(Node head){
   if(null != head){
       printList(head.next);
       System.out.print(head.val + " ");
  }
}

接下来我们利用栈来实现逆序：

void printList(Node head){
   if(null == head){
       return;
  }
   Stack<Node> s = new Stack<>();
   // 将链表中的结点保存在栈中
   Node cur = head;
   while(null != cur){
       s.push(cur);
       cur = cur.next;
  }
   // 将栈中的元素出栈
   while(!s.empty()){
       System.out.print(s.pop().val + " ");
  }
}

队列（Queue）

简单描述

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear）出队列：进行删除操作的一端称为队头（Head/Front）。

在Java中，Queue是个接口，底层是通过链表实现的。

队列（Queue）的一些常见方法

入队、出队、获取队头元素、获取队中元素个数、判断队列是否为空

public class Main {     public static void main(String[] args) {         Queue<Integer> queue = new LinkedList<>();         queue.offer(1);//入队         queue.offer(2);         queue.offer(3);         queue.poll();//删除队头元素         queue.peek();//获取队头元素         queue.size();//获取队中元素个数         queue.isEmpty();//判断队列是否为空     } }

使用链式结构来模拟实现队列

我们模拟实现队列既可以用线性结构也可以用链式结构，接下来我们使用链式结构来模拟实现一个简单队列。

public class MyQueue {     private int usedsize;     static class ListNode{         private int val;         private ListNode prev;         private ListNode next;          public ListNode(int val){             this.val = val;         }     }      private ListNode front;//队头     private ListNode rear;//队尾      public void offer(int data){         ListNode node = new ListNode(data);         if(front == null){             front = rear = node;         }else{             node.next = front;             front.prev = node;             front = node;             this.usedsize++;         }     }      public int poll(){         if(front == null){             System.out.println("队列没有元素！");             return -1;         }         if(front == rear){             int b = this.rear.val;             front = null;             rear = null;             this.usedsize--;             return b;         }         int a = this.rear.val;         this.rear.prev.next = null;         this.usedsize--;         return a;     }      public int peek(){         if(front == null){             System.out.println("队列没有元素！");             return -1;         }         if(front == rear){             int b = this.rear.val;             return b;         }         int a = this.rear.val;         return a;     }      public int size(){         return this.usedsize;     }      public boolean isEmpty(){         return this.usedsize == 0;     } }

这里我们 offer 入队操作采用的是链表中的头插法，我们使用双向链表的操作使得我们可以保存尾节点的位置，利于我们可以直接进行删除操作。