专注IT技术、资源分享!
【算法系列】堆栈结构的不同实现方式
【算法系列】堆栈结构的不同实现方式

【算法系列】堆栈结构的不同实现方式

我是小黑,一个在互联网“苟且”的程序员。

流水不争先,贵在滔滔不绝

栈(stack)又名堆栈,是一个线性表数据结构,后进先出(FILO)是它最大的特点。

使用数组实现堆栈结构

题目描述:

需要使用数组来实现堆栈。需要编写push和pop方法来演示Stack行为(后进先出)。

尽管在java中提供了所有抽象数据类型的实现,如堆栈、队列和链表等,但理解基本数据结构并自己实现它们能让我们有更深刻的理解。

堆栈的数组实现本质上不是动态的。你也可以通过链表实现动态行为的Stack。

思路:

在实现之前我们先看一下栈支持的基本操作:

  • push:将元素压入堆栈的顶部,堆栈大小加1;
  • pop:将栈顶元素删除并返回被删除元素,堆栈大小减1;
  • isEmpty:判断堆栈是否为空;
  • isFull:判断堆栈是否已满;
  • peek:返回栈顶元素,但是不删除它。

这些操作的时间复杂度都是O(1)。

代码实现:

package com.heiz.algorithm.stack;

/**
* @author 小黑说Java
* @ClassName StackCustom
* @Description
* @date 2021/11/21
**/
public class StackCustom {
   int size;
   int[] arr;
   int top;

   StackCustom(int size) {
       this.size = size;
       this.arr = new int[size];
       this.top = -1;
  }

   public void push(int pushedElement) {
       if (!isFull()) {
           top++;
           arr[top] = pushedElement;
           System.out.println("Pushed element:" + pushedElement);
      } else {
           System.out.println("Stack is full !");
      }
  }

   public int pop() {
       if (!isEmpty()) {
           int returnedTop = top;
           top--;
           System.out.println("Popped element :" + arr[returnedTop]);
           return arr[returnedTop];
      } else {
           System.out.println("Stack is empty !");
           return -1;
      }
  }

   public int peek() {
       if (!this.isEmpty())
           return arr[top];
       else {
           System.out.println("Stack is Empty");
           return -1;
      }
  }

   public boolean isEmpty() {
       return (top == -1);
  }

   public boolean isFull() {
       return (size - 1 == top);
  }

   public static void main(String[] args) {
       StackCustom StackCustom = new StackCustom(10);
       StackCustom.pop();
       System.out.println("=================");
       StackCustom.push(10);
       StackCustom.push(30);
       StackCustom.push(50);
       StackCustom.push(40);
       System.out.println("=================");
       StackCustom.pop();
       StackCustom.pop();
       StackCustom.pop();
       System.out.println("=================");
  }
}

运行结果:

如你所见,我们最后push的元素40,先被pop出来,符合栈后进先出(LIFO)的特点。

使用LinkedList实现堆栈结构

使用链表完成堆栈结构,我们主要完成两个重要的操作:

  • Push : 将元素推入链表的开头,演示堆栈的推行为;
  • Pop :我们将移除链表的第一个元素来演示Stack的Pop行为。

代码实现:

package com.heiz.algorithm.stack;

/**
* @author yuriy.lu
* @ClassName LinkedListStack
* @Description
* @date 2021/11/21
**/
public class LinkedListStack {
   private Node head; // 头结点

   //链表节点
   private static class Node {
       int value;
       Node next;
  }

   public LinkedListStack() {
       head = null;
  }

   public int pop() throws LinkedListEmptyException {
       if (head == null) {
           throw new LinkedListEmptyException();
      }
       int value = head.value;
       head = head.next;
       return value;
  }

   public void push(int value) {
       Node oldHead = head;
       head = new Node();
       head.value = value;
       head.next = oldHead;
  }

   public static void main(String[] args) {
       LinkedListStack lls = new LinkedListStack();
       lls.push(20);
       lls.push(50);
       lls.push(80);
       lls.push(40);
       lls.push(60);
       lls.push(75);
       System.out.println("Element removed from LinkedList: " + lls.pop());
       System.out.println("Element removed from LinkedList: " + lls.pop());
       lls.push(10);
       System.out.println("Element removed from LinkedList: " + lls.pop());
       printList(lls.head);
  }

   public static void printList(Node head) {
       Node temp = head;
       while (temp != null) {
           System.out.format("%d ", temp.value);
           temp = temp.next;
      }
       System.out.println();
  }
}

/**
* Exception to indicate that LinkedList is empty.
*/
class LinkedListEmptyException extends RuntimeException {
   private static final long serialVersionUID = 1L;

   public LinkedListEmptyException() {
       super();
  }
   public LinkedListEmptyException(String message) {
       super(message);
  }
}

运行结果:

使用两个队列实现堆栈

使用两个队列来实现堆栈行为,编写push和pop方法来演示栈的后进先出行为(LIFO)。

思路:

栈有两个最重要的操作push和pop,假设有两个队列:queue1, queue2来实现push和pop;

push:

  • 如果queue1为空,则向queue1添加元素;
  • 如果queue1不为空,将queue1中的所有元素添加到queue2中,将当前元素添加到queue1中,并将queue2中的所有元素复制到queue1中。

pop: 简单地从queue1中删除元素。

代码实现:

package com.heiz.algorithm.stack;

import java.util.LinkedList;
import java.util.Queue;

/**
* @author 小黑说Java
* @ClassName StackUsingTwoQueues
* @Description
* @date 2021/11/21
**/
public class StackUsingTwoQueues {

   Queue<Integer> queue1;
   Queue<Integer> queue2;

   StackUsingTwoQueues() {
       queue1 = new LinkedList<>();
       queue2 = new LinkedList<>();
  }

   public void push(int i) {
       if (queue1.size() == 0)
           queue1.add(i);
       else {
           int sizeOfQueue1 = queue1.size();
           for (int j = 0; j < sizeOfQueue1; j++)
               queue2.add(queue1.remove());
           queue1.add(i);
           for (int k = 0; k < sizeOfQueue1; k++)
               queue1.add(queue2.remove());
      }
  }

   public int pop() {
       if (queue1.size() == 0)
           throw new QueueEmptyException("Underflow Exception");
       return queue1.remove();
  }

   public static void main(String[] args) {
       StackUsingTwoQueues stack = new StackUsingTwoQueues();
       stack.push(20);
       stack.push(40);
       stack.push(70);
       stack.push(50);
       stack.push(90);
       stack.push(110);
       stack.push(30);
       System.out.println("Removed element : " + stack.pop());
       stack.push(170);
       System.out.println("Removed element : " + stack.pop());
  }
}

/**
* Exception to indicate that Queue is empty.
*/

class QueueEmptyException extends RuntimeException {
   private static final long serialVersionUID = 1L;

   public QueueEmptyException() {
       super();
  }

   public QueueEmptyException(String message) {
       super(message);
  }
}

运行结果:

image-20211121174031087

使用另一个堆栈对一个堆栈进行排序

使用另一个堆栈对一个堆栈进行排序。可以使用栈的push和pop操作来实现这一点。

思路:

  • 假设有两个栈,stack和tempStack;
  • 从堆栈中取出一个currentData元素,并将其与tempStack的head进行比较;
  • 如果currentData更大,则将其推到tempStack;
  • 如果currentData小于tempStack的head,从tempStack中取出一个元素并将其推入堆栈,直到得到大于currentData的元素;
  • 最后,tempStack将被排序为堆栈。

代码实现:

package com.heiz.algorithm.stack;

/**
* @author 小黑说Java
* @ClassName StackCustom
* @Description
* @date 2021/11/21
**/
public class StackCustom {
   int size;
   int arr[];
   int top;

   StackCustom(int size) {
       this.size = size;
       this.arr = new int[size];
       this.top = -1;
  }

   public void push(int pushedElement) {
       if (!isFull()) {
           top++;
           arr[top] = pushedElement;
      } else {
           System.out.println("Stack is full !");
      }
  }

   public int pop() {
       if (!isEmpty()) {
           int returnedTop = top;
           top--;
           return arr[returnedTop];

      } else {
           System.out.println("Stack is empty !");
           return -1;
      }
  }

   public int peek() {
       return arr[top];
  }

   public boolean isEmpty() {
       return (top == -1);
  }

   public boolean isFull() {
       return (size - 1 == top);
  }

   public static void main(String[] args) {
       StackCustom stackCustom = new StackCustom(10);
       System.out.println("=================");
       stackCustom.push(10);
       stackCustom.push(30);
       stackCustom.push(50);
       stackCustom.push(40);
       stackCustom.printStack(stackCustom);
       StackCustom sortedStack = sortStack(stackCustom);
       System.out.println("=================");
       System.out.println("After Sorting :");
       System.out.println("=================");
       sortedStack.printStack(sortedStack);
  }

   /**
    * 排序算法
    */
   public static StackCustom sortStack(StackCustom stack) {
       StackCustom tempStack = new StackCustom(10);
       while (!stack.isEmpty()) {
           int currentData = stack.pop();
           while (!tempStack.isEmpty() && tempStack.peek() > currentData) {
               stack.push(tempStack.pop());
          }
           tempStack.push(currentData);
      }
       return tempStack;
  }

   public void printStack(StackCustom stack) {
       if (top >= 0) {
           System.out.println("Elements of stacks are:");
           for (int i = 0; i <= top; i++) {
               System.out.println(arr[i]);
          }
      }
  }
}

运行结果:


以上是堆栈结构详细解析的全部内容,如果对你有所帮助,点个赞是对我最大的鼓励!

发表回复

您的电子邮箱地址不会被公开。