本道综合精品,亚洲精品中文在线观看,日韩中文字幕一区

1. 棧

1.1 概念

棧：是一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。
特點(diǎn)：棧中的數(shù)據(jù)元素遵循先進(jìn)后出的原則，但要注意進(jìn)的同時(shí)也可以出，元素不是要全部進(jìn)展后才能出棧
棧頂：進(jìn)行數(shù)據(jù)插入和刪除操作的一端
棧底：棧頂?shù)牧硪欢?/li>
壓棧：棧的插入操作就做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂
出棧：棧的刪除操作就叫做出棧，出數(shù)據(jù)在棧頂

1.2 助解圖題

助解圖：

手槍的彈夾其實(shí)就類似是一個(gè)棧

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

當(dāng)我們壓子彈的時(shí)候，就是壓棧

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

當(dāng)我們上膛后，打槍時(shí)，就是出棧

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

助解題：

題一：一個(gè)棧的入棧順序是 a、b、c、d、e，該棧不可能的出棧順序是（） A.edcba B.decba C.dceab D.abcde

結(jié)果為：C

題二：中綴表達(dá)式為 a + b * c + ( d * e + f ) * g，那么它的后綴表達(dá)式為什么？

結(jié)果為：a b c * + d e * f + g * +

方法步驟（快捷方法）：

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

該方法中將括號(hào)的運(yùn)算符移到括號(hào)前面得到的結(jié)果就是前綴表達(dá)式

本題背景：我們平常使用的表達(dá)式一般為中綴表達(dá)式，中綴表達(dá)式便于人們的理解與計(jì)算。而后綴表達(dá)式的運(yùn)算符更方便計(jì)算機(jī)的運(yùn)算（如二叉樹、堆棧的方法計(jì)算）

題三：通過棧返回后綴表達(dá)式 a b c * + d e * f + g * + 計(jì)算的結(jié)果

結(jié)果為：a + b * c + ( d * e + f ) * g

方法：當(dāng)參數(shù)是數(shù)字時(shí)就壓棧。當(dāng)參數(shù)為運(yùn)算符時(shí)，出棧第一個(gè)數(shù)作為運(yùn)算符后的參數(shù)，出棧第二個(gè)參數(shù)作為運(yùn)算符前的參數(shù)，將結(jié)果再壓入棧中。

1.3 棧的數(shù)組實(shí)現(xiàn)

在 Java 中棧的底層其實(shí)是一個(gè)數(shù)組，并且它擁有壓棧、出棧等等方法，借助這些我們來自己實(shí)現(xiàn)一個(gè)棧

public class MyStack{
  // 定義一個(gè)整型的數(shù)組，也可以直接使用泛型
  public int[] elem;
  // 定義數(shù)組已經(jīng)使用的長(zhǎng)度，初始時(shí)為0
  public int usedSize;
  // 創(chuàng)建 MyStack 的構(gòu)造方法
  public MyStack(){
      // 用 Mystack 創(chuàng)建對(duì)象時(shí)初始化數(shù)組的長(zhǎng)度為10
      this.elem=new int[10];
  }
  // 判斷棧是否已滿
  public boolean isFull(){
      return usedSize==this.elem.length;
  }
  // 壓棧
  public int push(int val){
      if(isFull()){
          // 擴(kuò)容
          this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
      }
      this.elem[this.usedSize++]=val;
      return val;
  }
  // 出棧
  public int pop(){
      if(empty()){
          throw new RuntimeException("棧為空");
      }
      this.usedSize--;
      return this.elem[this.usedSize];
  }
  // 查看棧頂元素，不刪除
  public int peek(){
      if(empty()){
      	throw new RuntimeException("棧為空");
      }
      return this.elem[this.usedSize-1];
  }
  // 判斷棧是否為空
  public boolean empty(){
      return usedSize==0;
  }
}

1.4 問題

我們上述的棧是用數(shù)組實(shí)現(xiàn)的，入棧和出棧的時(shí)間復(fù)雜度都為 O(1)

那么棧能否用單鏈表實(shí)現(xiàn)呢？

使用頭插法：入棧時(shí)間復(fù)雜度為 O(1)，出棧時(shí)間復(fù)雜度為 O(1)
使用尾插法：入棧時(shí)間復(fù)雜度為 O(N)，出棧時(shí)間復(fù)雜度為 O(N)

綜上分析，棧可以通過單鏈表的頭插頭刪法實(shí)現(xiàn)

1.5 棧的單鏈表實(shí)現(xiàn)

接下來將使用單鏈表實(shí)現(xiàn)棧，注意要使用頭插頭刪法

class Node{
  public int val;
  public Node next;
  public Node(int val){
      this.val=val;
  }
}
public class MyStack{
  Node head=null;
  // 壓棧
  public int push(int val){
      Node node=new Node(val);
      node.next = head;
      head = node;
      return head.val;
  }
  // 出棧
  public int pop(){
      if(empty()){
          throw new RuntimeException("棧為空");
      }
      int val=head.val;
      head=head.next;
      return val;
  }
  // 查看棧頂元素，不刪除
  public int peek(){
      if(empty()){
          throw new RuntimeException("棧為空");
      }
      return head.val;
  }
  // 判斷棧是否為空
  public boolean empty(){
      return head==null;
  }
}

2. 隊(duì)列

2.1 概念

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除操作的特殊線性表。
特點(diǎn)：隊(duì)列具有先進(jìn)先出的特點(diǎn)
對(duì)頭：進(jìn)行刪除操作的一端
隊(duì)尾：進(jìn)行插入操作的一段

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

2.2 問題

在我們實(shí)現(xiàn)隊(duì)列前，要思考隊(duì)列是靠數(shù)組實(shí)現(xiàn)呢還是拿鏈表實(shí)現(xiàn)呢？

在 Java 當(dāng)中，隊(duì)列是由 LinkedList 實(shí)現(xiàn)的，它的底層是一個(gè)雙向鏈表。

對(duì)于雙向鏈表：我們只要在尾節(jié)點(diǎn)進(jìn)行入隊(duì)操作，在頭節(jié)點(diǎn)進(jìn)行出隊(duì)操作就很容易實(shí)現(xiàn)
對(duì)于單鏈表：我們只要增加一個(gè)尾巴節(jié)點(diǎn)，然后尾巴節(jié)點(diǎn)進(jìn)行入隊(duì)操作，頭節(jié)點(diǎn)進(jìn)行出隊(duì)操作也能實(shí)現(xiàn)

至于數(shù)組，我們上述通過它實(shí)現(xiàn)了棧，而棧的特點(diǎn)其實(shí)是先進(jìn)后出，與隊(duì)列的先進(jìn)先出原則矛盾。使用數(shù)組來實(shí)現(xiàn)隊(duì)列會(huì)很麻煩。

2.3 隊(duì)列的單鏈表實(shí)現(xiàn)

根據(jù) Java 中隊(duì)列的一些方法，接下來我們來實(shí)現(xiàn)自己的隊(duì)列

class Node{
  public int val;
  public Node next;
  public Node(int val){
      this.val=val;
  }
}
public class MyQueueLinked {
  private Node front;
  private Node rear;
  private int usedSize;
  // 入隊(duì)列
  public void offer(int val){
      Node node=new Node(val);
      if(this.front==null){
          this.front=node;
          this.rear=node;
      }else{
          this.rear.next=node;
          this.rear=node;
      }
      this.usedSize++;
  }
  // 出隊(duì)列
  public int poll(){
     if(isEmpty()){
         throw new RuntimeException("隊(duì)列為空");
     }
     int val=this.front.val;
     if(this.front.next==null){
         this.front=null;
         this.rear=null;
     }else{
         this.front=this.front.next;
     }
      this.usedSize--;
      return val;
  }
  // 得到隊(duì)頭元素不刪除
  public int peek(){
      if(isEmpty()){
          throw new RuntimeException("隊(duì)列為空");
      }else{
          return this.front.val;
      }
  }
  // 判斷隊(duì)列是否為空
  public boolean isEmpty(){
      return this.usedSize==0;
  }
  // 得到隊(duì)列長(zhǎng)度
  public int size(){
      return this.usedSize;
  }
}

上述隊(duì)列是用單鏈表實(shí)現(xiàn)的，也叫鏈?zhǔn)疥?duì)列。大家也可以自行嘗試一下雙鏈表實(shí)現(xiàn)隊(duì)列。

2.4 數(shù)組實(shí)現(xiàn)隊(duì)列

假設(shè)現(xiàn)在我們用數(shù)組模擬入隊(duì)列和出隊(duì)列的模型

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

解決方法：

方法一：出隊(duì)時(shí)，移動(dòng)數(shù)組將后面的元素往前覆蓋（時(shí)間復(fù)雜度為 O(N)）
方法二：使用循環(huán)的方法，實(shí)現(xiàn)循環(huán)隊(duì)列（時(shí)間復(fù)雜度為 O(1)）

2.5 循環(huán)隊(duì)列

循環(huán)隊(duì)列即數(shù)組使用了循環(huán)的方式，讓數(shù)組方便隊(duì)列的入隊(duì)和出隊(duì)。那么怎么實(shí)現(xiàn)呢？模型如下

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

front：指向的位置就是隊(duì)列的頭，既已經(jīng)存放數(shù)據(jù)的第一個(gè)下標(biāo)（刪除數(shù)據(jù)一端）
rear：指向的位置就是隊(duì)列的尾巴，即可以存放數(shù)據(jù)的第一個(gè)下標(biāo)（插入數(shù)據(jù)一端）

問題1：如何判斷 front = rear 時(shí)是空還是滿？

為了能夠區(qū)別是空還是滿，我們常假定當(dāng) front = rear 時(shí)為空。而對(duì)于滿的話，我們則會(huì)將這個(gè)數(shù)組保留一個(gè)空的位置，那么當(dāng) rear+1 = front 時(shí)，則隊(duì)列滿了

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

問題2：當(dāng) front 在數(shù)組最后一個(gè)位置時(shí)，如何再移它到數(shù)組的第一個(gè)位置呢？

(下標(biāo)+1)%數(shù)組長(zhǎng)度

接下來讓我們實(shí)現(xiàn)循環(huán)隊(duì)列

public class MyCircularQueue {
  private int[] elem;
  private int front;
  private int rear;
  public MyCircularQueue(int k){
      this.elem=new int[k+1];
  }
  // 判斷隊(duì)列是否滿了
  public boolean isFull(){
      return (this.rear+1)%this.elem.length==this.front;
  }
  // 判斷隊(duì)列是否為空
  public boolean isEmpty(){
      return this.front==this.rear;
  }
  // 入隊(duì)
  public void enQueue(int val){
      if(isFull()){
          this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
      }
      this.elem[this.rear]=val;
      this.rear=(this.rear+1)%this.elem.length;
  }
  // 出隊(duì)
  public int deQueue(){
      if(isEmpty()){
          throw new RuntimeException("隊(duì)列為空");
      }
      int val=this.elem[this.front];
      this.front=(this.front+1)%this.elem.length;
      return val;
  }
  // 得到隊(duì)頭元素
  public int getFront(){
      if(isEmpty()){
          throw new RuntimeException("隊(duì)列為空");
      }
      return this.elem[this.front];
  }
  // 得到隊(duì)尾元素
  public int getRear(){
      if(isEmpty()){
          throw new RuntimeException("隊(duì)列為空");
      }
      if(this.rear==0){
          return this.elem[this.elem.length-1];
      }
      return this.elem[this.rear - 1];
  }
}

注意：

假設(shè)一個(gè)數(shù)組長(zhǎng)度為3，做題時(shí)可能人家用例入隊(duì)了3次，但是按照上述隊(duì)列為滿的方式，我們其實(shí)是保留了一個(gè)位置是不能存放數(shù)據(jù)的。因此對(duì)于這種題目我們可以將我們的數(shù)組開大一位

2.6 雙端隊(duì)列

雙端隊(duì)列：是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列
特點(diǎn)：元素可以從隊(duì)頭出隊(duì)和入隊(duì)，也可以從隊(duì)尾出隊(duì)和入隊(duì)

雙端隊(duì)列較簡(jiǎn)單，可以使用雙向鏈表實(shí)現(xiàn)，這里就展示一下雙端隊(duì)列的模型

Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)

3. 棧和隊(duì)列練習(xí)題

3.1 有效的括號(hào)

題目（OJ 鏈接）：

給定一個(gè)只包括 ‘('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：左括號(hào)必須用相同類型的右括號(hào)閉合，左括號(hào)必須以正確的順序閉合。

題解：使用棧，遍歷字符串，是左括號(hào)就進(jìn)行入棧，是右括號(hào)就與棧頂元素比較。

public boolean isValid(String s) {
  Stack<Character> stack=new Stack<>();
  for(int i=0;i<s.length();i++){
      char ch=s.charAt(i);
      switch(ch){
          case ')':
              if(stack.empty()||stack.pop()!='('){
                  return false;
              }
              break;
          case '}':
              if(stack.empty()||stack.pop()!='{'){
                  return false;
              }
              break;
          case ']':
              if(stack.empty()||stack.pop()!='['){
                  return false;
              }
              break;
          default:
              stack.push(ch);
              break;
      }
  }
  if(stack.empty()){
      return true;
  }
  return false;
}

3.2 用隊(duì)列實(shí)現(xiàn)棧

題目（OJ鏈接）：

請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

題解：

由于隊(duì)列是先進(jìn)先出，棧是先進(jìn)后出，故一個(gè)隊(duì)列無法滿足實(shí)現(xiàn)棧的能力。而使用兩個(gè)隊(duì)列，對(duì)于入棧，我們我只要找到棧不為空的隊(duì)列進(jìn)行入隊(duì)就行；對(duì)于出棧，我們只要將不為空的隊(duì)列的除最后一個(gè)入隊(duì)的元素全部轉(zhuǎn)移到另一個(gè)空隊(duì)列中，再將留下的元素出隊(duì)

代碼：

class MyStack {
  private Queue<Integer> q1;
  private Queue<Integer> q2;
  public MyStack() {
      q1=new LinkedList<>();
      q2=new LinkedList<>();
  }
  // 入棧
  public void push(int x) {
      if(!q1.isEmpty()){
          q1.offer(x);
      }else if(!q2.isEmpty()){
          q2.offer(x);
      }else{
          q1.offer(x);
      }
  }
  // 出棧
  public int pop() {
      if(empty()){
          throw new RuntimeException("棧為空");
      }
      if(!q1.isEmpty()){
          int val1=0;
          while(!q1.isEmpty()){
              val1=q1.poll();
              if(!q1.isEmpty()){
                  q2.offer(val1);
              }
          }
          return val1;
      }else{
          int val2=0;
          while(!q2.isEmpty()){
              val2=q2.poll();
              if(!q2.isEmpty()){
                  q1.offer(val2);
              }
          }
          return val2;
      }
  }
  // 得到棧頂元素不刪除
  public int top() {
      if(empty()){
          throw new RuntimeException("棧為空");
      }
      if(!q1.isEmpty()){
          int val1=0;
          while(!q1.isEmpty()){
              val1=q1.poll();
              q2.offer(val1);
          }
          return val1;
      }else{
          int val2=0;
          while(!q2.isEmpty()){
              val2=q2.poll();
              q1.offer(val2);
          }
          return val2;
      }
  }
  // 判斷棧是否為空
  public boolean empty() {
      return q1.isEmpty()&&q2.isEmpty();
  }
}

3.3 用棧實(shí)現(xiàn)隊(duì)列

題目（OJ 鏈接）：

請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。

題解：

我們可以創(chuàng)建兩個(gè)棧 s1、s2，s1 用來入隊(duì)，s2 用來出隊(duì)

代碼：

class MyQueue {
  private Stack<Integer> s1;
  private Stack<Integer> s2;
  public MyQueue() {
      s1=new Stack<>();
      s2=new Stack<>();
  }
  // 入隊(duì)
  public void push(int x) {
      s1.push(x);
  }
  // 出隊(duì)
  public int pop() {
      if(empty()){
          return -1;
      }
      if(s2.empty()){
          while(!s1.empty()){
              s2.push(s1.pop());
          }
      }
      return s2.pop();
  }
  // 返回隊(duì)首元素，不刪除
  public int peek() {
      if(empty()){
          return -1;
      }
      if(s2.empty()){
          while(!s1.empty()){
              s2.push(s1.pop());
          }
      }
      return s2.peek();
  }
  // 判斷隊(duì)列是否為空
  public boolean empty() {
      return s1.empty()&&s2.empty();
  }
}

3.4 實(shí)現(xiàn)一個(gè)最小棧

題目（OJ 鏈接）：

設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。

題解：

我們可以創(chuàng)建兩個(gè)棧，一個(gè)棧就是用來存儲(chǔ)刪除元素，另一個(gè)就是專門用來存儲(chǔ)最小值的棧。注意這個(gè)最小值是存儲(chǔ)該元素時(shí)該棧的最小值

代碼：

class MinStack {
  private Stack<Integer> stack;
  private Stack<Integer> minStack;
  public MinStack() {
      stack=new Stack<>();
      minStack=new Stack<>();
  }
  // 入棧
  public void push(int val) {
      stack.push(val);
      if(minStack.empty()){
          minStack.push(val);
      }else{
          if(val<=minStack.peek()){
              minStack.push(val);
          }
      }
  }
  // 出棧
  public void pop() {
      int val=stack.pop();
      if(minStack.peek()==val){
          minStack.pop();
      }
  }
  // 得到棧頂元素，不刪除
  public int top() {
      return stack.peek();
  }
  // 得到此時(shí)棧的最小值
  public int getMin() {
      return minStack.peek();
  }
}

3.5 設(shè)計(jì)循環(huán)隊(duì)列

題目（OJ 鏈接）：

設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱為“環(huán)形緩沖器”。

題解：

通過 (下標(biāo)+1)%數(shù)組長(zhǎng)度的方式將數(shù)組形成一個(gè)循環(huán)，先設(shè)定好數(shù)組為空和為滿的條件。注意防止題目將數(shù)組存滿，開數(shù)組時(shí)的大小要注意。

代碼：

class MyCircularQueue {
  private int[] elem;
  private int front;
  private int rear;
  public MyCircularQueue(int k) {
      this.elem=new int[k+1];
  }
  // 入隊(duì)列
  public boolean enQueue(int value) {
      if(isFull()){
          return false;
      }
      this.elem[rear]=value;
      this.rear=(this.rear+1)%this.elem.length;
      return true;
  }
  // 出隊(duì)列
  public boolean deQueue() {
      if(isEmpty()){
          return false;
      }
      this.front=(this.front+1)%this.elem.length;
      return true;
  }
  // 得到隊(duì)首元素，不刪除
  public int Front() {
      if(isEmpty()){
          return -1;
      }
      return this.elem[front];
  }
  // 得到隊(duì)尾元素，不刪除
  public int Rear() {
      if(isEmpty()){
          return -1;
      }
      if(this.rear==0){
          return this.elem[this.elem.length-1];
      }
      return this.elem[this.rear-1];
  }
  // 判斷隊(duì)列是否為空
  public boolean isEmpty() {
      return this.rear==this.front;
  }
  // 判斷隊(duì)列是否滿了
  public boolean isFull() {
      return (this.rear+1)%this.elem.length==this.front;
  }
}

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java 棧和隊(duì)列的實(shí)現(xiàn)內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！

原文鏈接：https://blog.csdn.net/weixin_51367845/article/details/120931373