Java数据结构：堆栈与队列/Stack & Queue（第八周）

谁践踏了优雅 2022-05-14 02:29 173阅读 0赞

题目来源：大工慕课 [链接][Link 1]  
作者：Caleb Sung

# 关于Stack #

*  stack 是堆栈容器， 是一种“先进后出” 的容器。
 *  stack 是简单地装饰 deque 容器而成为另外的一种容器。

# Stack的Java实现 #

public class Homework_ds7 {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Stack sk = new Stack(10);
            sk.randomFull();
            System.out.println("随机生成的栈为：");
            for (int i : sk.getData())
                System.out.print(i + " ");
            System.out.println();
            System.out.println("出栈：");
            System.out.println(sk.Pop());
            System.out.println(sk.Pop());
            System.out.println("'20' '1'进栈后：");
            sk.Push(20);
            sk.Push(1);
            for (int i : sk.getData())
                System.out.print(i + " ");
        }
    
    }
    
    class Stack {
        private int[] data;
        private int top;
    
        public Stack(int max) {
            top = -1;
            data = new int[max];
        }
    
        public boolean isFull() {
            return top == data.length - 1;
        }
    
        public boolean isEmpty() {
            return top == -1;
        }
    
        public void Push(int x) {
            if (isFull())
                System.out.println("栈已满！");
            else
                data[++top] = x;
        }
    
        public int Pop() {
            if (isEmpty())
                throw new RuntimeException("空栈！");
            else
                return data[top--];
        }
    
        public void randomFull() {
            for (int i = 0; i < data.length; i++) {
                data[i] = (int) (Math.random() * 100);
                top++;
            }
        }
    
        public int[] getData() {
            return data;
        }
    }

# 关于Queue #

*  queue 是队列容器， 是一种“先进先出” 的容器。
 *  queue 是简单地装饰 deque 容器而成为另外的一种容器。

# Queue的Java实现 #

public class Homework_ds8_ {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Queue q = new Queue();
            for (int i = 0; i < 10; i++)
                q.enqueue((int) (Math.random() * 100));
            System.out.println("随机生成的队列为： ");
            int[] a = new int[10];
            a = q.getQueueArray();
            for (int i = 0; i < 10; i++)
                System.out.print(a[i] + " ");
    
            System.out.println("\n出队列 ");
            for (int i = 0; i < 10; i++) {
                q.dequeue();
                System.out.print(q.getFront() + " ");
            }
        }
    }
    
    class Queue {
    
        private int head = 0;
        private int tail = 0;
        private int count = 0;
        private int size = 10;
        private int[] array = new int[size];
    
        public Queue() {
    
        }
    
        public boolean isFull() {
            return count == size;
        }
    
        public boolean isEmpty() {
            return count == 0;
        }
    
        public boolean enqueue(int item) {
            if (isFull()) {
                System.out.println("full queue");
                return false;
            }
            array[tail] = item;
            tail = (tail + 1) % size;
            count++;
            return true;
        }
    
        public int dequeue() {
            if (!isEmpty()) {
                int item = array[head];
                head = (head + 1) % size;
                count--;
                return item;
            }
            return 0;
        }
    
        public int getFront() {
            if (!isEmpty())
                return array[head];
            return 0;
        }
    
        public int[] getQueueArray() {
            return array;
        }
    
        public void clear() {
            head = tail = count = 0;
        }
    }

# Stack和Queue的异同点 #

## 1、栈与队列的相同点： ##

1.都是线性结构。  
2.插入操作都是限定在表尾进行。  
3.都可以通过顺序结构和链式结构实现。、  
4.插入与删除的时间复杂度都是O（1），在空间复杂度上两者也一样。  
5.多链栈和多链队列的管理模式可以相同。

## 2、栈与队列的不同点： ##

1.删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。  
2.应用场景不同；常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。  
3.顺序栈能够实现多栈空间共享，而顺序队列不能。

[Link 1]: https://mooc.dlut.edu.cn/