【数据结构】6栈

0

章节

3．1到3．3小节。

认知与理解栈结构；

列举栈的操作特点。

理解并列举栈的应用案例。

重点

栈的特点与实现；

难点

栈的灵活实现与应用

作业或思考题

完成学习测试２，？

内容达成以下标准(考核点)：

正确实现栈基本操作；

分析总结栈与队列实现算法；

作业4：栈和队列基本操作

一、题目及分析

1.1题目

有两组型数：A（99，98，89，88，78，78，69，68）和B（89，88，87，86，85，84，83，82，81），

（1）分别建立顺序栈和链栈，来存放A和B，实现数据入栈和出栈操作，输出一种数据元素入栈和对应出栈列表；

（2）分别建立顺序队列和链队列，来存放A和B，实现数据入队和出队操作，输出数据元素入队和出队顺序；

1.2分析问题与实现工程类结构图

题目要求使用顺序栈、链栈、顺序队列和链队列来存放两组数据A和B，并实现相应的入栈、出栈、入队和出队操作。需要分析每种数据结构的特点和操作过程，然后根据题目要求编写相应的代码。

1. 顺序栈（数组）：顺序栈是一种使用数组实现的栈，具有先进后出（LIFO）的特点。入栈操作即将数据元素依次添加到栈顶，出栈操作即将栈顶元素移除并返回。入栈操作时，需要判断栈是否已满，若未满则将元素添加到栈顶；出栈操作时，需要判断栈是否为空，若不为空则将栈顶元素移除并返回。由于顺序栈的栈顶位置在数组的末尾，所以入栈、出栈操作的时间复杂度均为O(1)。

2. 链栈：链栈是一种使用链表实现的栈，同样具有先进后出的特点。内存动态分配，无固定大小限制。入栈操作即将数据元素添加到链表的头部，出栈操作即将链表头部元素移除并返回。入栈操作时，需要新建一个节点并将其添加到链表头部；出栈操作时，需要判断链表是否为空，若不为空则将链表头部节点移除并返回。由于链栈的栈顶位置在链表的头部，所以入栈、出栈操作的时间复杂度均为O(1)。

3. 顺序队列（数组）：顺序队列是一种使用数组实现的队列，具有先进先出（FIFO）的特点。入队操作即将数据元素添加到队尾，出队操作即将队头元素移除并返回。入队操作时，需要判断队列是否已满，若未满则将元素添加到队尾；出队操作时，需要判断队列是否为空，若不为空则将队头元素移除并返回。由于顺序队列的队头和队尾位置在数组的两端，所以队列的元素位置可能会发生变动，需要使用循环队列来解决这个问题。循环队列可以通过“头尾相接”来实现，入队、出队操作的时间复杂度均为O(1)。

4. 链队列：链队列是一种使用链表实现的队列，同样具有先进先出的特点。入队操作即将数据元素添加到链表的尾部，出队操作即将链表头部元素移除并返回。入队操作时，需要新建一个节点并将其添加到链表尾部；出队操作时，需要判断链表是否为空，若不为空则将链表头部节点移除并返回。由于链队列的队头和队尾位置分别在链表的头部和尾部，所以入队、出队操作的时间复杂度均为O(1)。

对于每种数据结构，我们需要编写入栈、出栈、入队、出队的代码，并输出数据元素入栈和对应出栈列表，以及数据元素入队和出队的顺序。

1.3工程类结构图

二、类的实现

2.1 SeqStck类代码

package homework4;//1,顺序栈
public class SeqStack<T> {private int maxSize; // 栈的最大容量private Object[] stackArray; // 存储栈元素的数组private int top; // 栈顶指针，指向栈顶元素的下标// 构造方法，初始化栈public SeqStack(int size) {maxSize = size;stackArray = new Object[maxSize];top = -1;}// 判断栈是否为空public boolean isEmpty() {return top == -1;}// 判断栈是否已满public boolean isFull() {return top == maxSize - 1;}// 入栈操作public void push(T data) {if (isFull()) {System.out.println("栈已满，无法入栈");return;}stackArray[++top] = data;}// 出栈操作public T pop() {if (isEmpty()) {System.out.println("栈为空，无法出栈");return null;}return (T) stackArray[top--];}}

2.2 LinkedStack类代码

package homework4;//2,链栈
public class LinkedStack<T> {private Node<T> top; // 栈顶节点// 构造方法，初始化链栈public LinkedStack() {top = null;}// 判断链栈是否为空public boolean isEmpty() {return top == null;}// 入栈操作public void push(T data) {Node<T> newNode = new Node<>(data);newNode.next = top;top = newNode;}// 出栈操作public T pop() {if (isEmpty()) {System.out.println("链栈为空，无法出栈");return null;}T data = top.data;top = top.next;return data;}// 链栈节点的定义private class Node<T> {private T data;private Node<T> next;public Node(T data) {this.data = data;}}
}

2.3 SeqQueue类代码

package homework4;//3,顺序队列
public class SeqQueue<T> {private int maxSize; // 队列的最大容量private Object[] queueArray; // 存储队列元素的数组private int front; // 队头指针，指向队头元素的下标private int rear; // 队尾指针，指向队尾元素的下标的后一个位置// 构造方法，初始化队列public SeqQueue(int size) {maxSize = size;queueArray = new Object[maxSize];front = rear = 0;}// 判断队列是否为空public boolean isEmpty() {return front == rear;}// 判断队列是否已满public boolean isFull() {return (rear + 1) % maxSize == front;}// 入队操作public void enqueue(T data) {if (isFull()) {System.out.println("队列已满，无法入队");return;}queueArray[rear] = data;rear = (rear + 1) % maxSize;}// 出队操作public T dequeue() {if (isEmpty()) {System.out.println("队列为空，无法出队");return null;}T data = (T) queueArray[front];front = (front + 1) % maxSize;return data;}
}

2.4 LinkedQueue类代码

package homework4;//4,链队列
public class LinkedQueue<T> {private Node<T> front; // 队头节点private Node<T> rear; // 队尾节点// 构造方法，初始化链队列public LinkedQueue() {front = rear = null;}// 判断链队列是否为空public boolean isEmpty() {return front == null;}// 入队操作public void enqueue(T data) {Node<T> newNode = new Node<>(data);if (isEmpty()) {front = rear = newNode;} else {rear.next = newNode;rear = newNode;}}// 出队操作public T dequeue() {if (isEmpty()) {System.out.println("链队列为空，无法出队");return null;}T data = front.data;front = front.next;if (front == null) {rear = null;}return data;}// 链队列节点的定义private class Node<T> {private T data;private Node<T> next;public Node(T data) {this.data = data;}}
}

2.5 Main类代码

package homework4;public class Main {public static void main(String[] args) {// 分别建立顺序栈和链栈来存放ASeqStack<Integer> seqStackA = new SeqStack<>(8);LinkedStack<Integer> linkedStackA = new LinkedStack<>();int[] stackDataA = {99, 98, 89, 88, 78, 78, 69, 68};for (int j : stackDataA) {seqStackA.push(j);linkedStackA.push(j);}System.out.println("顺序栈A出栈顺序：");while (!seqStackA.isEmpty()) {System.out.print(seqStackA.pop() + " ");}System.out.println();System.out.println("链栈A出栈顺序：");while (!linkedStackA.isEmpty()) {System.out.print(linkedStackA.pop() + " ");}System.out.println();// 分别建立顺序队列和链队列来存放BSeqQueue<Integer> seqQueueB = new SeqQueue<>(10);LinkedQueue<Integer> linkedQueueB = new LinkedQueue<>();int[] queueDataB = {89, 88, 87, 86, 85, 84, 83, 82, 81};for (int j : queueDataB) {seqQueueB.enqueue(j);linkedQueueB.enqueue(j);}System.out.println("顺序队列B出队顺序：");while (!seqQueueB.isEmpty()) {System.out.print(seqQueueB.dequeue() + " ");}System.out.println();System.out.println("链队列B出队顺序：");while (!linkedQueueB.isEmpty()) {System.out.print(linkedQueueB.dequeue() + " ");}System.out.println();}
}

三、结果与总结

3.1程序运行结果

3.2总结

SeqStack类、LinkedStack类、SeqQueue类和LinkedQueue类分别实现了顺序栈、链栈、顺序队列和链队列数据结构。它们的优点和缺点如下：

SeqStack类的优点：

1. 使用数组实现，插入和删除元素的时间复杂度为O(1)，具有较高的效率。

2. 对于固定大小的栈，空间利用率较高。

SeqStack类的缺点：

1. 需要预先指定栈的最大容量，如果栈的元素个数超过了容量，会导致栈溢出。

2. 在插入或删除元素时，需要移动其他元素的位置，效率较低。

LinkedStack类的优点：

1. 使用链表实现，插入和删除元素的时间复杂度为O(1)，具有较高的效率。

2. 不需要预先指定栈的最大容量，可以根据实际需求动态调整。

LinkedStack类的缺点：

1. 需要额外的内存空间存储链表节点的指针，占用较多的内存。

2. 对于频繁插入或删除元素的操作，可能会导致频繁的内存分配和释放，影响性能。

SeqQueue类的优点：

1. 使用数组实现，循环队列的方式解决了队列满时无法插入元素的问题。

2. 插入和删除元素的时间复杂度为O(1)，具有较高的效率。

SeqQueue类的缺点：

1. 需要预先指定队列的最大容量，如果队列的元素个数超过了容量，会导致队列溢出。

2. 在删除元素时，需要移动其他元素的位置，效率较低。

LinkedQueue类的优点：

1. 使用链表实现，插入和删除元素的时间复杂度为O(1)，具有较高的效率。

2. 不需要预先指定队列的最大容量，可以根据实际需求动态调整。

LinkedQueue类的缺点：

1. 需要额外的内存空间存储链表节点的指针，占用较多的内存。

2. 对于频繁插入或删除元素的操作，可能会导致频繁的内存分配和释放，影响性能。

3. 在获取队列长度时，需要遍历整个链表，效率较低。

综上所述，不同的数据结构适用于不同的场景。如果需要固定大小的栈或队列，并且对空间利用率有要求，可以选择SeqStack类和SeqQueue类；如果需要动态调整大小的栈或队列，并且对内存占用有要求，可以选择LinkedStack类和LinkedQueue类。

实验2：栈和队列的应用

一、题目一

1.1题目

编程实现将一个M进制整数转换成N进制数，程序运行时M和N由键盘输入（M和N为正整数），并将一个具体M进制数转成N进制数输出。

1.2问题的分析

根据题目要求，我们需要将一个M进制整数转换为N进制数。具体而言，需要完成以下几个步骤：

1. 从键盘读取输入的M和N（M和N为正整数）。

2. 从键盘读取输入的M进制整数。

3. 将M进制整数转换为十进制数（使用栈来存储每一位的值，计算时需要按权展开累加）。

4. 将十进制数转换为N进制数（使用队列来存储每一位的值，求余数并入队，再不断整除进队）。

5. 输出转换后的N进制数。

在上述步骤中，我们可以使用栈来实现将M进制整数转换为十进制数，因为栈具有后进先出的特性，适合处理从右到左的操作。而将十进制数转换为N进制数，我们可以使用队列来实现，因为队列具有先进先出的特性，适合处理从左到右的操作。

1.3 工程中类结构图

类BaseConversion，该类包含以下成员变量：

num：待转换的M进制整数；
M：原进制；
N：目标进制；
decimalNum：转换为十进制的数字；
convertedNum：转换为N进制的结果。

该类可以包含以下方法：

构造函数：接收M进制整数、原进制和目标进制，将M进制整数转换为十进制数，并将十进制数转换为目标进制数；
convertToDecimal方法：接收M进制整数和原进制，将M进制整数转换为十进制数，并使用栈来辅助计算；
convertFromDecimal方法：接收十进制数和目标进制，将十进制数转换为目标进制数，并使用队列来辅助计算；
charToInt方法：将一个字符转换为对应的整数；
intToChar方法：将一个整数转换为对应的字符；
printResult方法：输出转换后的N进制数。

类Test1

在主函数中，可以从键盘读取输入的M和N值以及M进制数，然后创建一个BaseConversion对象进行转换，最后输出转换后的N进制数。

1.4各个类的实现

通过BaseConversion类中的convertToDecimal和convertFromDecimal函数将M进制数转换为十进制数，再将十进制数转换为N进制数。在main函数中，先读取输入的M和N值以及M进制数，然后创建一个BaseConversion对象进行转换，最后输出转换后的N进制数。

首先定义了BaseConversion类，该类包含了num（待转换的M进制整数）、M（原进制）、N（目标进制）、decimalNum（转换为十进制的数字）和convertedNum（转换为N进制的结果）等成员变量。

在构造函数中，将输入的M进制整数转换为十进制数，并将十进制数转换为N进制数。

convertToDecimal方法使用了栈来辅助计算，从num的最后一位开始，通过charToInt将字符转换为对应的数字，并根据M的幂次进行累加得到十进制数。

convertFromDecimal方法使用了队列来辅助计算，通过不断将十进制数除以N，得到余数并入队列，直到十进制数变为0。然后依次出队列，通过intToChar将数字转换为对应的字符，构建出N进制数的字符串表示。

接着是定义了charToInt方法和intToChar方法，用于字符和数字的相互转换。

在printResult方法中，输出转换后的N进制数。

最后，在Test1类的main函数中，从键盘读取输入的M和N，并输入待转换的M进制整数。然后创建一个BaseConversion对象，并传入参数进行转换。最后调用printResult方法输出转换后的结果。

1.4.1 BaseConversion类代码

package experience2;import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;public class BaseConversion {private String num;private int M;private int N;private int decimalNum;private String convertedNum;public BaseConversion(String num, int M, int N) {this.num = num;this.M = M;this.N = N;// 将输入的M进制整数转换为十进制数decimalNum = this.convertToDecimal(num, M);// 将十进制数转换为N进制数convertedNum = this.convertFromDecimal(decimalNum, N);}// 将一个M进制整数转换为十进制数public static int convertToDecimal(String num, int M) {int decimalNum = 0;int power = 1;Stack<Integer> stack = new Stack<>();for (int i = num.length() - 1; i >= 0; i--) {int digit = charToInt(num.charAt(i));decimalNum += digit * power;power *= M;}return decimalNum;}// 将一个十进制数转换为N进制数public static String convertFromDecimal(int decimalNum, int N) {Queue<Integer> queue = new LinkedList<>();while (decimalNum > 0) {int remainder = decimalNum % N;queue.offer(remainder);decimalNum /= N;}StringBuilder sb = new StringBuilder();while (!queue.isEmpty()) {sb.append(intToChar(queue.poll()));}return sb.toString();}// 将一个字符转换为对应的整数private static int charToInt(char ch) {if (ch >= '0' && ch <= '9') {return ch - '0';} else {return ch - 'A' + 10;}}// 将一个整数转换为对应的字符private static char intToChar(int num) {if (num >= 0 && num <= 9) {return (char) ('0' + num);} else {return (char) ('A' + num - 10);}}public void printResult () {// 输出转换后的N进制数System.out.println(num + "的" + N + "进制表示为：" + convertedNum);}
}

1.4.2 Test1类代码

package experience2;import java.util.Scanner;public class Test1 {public static void main(String[] args) {// 从键盘读取输入的M和NScanner scanner = new Scanner(System.in);System.out.println(">=======将一个M进制整数转换成N进制数========<");System.out.print("请输入M的值：");int M = scanner.nextInt();System.out.print("请输入N的值：");int N = scanner.nextInt();// 从键盘读取输入的M进制整数System.out.print("请输入一个M进制整数：");String num = scanner.next();// 创建一个BaseConversion对象，并传入参数
//        BaseConversion bc = new BaseConversion("123", 8, 2);BaseConversion bc = new BaseConversion(num, M, N);//输出结果, 输出转换后的N进制数bc.printResult();}
}

1.5程序运行结果

二、题目二

2.1题目

数据结构是一门较难的课程，同学们学习时问题较多，请你编写一个课程答疑程序，对多个同学的问题进行一一解答。

2.2问题的分析

这个程序的主要目标是模拟一个课堂答疑环境。在这个环境中，学生可以提出问题，问题被放入一个队列中，然后老师从队列中取出问题并回答。

这个程序的设计涉及到几个主要的问题：

1. 如何表示学生和问题？

创建了一个学生类和一个问题类来解决这个问题。学生类包含学生的姓名、编号和他们提出的问题列表。问题类包含提问者和问题内容。

2. 如何存储问题？

使用一个循环队列来存储问题。循环队列是一种特殊的队列，当队列满时，新的元素会被添加到队列的开头。这种数据结构非常适合模拟这个问题，因为它可以保证问题按照先进先出的顺序被回答。

3. 如何处理问题？

创建学生对象和问题对象，然后将问题添加到循环队列中。然后，使用一个循环，从队列中取出问题并回答，直到队列为空。

需求:

1. 需要定义一个学生类（Student），包含学生的姓名、学号和问题列表。

2. 需要定义一个问题类（Question），包含提问者（学生对象）和问题内容。

3. 需要定义一个循环队列类（CircularQueue），实现队列接口（QueueInterface），用于存储学生的问题。

4. 主类（Main）中，创建循环队列对象和多个学生对象，并将学生的问题加入队列中。

5. 使用循环队列模拟老师回答问题的过程，从队列中取出问题并进行回答。

2.3工程中类结构图

程序包括以下几个部分：

1. 接口QueueInterface：定义了队列的基本操作，包括入队、出队、获取队头元素和判断队列是否为空。

2. 类CircularQueue：实现了QueueInterface接口，代表一个循环队列。它使用数组实现队列，并记录了队列的大小、队头和队尾指针。具体的功能包括入队、出队、获取队头元素和判断队列是否为空。

3. 类Question：代表一个问题，包含提问者和问题内容。它提供了输出问题信息的方法。

4. 类Student：代表一个学生，包含学号、姓名和问题列表。它提供了添加问题和输出学生信息的方法。

5. 主类Main：在main方法中创建了一个CircularQueue对象和两个Student对象，并将学生的问题加入队列中。然后通过循环从队列中取出问题并回答。

程序的运行逻辑如下：

1. 创建循环队列对象queue。

2. 创建两个Student对象s1和s2，并为每个学生添加问题。

3. 将学生的问题加入队列中。

4. 循环从队列中取出问题，回答问题，并输出回答内容。

2.4各个类的实现

2.4.1 CircularQueue类代码

package experience2.t2;// 定义循环队列，实现接口
public class CircularQueue<T> implements Queue<T> {private T[] queue;private int size;int front, rear;public CircularQueue() {front = rear = 0;size = 5;queue = (T[]) (new Object[size]);}void setSize(int n) {this.size = n;}public void enterQueue(T element) {if ((rear + 1) % size == front) {System.out.print("队列满");return;}queue[rear] = element;rear = (rear + 1) % size;System.out.println("  front=" + front + ",rear=" + rear);}public T delQueue() {if (isEmpty()) {System.out.print("队空");return null;}T queueHead = queue[front];front = (front + 1) % size;System.out.println("  front=" + front + ",rear=" + rear);return queueHead;}public T getHead() {if (isEmpty()) {System.out.print("队空");return null;}T queueHead = queue[front + 1];System.out.println("  front=" + front + ",rear=" + rear);return queueHead;}public boolean isEmpty() {return rear == front;}
}

2.4.2 Question类代码

package experience2.t2;public class Question {Student asker;String content;public Question(Student asker, String content) {this.asker = asker;this.content = content;}public void outInformation() {System.out.println("来自 " + asker.name + " 的问题: " + content);}
}

2.4.3 Queue接口代码

package experience2.t2;// 定义接口规范队列完成功能
public interface Queue<T> {void enterQueue(T element);T delQueue();T getHead();boolean isEmpty();
}

2.4.4 Student类代码

package experience2.t2;import java.util.ArrayList;
import java.util.List;public class Student {String num;String name;List<Question> questions;public Student(String name, String num) {this.num = num;this.name = name;this.questions = new ArrayList<>();}public void addQuestion(Question question) {this.questions.add(question);}public void outInformation() {System.out.println(name + "," + num);}
}

2.4.5 Test2类代码

package experience2.t2;public class Test2 {public static void main(String[] args) {CircularQueue<Question> queue = new CircularQueue<>();Student s1 = new Student("LiMing", "123456789");s1.addQuestion(new Question(s1, "数据结构是什么?"));s1.addQuestion(new Question(s1, "队列是如何工作的?"));Student s2 = new Student("YiMing", "2323345");s2.addQuestion(new Question(s2, "什么是栈?"));s2.addQuestion(new Question(s2, "二叉树是如何工作的?"));// 学生提问for (Question question : s1.questions) {queue.enterQueue(question);}for (Question question : s2.questions) {queue.enterQueue(question);}// 老师回答问题while (!queue.isEmpty()) {Question question = queue.delQueue();System.out.println("回答问题: ");question.outInformation();System.out.println("回答: 这是一个好问题。");}}
}