栈和队列

栈的实现（

容器使用前一篇的数组容器

）

1.stack接口定义

package subject.lesson02;

public interface Stack<T> {
    //是否为空
    boolean isEmpty();

    //栈中元素的个数
    int getSize();

    //压栈
    void push(T ele);


    //出栈
    T pop();

    //查看栈顶元素
    T peek();
}

2.具体接口实现

package subject.lesson02;

public class MyStack<T> implements Stack<T>{

    MyArray<T> myArray;//数据容器

    public MyStack(){
        this(10);
    }

    public MyStack(int capacity){
        myArray = new MyArray<>(capacity);
    }

    @Override
    public boolean isEmpty() {
        return myArray.isEmpty();
    }

    @Override
    public int getSize() {
        return myArray.getSize();
    }

    @Override
    public void push(T ele) {
        myArray.addTail(ele);
    }

    @Override
    public T pop() {
        return myArray.removeTail();
    }

    @Override
    public T peek() {
        return myArray.getLastElement();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("实际存储元素"+myArray.getSize()+"，内容如下：\n");
        while (!this.isEmpty()){
            sb.append(this.pop()+"<--");
        }
        return sb.substring(0,sb.lastIndexOf("-")-2).toString();
    }
}

练习（LeetCode0020）

解题思路

1. 首先我们应该先判断输入进来的字符串是否为空，如果为空则返回false

2. 之后我们遍历整个字符串，如果遇到‘(’、‘[’、‘{’则直接入栈，为后面的判断做准备

3. 如果遇到了‘)’、‘]’、‘}’。则说明字符串括号的左半边已经输入完成，此时需要将栈中元素出栈跟字符串s进行匹配

4. 最后，在return时我们不要忘记判断一次字符串是否为空，因为如果是类似于’({})]’情况，仍然需要返回false

AC代码

public class Solution {
    public boolean isValid(String s) {
        if(s==null||s.length()==0){
            throw  new IllegalArgumentException("this is empty");
        }
        Stack<Character> stack = new Stack();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='('||c=='['||c=='{'){
                stack.push(c);
            }else {
                if(stack.isEmpty()){
                    return false;
                }
                char result = stack.pop();
                if(c==')'&&result!='('){
                    return false;
                }
                if(c==']'&&result!='['){
                    return false;
                }
                if(c=='{'&&result!='}'){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

提交记录

队列的实现

• 队列也是一种线性数据结构

• 只能从一端（队尾）添加元素，从另一端（队首）取出元素

• 队列是一种先进先出的数据结构

队列的实现


Queue<E>


• void enqueue(E)
• E dequeue()
• E getFront()
• int getSize()
• boolean isEmpty()

1.队列接口

package subject.lesson02;

public interface Queue<T> {
    //获取队列中元素个数
    int getSize();
    //判断队列是否为空
    boolean isEmpty();
    //入队
    void enQueue(T ele);
    //出队
    T deQueue();
    //获取队首元素
    T getFront();
}

2.接口实现

package subject.lesson02;

public class MyQueue<T> implements Queue<T>{
    private MyArray<T> myArray;

    public MyQueue() {
        this(10);
    }

    public MyQueue(int capacity){
        myArray = new MyArray<>(capacity);
    }

    @Override
    public int getSize() {
        return myArray.getSize();
    }

    @Override
    public boolean isEmpty() {
        return myArray.isEmpty();
    }

    @Override
    public void enQueue(T ele) {
        myArray.addTail(ele);
    }

    @Override
    public T deQueue() {
        return myArray.removeHead();
    }

    @Override
    public T getFront() {
        return myArray.getFirstElement();
    }
}

循环队列

package subject.lesson02;

public class LoopQueue<T> {

    private T[] data;//数据容器
    private int size;//队列中元素的个数
    private int front;//队首指针
    private int tail;//队尾指针

    public LoopQueue(){
        this(10);
    }

    public LoopQueue(int capacity){
        this.data = (T[])new Object[capacity+1];
        this.size = 0;
        this.front = 0;
        this.tail = 0;
    }

    //获取容积
    public int getCapacity(){
        return this.data.length;
    }

    //实际存放元素的个数
    public int getSize(){
        return this.size;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return this.front == this.tail;
    }

    //扩容
    public void resize(int newCapacity){
        T[] newDate = (T[])new Object[newCapacity];
        for(int i=0;i<this.size;i++){
            newDate[i] = this.data[(this.front+i)%this.getCapacity()];
        }
        this.data = newDate;
        this.front = 0;
        this.tail = this.size;
    }

    //入队
    public void enQueue(T ele){
        //先判断队列是否已满
        if((this.tail+1)%this.getCapacity()==this.front){
            //扩容
            resize(this.getCapacity()*2-1);
        }
        this.data[this.tail]=ele;
        this.size++;
        this.tail=(this.tail+1)%this.getCapacity();
    }
    //出队
    public T deQueue(){
        //判断队列是否为空
        if(this.isEmpty()){
            throw new IllegalArgumentException("this queue is empty");
        }
        T result = this.data[this.front];
        this.size--;
        this.front = (this.front+1)%this.getCapacity();
        //缩容操作
        if(this.getSize()==this.getCapacity()/4 && this.getCapacity()/2>1){
            resize((this.getCapacity()+1)/2);
        }
        return result;
    }

    //获取队首元素
    public T getFront(){
        //判断队列是否为空
        if(this.isEmpty()){
            throw new IllegalArgumentException("this queue is empty");
        }
        return this.data[this.front];
    }
}

练习（LeetCode682. 棒球比赛）

解题思路


1.首先我们需要发现这是一个字符匹配类型的题

2.然后思考用哪种数据类型来解决。发现题目规则最多也就是对序列中的前两个数进行操作，确定使用栈的思路

3.接下来就是简单的匹配过程啦！！！

class Solution {
    public int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack();

        for(String str : ops){
            if(str.equals("+")){
                int top = stack.pop();
                int add = top+stack.peek();
                stack.push(top);
                stack.push(add);
            }else if(str.equals("D")){
                int top = stack.peek();
                stack.push(top*2);
            }else if(str.equals("C")){
                stack.pop();
            }else {
                stack.push(Integer.valueOf(str));
            }
        }
        int index = 0;
        for(int score : stack){
            index += score;
        }
        return index;
    }
}

提交记录

练习（剑指 Offer 09. 用两个栈实现队列）

思路


很清晰的一个思路

前面两个简单方法：创建栈和出栈

第三个方法：

1.先判断栈2是否为空，如果不空则将2中元素全部出栈，否则转到步骤二

2.判断栈1是否为空，如果是空的，那么说明两个栈里面都已经没有元素了，则直接返回-1。否则栈1非空，那么将1中元素出栈再压入2中

3.最后将2中元素全部出栈即可

代码实现

class CQueue {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }
        if(stack1.isEmpty()){
            return -1;
        }else {
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }
}

提交截图