链式队列/链式栈

- 日理万妓 2021-09-23 07:02 410阅读 0赞

### Java实现链式队列 ###

/**
     * @auther: 巨未
     * @DATE: 2019/1/5 0005 20:49
     * @Description:  链式队列
     */
    class LinkQueue{
        class Entry{
            int data;
            Entry next;
    
            public Entry(){
                this.data = -1;
                this.next = null;
            }
    
            public Entry(int val){
                this.data = val;
                this.next = null;
            }
        }
    
        private Entry front;
        private Entry rear;
        private int usedSize;
    
        public LinkQueue(){
            this.front = null;
            this.rear = null;
            this.usedSize = 0;
        }
    
        /*入队*/
        public void push(int val) {
            if (isEmpty()) {
                //第一次入队
                    rear = new Entry(val); //新建一个节点
                    front = rear;
                } else {
                    //非第一次入队
                    Entry entry = new Entry(val); //新建一个节点，让rear的next域指向新节点的地址，然后更新rear
                    rear.next = entry;
                    rear = rear.next;
                }
                this.usedSize++;
            }
        /*判空*/
        public boolean isEmpty(){
            return this.usedSize ==0;
        }
    
        /*出队*/
        public int pop(){
            if(isEmpty()){
                throw new UnsupportedOperationException("is Empty");
            }
            int data = this.front.data;
            this.front = this.front.next;  //front指向front的next节点
            return data;
        }
        /*打印*/
        public void show(){
            Entry cur = this.front;
          while(cur != null) {
              System.out.print(cur.data + " ");
              cur = cur.next;
            }
            System.out.println();
        }
    
    
    }
    public class LinkQueueDemo {
    
        public static void main(String[] args) {
        LinkQueue linkQueue = new LinkQueue();
        linkQueue.push(10);
        linkQueue.push(20);
        linkQueue.push(90);
        linkQueue.show();   // 10 20 90
        //linkQueue.pop();
            System.out.println(linkQueue.pop());  //10出栈
        linkQueue.show();  // 20 90
        }
    }

### Java实现链式栈 ###

/**
     * @auther: 巨未
     * @DATE: 2019/1/5 0005 18:55
     * @Description:  链式栈  ......................
     */
    class LinkStack{
        class Entry{
            int data;
            Entry next;
    
            public Entry(){
                this.data = -1;
                this.next = null;
            }
            public Entry (int val) {
                this.data = val;
                this.next = null;
            }
        }
        private  Entry head = null;
    
        public LinkStack(){   //得到头结点的引用
            this.head = new Entry();
        }
        /*入栈 === 头插法*/
        public void push(int val) {
            if(isFull()){
                return;
            }
            Entry entry = new Entry(val);
            entry.next = this.head.next;
            this.head.next = entry;
        }
        /*出栈*/
        public void pop(){
            if(isEmpty()){
                return;
            }
            Entry del = this.head.next; //删除第一个数据节点
            this.head.next = del.next;
        }
        /*判满*/
        public boolean isFull(){
            if(this.head == null) {
                return true;
            }
            return false;
        }
        /*判空*/
        public boolean isEmpty(){
            if(this.head.next == null) {
                return true;
            }
            return false;
        }
        /*得到栈顶元素*/
        public int getTop(){
            if(isEmpty()){
                throw new UnsupportedOperationException("stack is empty！");
            }
            return this.head.next.data;
        }
        /*打印*/
        public void show(){
            Entry cur = this.head.next;
            while (cur != null) {;
                System.out.print(cur.data+ " ");
                cur = cur.next;
            }
            System.out.println();
        }
    }
    public class LinkStackDemo {
    
        public static void main(String[] args) {
            LinkStack linkStack  = new LinkStack();
            linkStack.push(1);
            linkStack.push(4);
            linkStack.push(2);
            linkStack.push(9);
            linkStack.show();//9 2 4 1
            System.out.println(linkStack.getTop());// 9
            linkStack.pop();//9
            linkStack.show();// 2 4 1
        }
    }