【数据结构】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("回答: 这是一个好问题。");}}
}

2.5程序运行结果

三 实验总结

3.1对于问题一

1：如何将M进制数转换为十进制数？

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

2：如何将十进制数转换为N进制数？

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

3：如何将字符转换为对应的整数？

解决方案：使用charToInt方法将字符转换为对应的整数。如果字符是数字，则将其减去字符'0'的ASCII码值；如果字符是字母，则将其减去字符'A'的ASCII码值再加上10。

4：如何将整数转换为对应的字符？

解决方案：使用intToChar方法将整数转换为对应的字符。如果整数在0到9之间，则将其加上字符'0'的ASCII码值；如果整数在10到35之间，则将其加上字符'A'的ASCII码值再减去10。

在程序实现过程中，采用了面向对象的编程思想，将转换的逻辑封装在BaseConversion类中，并且通过构造函数进行初始化。这样做的好处是可以重复使用该类，并且提高代码的可读性和可维护性。

程序的优点：

1. 可以实现将任意M进制整数转换为N进制数，具有一定的通用性。

2. 使用栈和队列来辅助计算，遵循了栈先进后出和队列先进先出的特点，使得转换过程更加简洁明了。

3. 代码结构清晰，函数划分合理，易于理解和维护。

程序的缺点：

1. 没有对用户输入的数据进行验证和异常处理，如果输入的M和N不是正整数或M进制数中包含非法字符，程序可能会出现错误。

2. 对于大数字的计算可能存在效率问题，因为使用了栈和队列来存储每一位的值，当数字很大时，可能会占用较多的内存空间。

3. 在实际使用中，需要注意对输入数据的验证和异常处理，以及对大数字的计算效率优化。

3.2对于问题二

在这个实验中，我们实现了一个循环队列和学生提问的模拟。通过这个实验，我遇到了一些问题并找到了解决方法。

问题1：为什么要使用循环队列？

解决方法：循环队列可以有效地利用存储空间，通过循环利用数组空间来实现队列的功能。当队列满时，可以将队尾指针重新指向队首，实现循环利用。

问题2：如何判断队列是否为空？

解决方法：我们可以通过判断队首指针和队尾指针是否相等来判断队列是否为空。如果相等，则表示队列为空。

问题3：为什么需要定义Question类和Student类？

解决方法：Question类表示学生的问题，包含提问者和问题内容两个属性。Student类表示学生，包含姓名、学号和问题列表三个属性。通过定义这两个类，我们可以将学生的问题与学生进行关联，并方便地管理学生的问题。

程序优点：

1. 实现了循环队列的基本功能，包括入队、出队、获取队首元素和判断队列是否为空。

2. 分别定义了Question类和Student类，使得代码结构清晰，易于理解和扩展。

3. 使用了泛型，可以适应不同类型的队列元素。

程序缺点：

1. 循环队列的大小是固定的，无法动态扩容。如果队列已满，再添加元素会导致队列溢出。

2. 没有提供删除指定元素的功能，只能删除队首元素。

3. 在CircularQueue类中，没有提供获取队尾元素的方法，只能通过出队操作来获取队尾元素。

4. 没有对输入进行严格的校验，比如在enterQueue()方法中，没有判断element是否为null。

通过这个实验，我学习了循环队列的实现原理和相关操作。在今后的编程实践中，我会更加注重程序的可扩展性和灵活性，同时注意处理边界情况和异常情况，提高程序的健壮性。