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

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

题目来源：大工慕课 链接
作者：Caleb Sung

关于Stack

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

Stack的Java实现

public class Homework_ds7 {public static void main(String[] args) {// TODO Auto-generated method stubStack 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("栈已满！");elsedata[++top] = x;}public int Pop() {if (isEmpty())throw new RuntimeException("空栈！");elsereturn 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 stubQueue 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.Front() + " ");}}
}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.顺序栈能够实现多栈空间共享，而顺序队列不能。