乐趣区

关于数据结构:数据结构之栈和队列

jiezi

栈和队列

  • 栈也是一种线性构造
  • 相比数组，栈对应的操作是数组的子集
  • 只能从一端增加元素，也只能从一端取出元素
  • 这一端称为栈顶
  • 栈是一种后进先出的数据结构（LIFO）

举一个例子，咱们平时敲代码都常常撤销，而撤销操作的原理就是靠栈来实现的。

比方咱们先打出 “ 沉迷 ”、” 学习 ”、” 不法 ”，这个时候咱们发现打错了无奈两个字，而这个时候栈是这样的。

通过应用撤销性能，不法将从栈顶取出，而后删除不法两个字。这个时候栈中就只有两个元素。

再举一个深刻的例子：程序调用的零碎栈

假如咱们有三个函数。

咱们通过调用函数 A，在执行第二行执行 B 函数的时候，暂停函数 A。这个时候就会将暂停的函数 A 压入栈中。

而后调用函数 B 里的 C 函数时候，也会将函数 B 压入栈中，

当函数 C 执行完了当前，会首先取出栈中的 B2，而后继续执行 B2 剩下的函数，执行实现当前执行 A2。

栈的根本实现

定义一个 Stack 接口和实现类

 public interface Stack<E> {int getSize();
        boolean isEmpty();
        void push(E e);
        E pop();
        E peek();}
 public class ArrayStack<E> implements Stack<E>{
        private Array<E> array;
        public ArrayStack(){array = new Array<>();
        }
        public ArrayStack(int capacity){array = new Array<>(capacity);
        }
        @Override
        public int getSize() {return array.getSize();
        }
        @Override
        public boolean isEmpty() {return array.isEmpty();
        }
        // 增加到栈顶
        @Override
        public void push(E e) {array.addLast(e);
        }
        // 取出并移除栈顶元素
        @Override
        public E pop() {return array.removeLast();
        }
        // 查看栈顶元素
        @Override
        public E peek() {return array.get(array.getSize() - 1);
        }
        public int getCapacity(){return array.getCapacity();
        }
        @Override
        public String toString() {StringBuilder res = new StringBuilder();
            res.append("Stack:");
            res.append("[");
            for (int i = 0; i < array.getSize(); i++) {res.append(array.get(i));
                if (i != array.getSize() - 1) {res.append(",");
                }
            }
            res.append("] top");
            return res.toString();}
}

创立测试类

 public class Main {public static void main(String[] args) {ArrayStack<Integer> arrayStack = new ArrayStack<>();
            for (int i = 0; i < 5; i++) {arrayStack.push(i);
                System.out.println(arrayStack);
            }
            System.out.println("取出栈顶元素"+arrayStack.pop());
            System.out.println(arrayStack);
        }
}
    Stack: [0] top
    Stack: [0, 1] top
    Stack: [0, 1, 2] top
    Stack: [0, 1, 2, 3] top
    Stack: [0, 1, 2, 3, 4] top
            取出栈顶元素 4
    Stack: [0, 1, 2, 3] top

栈的复杂度剖析

ArrayStack<E>

  • void push(E)     O(1)
  • E pop() O(1)
  • E peek() O(1)
  • int getSize() O(1)
  • boolean isEmpty() O(1)

栈的利用 - 括号匹配器

援用 LeetCode 上 20. 无效的括号

给定一个只包含 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否无效。

无效字符串需满足：

  • 左括号必须用雷同类型的右括号闭合。
  • 左括号必须以正确的程序闭合。
  • 留神空字符串可被认为是无效字符串。

具体思路就是判断以后是左侧括号还是右侧，如果是左侧就压入栈，当是右侧的时候就取出栈顶元素进行顺次匹配。

class Solution {public boolean isValid(String s) {if(s.isEmpty()) {return true;}
            if (s.length() % 2 != 0){return false;}
            Stack<Character> stack=new Stack<>();
            for(char c:s.toCharArray()){if(c=='(') {stack.push(')');
                } else if(c=='{') {stack.push('}');
                } else if(c=='[') {stack.push(']');
                } else if(stack.empty()||c!=stack.pop()) {return false;}
            }
            return stack.empty();}
}

队列的根本实现

  • 队列也是一种线性构造
  • 相比数组，队列对应的操作是数组的子集
  • 只能从队尾增加元素，只能从队首取出元素
  • 队列是一种先进先出的数据结构（FIFO）

很容易了解，和生存中的排队是一样的。

public interface Queue<E> {int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();}
public class ArrayQueue<E> implements Queue<E> {
        private Array<E> array;
        public ArrayQueue() {array = new Array<>();
        }
        public ArrayQueue(int capacity) {array = new Array<>(capacity);
        }
        @Override
        public int getSize() {return array.getSize();
        }
        @Override
        public boolean isEmpty() {return array.isEmpty();
        }
        // 插入队尾
        @Override
        public void enqueue(E e) {array.addLast(e);
        }
        // 拿出队首元素
        @Override
        public E dequeue() {return array.removeFirst();
        }
        // 查看队首元素
        @Override
        public E getFront() {return array.get(0);
        }
        public int getCapacity(){return array.getCapacity();
        }
        @Override
        public String toString() {StringBuilder res = new StringBuilder();
            res.append("Queue:");
            res.append("front [");
            for (int i = 0; i < array.getSize(); i++) {res.append(array.get(i));
                if (i != array.getSize() - 1) {res.append(",");
                }
            }
            res.append("] tail");
            return res.toString();}
}

数组队列的复杂度剖析

ArrayQueue<E>

  • void enqueue(E) O(1)
  • E dequeue() O(n)
  • E front() O(1)
  • int getSize() O(1)
  • boolean isEmpty O(1)

循环队列

因为数组队列的出队操作是 O(n) 的，是存在肯定的局限性，应用循环队列来解决这个问题。

因为咱们在删除索引为 0 的数据时候，会导致前面的数据前移，所以是 O(n) 级别。

循环队列其实就是在队首移除的时候，咱们不进行前面数据的挪动，而是应用 front 变量进行自增，而后指向下一个元素，tail 变量来保护队尾的地位。

一开始的时候，front 和 tail 都指向索引 0 的地位。

当新增一个元素后，tail 进行自增而后指向下一个元素的地位，而 front 放弃不变。

而移除一个队首元素的时候，front 要进行自增而后指向下一个元素的地位，tail 放弃不变，这样的话咱们不须要挪动对象，只须要更改 front 的指向即可。

那为什么叫循环队列呢，因为咱们当队列满了的时候，咱们须要进行 (tail+1) % capacity 操作，而后将 tail 指向新的地位。

当咱们在 0 的地位再新增一个元素的时候，咱们如何判断队列是否满了呢，因为咱们之前说过 front == tail 的时候阐明数组为空，而咱们应用循环队列的话，咱们须要应用 (tail + 1) % capacity == front 就阐明队列满了须要进行扩容。须要阐明循环队列会节约一个空间。

循环队列的实现

public interface Queue<E> {int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();}
public class LoopQueue<E> implements Queue<E> {private E[] data;
        private int front, tail;
        private int size;
        public LoopQueue(int capacity) {
            // 因为循环队列须要节约一个空间，所以要将数组大小 +1
            data = (E[]) new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
        public LoopQueue() {this(10);
        }
        public int getCapacity() {return data.length - 1;}
        @Override
        public int getSize() {return size;}
        @Override
        public boolean isEmpty() {return front == tail;}
        @Override
        public void enqueue(E e) {if ((tail + 1) % data.length == front) {resize(getCapacity() * 2);
            }
            data[tail] = e;
            tail = (tail + 1) % data.length;
            size++;
        }
        @Override
        public E dequeue() {if (isEmpty()) {throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            }
            E ret = data[front];
            data[front] = null;
            front = (front + 1) % data.length;
            size--;
            if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {resize(getCapacity() / 2);
            }
            return ret;
        }
        @Override
        public E getFront() {if (isEmpty()) {throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            }
            return data[front];
        }
        private void resize(int newCapacity) {E[] newData = (E[]) new Object[newCapacity + 1];
            for (int i = 0; i < size; i++) {newData[i] = data[(i + front) % data.length];
            }
            data = newData;
            front = 0;
            tail = size;
        }
        @Override
        public String toString() {StringBuilder res = new StringBuilder();
            res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
            res.append("front [");
            for(int i = front ; i != tail ; i = (i + 1) % data.length){res.append(data[i]);
                if((i + 1) % data.length != tail) {res.append(",");
                }
            }
            res.append("] tail\n");
            res.append("front ="+front);
            res.append("，tail ="+tail);
            res.append("，data.length ="+data.length);
            return res.toString();}
}

循环队列的复杂度剖析

LoopQueue<E>

  • void enqueue(e) O(1)
  • E dequeue() O(1)
  • E getFront() O(1)
  • int getSize() O(1)
  • boolean isEmpty() O(1)
退出移动版