Java实现栈和队列

本文以复习为目的，非原创。

出处：http://www.cnblogs.com/CherishFX/p/4608880.html

一、栈的数据结构实现

下面是个人实现的顺序栈：

package 栈;

/**
 * 顺序栈
 * 
 * @author 15037
 *
 * @param <T>
 */
public class MyStack<E> {
    private Object[] data = null;
    private int maxSize = 0; // 栈容量
    private int top = -1; // 栈顶指针

    public MyStack() {
        this(10);// 默认栈大小为10
    }

    public MyStack(int init) {
        if(init>=0) {
            this.maxSize = init;
            data = new Object[maxSize];
            top = -1;
        }else {
            throw new RuntimeException("初始化栈大小不能小于0:"+init);
        }
    }
    
    /**
     * 判定栈是否为空
     * @return
     */
    public boolean isEmpty() {
        return top==-1;
    }
    /**
     * 入栈操作
     * @param e
     * @return
     */
    public boolean push(E e) {
        if(top == maxSize-1) {//如果栈满了
             throw new RuntimeException("栈已满，无法将元素入栈！");
        }else {
            data[++top] = e;
            return true;
        }
    }
    /**
     * 出栈操作
     * @return
     */
    public E pop() {
        if(isEmpty()) {//如果栈空
            throw new RuntimeException("栈为空！");
        }else {
            E e =(E) data[top--];
            return e;
        }
    }
    
    /**
     * 查看栈顶元素但不移除
     */
    public E peek() {
        if(isEmpty()) {//如果栈空
            throw new RuntimeException("栈为空！");
        }else {
            E e =(E) data[top];
            return e;
        }
    }
    
    /**
     * 返回对象在栈中的位置 ,找不到返回-1，从1开始
     */
    public int search(E e) {
        for(int i = 0 ; i < maxSize ; i++) {
            if(e.equals(data[i])) {
                return i+1;
            }
        }
        return -1;
    }
    
     public static void main(String[] args) {
            MyStack<Integer> s = new MyStack<>();
            s.push(5);s.push(6);s.push(7);
            System.out.println(s.search(5));
            System.out.println(s.search(6));
            System.out.println(s.search(7));
        }
    
}

链式栈

package 栈;



public class MyLinkStack<E> {
    class Node<E> {
        E e;// 数据域
        Node<E> next;// 指针域

        public Node() {
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
    }

    private Node<E> top; // 栈顶元素
    private int size; // 当前栈大小

    public MyLinkStack() {
        top = null;
    }

    /**
     * 栈大小
     * 
     * @return
     */
    public int length() {
        return size;
    }

    /**
     * 判空
     * 
     * @return
     */
    public boolean empty() {
        return size == 0;
    }
    
    /**
     * 新元素指向top，top变为新元素，更新栈大小
     * @param e
     * @return
     */
    public boolean push(E e) {
        top = new Node(e, top);
        size++;
        return true;
    }
    
    /**
     * 查看栈顶元素但不删除
     * @return
     */
    public Node<E> peek(){
        if(empty()){
            throw new RuntimeException("空栈异常！");
        }else{
            return top;
        }
    }
    /**
          * 出栈操作，更新栈大小
     * @return
     */
    public Node<E> pop(){
        if(empty()) {
            throw new RuntimeException("空栈异常！");
        }else {
            Node temp = top.next;
            top = top.next;
            temp.next = null;//断开指针
            size--;
            return temp;
        }
    }
    
    public static void main(String[] args) {
        MyLinkStack<Integer> ls = new MyLinkStack<>();
        ls.push(5);ls.push(6);ls.push(7);
        System.out.println(ls.peek().e);
        ls.pop();
        System.out.println(ls.length());
    }
    

}

二、栈的应用举例

1、十进制转换为任意进制

原理（如转换为8进制）：N = (N div 8)*8 +(N mod 8)
备注：div是整除，mod是求模（余）

package 栈;

public class StackTest {
    
    public static void main(String[] args) {
        MyStack<Integer> ms = new MyStack<>();
        int n = 1348;
        int temp = n;
        while(temp != 0) {
            ms.push(temp%8);
            temp = temp/8;
        }
        while(!ms.isEmpty()) {
            System.out.print(ms.pop()+" ");
        }
    }
}

1、括号匹配问题

此处参考：https://blog.csdn.net/qq_26331127/article/details/50222151

package 栈;

public class StackTest2 {
    
    public static void main(String[] args) {
        check("()[]");
    }

    public static void check(String str) {
         
        MyStack<Character> stack = new MyStack<Character>();
        // 如果该String长度为奇数，不匹配
        if (str.length() % 2 == 1) {
            System.out.println("No");
        } else {
            stack = new MyStack<Character>();
 
            for (int i = 0; i < str.length(); i++) {
                if (stack.isEmpty()) {
                    stack.push(str.charAt(i)); // 当前栈是空的 存入当前位置的字符
                } else if ((stack.peek() == '[' && str.charAt(i) == ']')
                        || (stack.peek() == '(' && str.charAt(i) == ')')) {
                    stack.pop(); // 满足上面的条件 表示相邻的两个字符是一对匹配的括号 进行出栈操作
                } else {
                    stack.push(str.charAt(i));
                }
            }
 
            if (stack.isEmpty()) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
 
    }
}

总结