如何使用数组实现栈和队列？

Python中的list有如下的两个方法：

  • appned(x)：在列表的末尾添加元素
  • pop(index = -1)：从列表中弹出指定索引的元素，默认为弹出列表的末尾元素

因此，我们使用list可以很方法的实现栈和队列，废话不多说，直接上代码：

数组实现栈：

  • python实现

    1. class Stack:
    2.   def __init__(self, array = None):
    3.       super().__init__()
    4.       self.array = array
    6.   # 入栈
    7.   def push(self, x):
    8.       self.array.append(x)
    10.   # 出栈
    11.   def pop(self,):
    12.       if len(self.array) == 0:
    13.           return
    15.       return self.array.pop()
    17.   # 取栈顶元素
    18.   def top(self,):
    19.       if len(self.array) == 0:
    20.           return
    22.       return self.array[-1]
    24.   # 判空
    25.   def isEmpty(self,):
    26.       return True if self.array == [] else False

  • Java实现
    Java中的数组并没有python中list类似的方法，因此需要设置一个变量size来表示当前数组中的元素个数，以及方便进行栈顶元素的获取。 ```java public class ArrayToStack {

    public static class Array2Stack{

    1. private T[] array;
    2. private int size;
    4. public Array2Stack() {
    5. }
    7. public Array2Stack(T[] array) {
    8.     this.array = array;
    9.     this.size = 0;
    10. }
  1.   // 入栈
  2.   public void push(T x){
  3.       if (this.size == this.array.length){
  4.           throw new ArrayIndexOutOfBoundsException("the stack is full!");
  5.       }
  7.       this.array[size++] = x;
  8.   }
  9.   // 出栈
  10.   public T pop(){
  11.       if (isEmpty()){
  12.           throw new ArrayIndexOutOfBoundsException("the stack is empty");
  13.       }
  15.       return this.array[--size];
  16.   }
  17.   // 取栈顶元素
  18.   public T top(){
  19.       if (isEmpty()){
  20.           return null;
  21.       }
  22.       return this.array[size];
  23.   }
  25.   // 判空
  26.   public boolean isEmpty(){
  27.       boolean flag = this.size == 0 ? true : false;
  28.       return flag;
  29.   }

}

public static void main(String[] args) { int size = 10; Integer [] array = new Integer[size]; Array2Stack stack = new Array2Stack<>(array);

  1.   // 入栈
  2.   stack.push(1);
  3.   stack.push(2);
  4.   stack.push(3);
  6.   // 出栈
  7.   while(!stack.isEmpty()){
  8.       System.out.println(stack.pop()); // 3, 2, 1
  9.   }
  11.   String[] arr = new String[size];
  12.   Array2Stack<String> stack1 = new Array2Stack<>(arr);
  13.   stack1.push("Forlogen");
  14.   stack1.push("kobe");
  16.   while(!stack1.isEmpty()){
  17.       System.out.println(stack1.pop()); // kobe, Forlogen
  18.   }

} }

  4. <a name="76b1e409"></a>
  5. #### 数组实现队列
  7. - 
  8. python实现：
  9. ```python
  10. class Queue:
  11.     def __init__(self, array = None):
  12.         super().__init__()
  13.         self.array = array
  15.     # 入队
  16.     def enqueue(self, x):
  17.         self.array.append(x)
  19.     # 出队
  20.     def dequeue(self):
  21.         if len(self.array) == 0:
  22.             return
  24.         return self.array.pop(0)
  26.     # 判空
  27.     def isEmpty(self,):
  28.         return True if self.array == [] else False
  • Java实现
    使用数组实现队列除了需要变量size来表示当前数组中的元素个数外，还需要first和last来表示队头元素和队尾元素的位置，将数组循环使用。 ```java package DataStructure;

import java.util.Arrays;

public class ArrayToQueue{ private T[] array; private int size = 0; private int first = 0; private int last = 0;

  1. public ArrayToQueue() {
  2. }
  4. public ArrayToQueue(T[] array) {
  5.     if (size < 0){
  6.         throw new IllegalArgumentException("the size is less than 0!");
  7.     }
  8.     this.array = array;
  9. }
  11. // 入队
  12. public void enqueue(T x){
  13.     if (this.size == this.array.length){
  14.         throw new ArrayIndexOutOfBoundsException("the queue is full!");
  15.     }
  16.     size++;
  17.     this.array[this.last] = x;
  18.     last = last == this.array.length - 1 ? 0 : last + 1;
  19. }
  21. // 出队
  22. public T dequeue(){
  23.     if (isEmpty()){
  24.         throw new ArrayIndexOutOfBoundsException("the queue is empty!");
  25.     }
  26.     size--;
  27.     int tmp = first;
  28.     first = first == this.array.length - 1 ? 0: first + 1;
  29.     return this.array[tmp];
  30. }
  32. public boolean isEmpty(){
  33.     boolean flag = this.size == 0 ? true : false;
  34.     return flag;
  35. }
  38. public static void main(String[] args) {
  39.     int size = 10;
  40.     Integer[] array = new Integer[size];
  41.     ArrayToQueue<Integer> queue = new ArrayToQueue<>(array);
  43.     // 入队
  44.     queue.enqueue(1);
  45.     queue.enqueue(2);
  46.     queue.enqueue(3);
  48.     System.out.println(Arrays.toString(array));
  49.     while(!queue.isEmpty()){
  50.         System.out.println(queue.dequeue()); // 1, 2,3
  51.     }
  53. }

}

  4. ---
  6. <a name="5fac658e"></a>
  7. ### 如何构建获取最小元素的栈
  9. - 
  10. **思路1**：`array`和`mins`分别存储入栈的元素和当前已入栈元素中最小的元素
  12.    - 入栈：如果此时栈为空，则将元素同时压入两个数组中；如果此时栈不为空且入栈的元素小于`mins`的末尾元素，则同时压入两个数组；如果此时栈不为空但入栈的元素大于`mins`的末尾元素，则只将入栈元素压入`array`
  13.    - 出栈：同样需要判断当前`array`的栈顶元素和`mins`末尾元素的关系，从而来判断是否需要同时出栈，还是只对`array`执行出栈操作
  14. ```python
  15. class MinStack:
  16.     def __init__(self, array = None):
  17.         super().__init__()
  18.         self.array = array
  19.         self.mins = []
  21.     # 入栈
  22.     def push(self, x):
  23.         if len(self.mins) == 0:
  24.             self.array.append(x)
  25.             self.mins.append(x)
  26.         else:
  27.             if x < self.mins[-1]:
  28.                 self.array.append(x)
  29.                 self.mins.append(x)
  30.             else:
  31.                 self.array.append(x)
  33.     # 出栈
  34.     def pop(self,):
  35.         if len(self.array) == 0:
  36.             return
  37.         elif self.top() == self.mins[-1]:
  38.             self.mins.pop()
  39.             return self.array.pop()
  40.         else:
  41.             return self.array.pop()
  43.     # 获取栈中的最小元素
  44.     def getMin(self, ):
  45.         if len(self.array) == 0:
  46.             return
  47.         return self.mins[-1]
  49.     # 取栈顶元素
  50.     def top(self,):
  51.         if len(self.array) == 0:
  52.             return
  54.         return self.array[-1]

  • 思路2： 同样使用array和mins来存储入栈的元素和当前栈中最小的元素，不同之处在于入栈和出栈更为简单，假设当前栈不为空：

    • 入栈：如果入栈元素x大于等于mins的栈顶元素，则将x压入array中，而mins重新压入它当前的栈顶元素

    • 出栈：array和mins同时出栈 ```python class MinStack: def init(self, array = None): super().init() self.array = array self.mins = []

      入栈

      def push(self, x): if len(self.mins) == 0:

      1.    self.array.append(x)
      2.    self.mins.append(x)

      else:

      1.    if x < self.mins[-1]:
      2.        self.array.append(x)
      3.        self.mins.append(x)
      4.    else:
      5.        self.mins.append(self.mins[-1])
      6.        self.array.append(x)

      出栈

      def pop(self,): if len(self.array) == 0:

      1.    return

      self.mins.pop() return self.array.pop()

  1. # 获取栈中的最小元素
  2. def getMin(self, ):
  3.     if len(self.array) == 0:
  4.         return
  5.     return self.mins[-1]
  7. # 取栈顶元素
  8. def top(self,):
  9.     if len(self.array) == 0:
  10.         return
  12.     return self.array[-1]
  2. ---
  4. <a name="f2a0b1f3"></a>
  5. ### 如何使用队列实现栈？
  7. - 
  8. python实现：
  9. <br />Python的`collections`模块中的`deque`为一个双端队列，使用其中的`append()`入栈和使用`pop()`出栈，实现代码：
  10. ```python
  11. from collections import deque
  13. class Stack:
  14.     def __init__(self, array = None):
  15.         super().__init__()
  16.         self.queue = deque(array) 
  18.     # 入栈  
  19.     def push(self, x):
  20.         self.queue.append(x)
  22.     # 出栈
  23.     def pop(self,):
  24.         if (list(self.queue)) == 0:
  25.             return
  26.         return self.queue.pop()
  28.     # 取栈顶元素
  29.     def top(self,):
  30.         if (list(self.queue)) == 0:
  31.             return
  33.         return list(self.queue)[-1]
  35.     # 判空
  36.     def isEmpty(self, ):
  37.         return True if (list(self.queue)) == 0 else False
  • Java 实现： ```java import java.util.LinkedList; import java.util.Queue;

public class QueueToStack{ private Queue queue1; private Queue queue2;

  1. public QueueToStack(Queue<T> queue1, Queue<T> queue2) {
  2.     this.queue1 = queue1;
  3.     this.queue2 = queue2;
  4. }
  6. // 入栈
  7. public void push(T x){
  8.     this.queue1.add(x);
  9. }
  10. // 出栈
  11. public T pop(){
  12.     if (queue1.isEmpty()){
  13.         throw new RuntimeException("stack is empty");
  14.     }
  15.     while (this.queue1.size() > 1){
  16.         this.queue2.add(this.queue1.poll());
  17.     }
  18.     T res = this.queue1.poll();
  19.     swap();
  20.     return res;
  21. }
  23. // 交换引用
  24. private void swap() {
  25.     Queue<T> tmp = this.queue2;
  26.     queue2 = queue1;
  27.     queue1 = tmp;
  28. }
  29. // 返回栈顶元素
  30. public T top(){
  31.     if (queue1.isEmpty()){
  32.         throw new RuntimeException("stack is empty");
  33.     }
  34.     while (this.queue1.size() > 1){
  35.         this.queue2.add(this.queue1.poll());
  36.     }
  37.     T res = this.queue1.poll();
  38.     this.queue2.add(res);
  39.     swap();
  40.     return res;
  41. }
  43. // 判空
  44. public boolean isEmpty(){
  45.     if (this.queue1.isEmpty() && this.queue2.isEmpty()){
  46.         return true;
  47.     } else{
  48.         return false;
  49.     }
  50. }
  53. @Override
  54. public String toString() {
  55.     return "QueueToStack{" +
  56.             "queue1=" + queue1 +
  57.             ", queue2=" + queue2 +
  58.             '}';
  59. }
  61. public static void main(String[] args) {
  62.     Queue<Integer> queue1 = new LinkedList<>();
  63.     Queue<Integer> queue2 = new LinkedList<>();
  65.     QueueToStack<Integer> stack = new QueueToStack<>(queue1, queue2);
  67.     stack.push(1);
  68.     stack.push(2);
  69.     stack.push(3);
  70.     stack.push(4);
  71.     stack.push(5);
  72.     System.out.println(stack);  // QueueToStack{queue1=[1, 2, 3, 4, 5], queue2=[]}
  74.     System.out.println(stack.top()); // 5
  76.     stack.pop();
  77.     System.out.println(stack); // QueueToStack{queue1=[1, 2, 3, 4], queue2=[]}
  78. }

}

  4. ---
  6. <a name="33315cdf"></a>
  7. ### 如何使用栈构建队列？
  9. - 
  10. python实现：<br />
  11. 队列是一种先进先出的数据结构，而栈是一种后见先出的数据结构。因此需用一个栈`stack1`做入队，另一个`stack2`做出队。如果`stack2`不为空则直接弹出，否则需将`stack1`中的全部元素先压入`stack2`再从`stack2`中出栈。
  12. ```python
  13. class Queue:
  14.     def __init__(self):
  15.         super().__init__()
  16.         self.stack1 = []
  17.         self.stack2 = []
  19.     # 入栈
  20.     def push(self, x):
  21.         self.stack1.append(x)
  23.     # 出栈
  24.     def pop(self,):
  25.         if self.stack2:
  26.             return self.stack2.pop()
  28.         while self.stack1:
  29.             self.stack2.append(self.stack1.pop())
  31.         return self.stack2.pop()
  33.     def isEmpty(self,):
  34.         if len(self.stack1) == 0 and len(self.stack2) == 0:
  35.             return True
  36.         else:
  37.             return False
  • Java实现： ```java import java.util.Stack;

public class StackToQueue{ private Stack stack1; private Stack stack2;

  1. public StackToQueue() {
  2. }
  4. public StackToQueue(Stack<T> stack1, Stack<T> stack2) {
  5.     this.stack1 = stack1;
  6.     this.stack2 = stack2;
  7. }
  9. // 入队
  10. public void enqueue(T x){
  11.     this.stack1.push(x);
  12. }
  14. // 出队
  15. public T dequeue(){
  16.     if (!this.stack2.isEmpty()){
  17.         return this.stack2.pop();
  18.     } else{
  19.         while (!this.stack1.isEmpty()){
  20.             this.stack2.add(this.stack1.pop());
  21.         }
  22.         return this.stack2.pop();
  23.     }
  24. }
  26. // 返回队首
  27. public T top(){
  28.     if (!this.stack2.isEmpty()){
  29.         return this.stack2.pop();
  30.     } else{
  31.         while (!this.stack1.isEmpty()){
  32.             this.stack2.add(this.stack1.pop());
  33.         }
  34.         return this.stack2.peek();
  35.     }
  36. }
  38. // 判空
  39. public boolean isEmpty(){
  40.     if (this.stack1.isEmpty() && this.stack2.isEmpty()){
  41.         return true;
  42.     }else{
  43.         return false;
  44.     }
  45. }
  47. @Override
  48. public String toString() {
  49.     return "StackToQueue{" +
  50.             "stack1=" + stack1 +
  51.             ", stack2=" + stack2 +
  52.             '}';
  53. }
  56. public static void main(String[] args) {
  57.     Stack<Integer> stack1 = new Stack<>();
  58.     Stack<Integer> stack2= new Stack<>();
  60.     StackToQueue<Integer> queue = new StackToQueue<>(stack1, stack2);
  62.     queue.enqueue(1);
  63.     queue.enqueue(2);
  64.     queue.enqueue(3);
  65.     queue.enqueue(4);
  66.     queue.enqueue(5);
  67.     System.out.println(queue); //StackToQueue{stack1=[1, 2, 3, 4, 5], stack2=[]}
  69.     System.out.println(queue.top()); // 1
  71.     System.out.println(queue.dequeue()); // 1
  72.     System.out.println(queue); // StackToQueue{stack1=[], stack2=[5, 4, 3, 2]}
  74. }

} ```