841软件工程专业综合相关代码题总结（2）—— 栈、队列相关

栈相关

1、共享栈

共享栈的结构设计

class ShareStack{
    int maxSize;
    int begin1;
    int begin2;
    int[] elem;
}
1
2
3
4
5
6

初始化

//初始化
public static int init(ShareStack stack,int maxSize){
    stack.maxSize = maxSize;
    stack.elem = new int[maxSize];
    stack.begin1 = 0;
    stack.begin2 = maxSize-1;
    return 1;
}
1
2
3
4
5
6
7
8

进栈

//进栈
public static int push(ShareStack stack,int elem,int stNo){
    if (stack.begin1+1==stack.begin2)return -1;
    if (stNo == 1){
        stack.begin1++;
        if (stack.begin1 == stack.begin2)return -1;
        stack.elem[stack.begin1] = elem;
    }else if (stNo == 2){
        stack.begin2--;
        if (stack.begin1 == stack.begin2)return -1;
        stack.elem[stack.begin2] = elem;
    }
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

出栈

//出栈
public static int pop(ShareStack stack,int stNo){
    if (stack.begin1 == 0 && stack.begin2 == stack.maxSize-1)return -1;
    if (stNo == 1){
        if (stack.begin1 == 0)return -1;
        int temp = stack.elem[stack.begin1];
        stack.begin1--;
        return temp;
    }else if (stNo == 2){
        if (stack.begin2 == stack.maxSize-1)return -1;
        int temp = stack.elem[stack.begin2];
        stack.begin2++;
        return temp;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、括号匹配

public static boolean isValid(String s) {
    //如果是奇数个，则肯定不符合匹配规则
    if (s.length() % 2 != 0)return false;
    //初始化栈
    Stack<String> stack = new Stack<>();
    //遍历字符串
    for (int i = 0; i < s.length(); i++) {
        //截取字符串中每一位字符
        String content = s.substring(i,i+1);
        //如果一开始栈为空，则直接将字符压入栈中
        if (stack.isEmpty()){
            stack.push(content);
        }
        //如果是左括号，将左括号压入栈中
        else if (content.equals("(") || content.equals("{") || content.equals("[")){
            stack.push(content);
        //如果是右括号且栈顶元素和当前右括号不匹配，则直接返回false
        }else if ((content.equals(")") && !stack.peek().equals("(")) ||
                (content.equals("}") && !stack.peek().equals("{")) ||
                (content.equals("]") && !stack.peek().equals("["))){
            return false;
        //如果匹配，则将栈顶元素出栈，继续进行匹配
        }else{
            stack.pop();
        }
    }
    //栈最终为空则说明已经完全匹配
    if (stack.isEmpty())return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3、回文字符串

public static boolean isPalindrome(String s){
    //初始化栈
    Stack<String> stack = new Stack<>();
    //遍历字符串，将字符全部压入栈中
    for (int i = 0; i < s.length(); i++) {
        stack.push(s.substring(i,i+1));
    }
    //临时变量，用来拼接字符串
    String temp = "";
    //将字符串全部出栈并进行拼接
    while(!stack.isEmpty()){
        temp+=stack.pop();
    }
    //判断是否为回文字符串
    return temp.equals(s);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4、括号的最大嵌套深度

int size = 0;
int ans = 0;
for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (c == '('){
        size++;
        ans = Math.max(size,ans);
    }else if (c == ')'){
        size--;
    }
}
return ans;
1
2
3
4
5
6
7
8
9
10
11
12

这道题其实就是求栈中最多的时候能存多少（，我们用size++以及Math.max(size,ans)和size–，其实也是模拟进出栈时栈中（的变化。因为我们只关注栈中元素数量的变化，因此不需要真的去使用栈。

5、进制转换

public static int toBinary(int num){
    Stack<Integer> stack = new Stack<>();
    int number = 0;
    int ans = num;
    while(ans >= 8){
        number = num%8;
        ans = num/8;
        stack.push(number);
    }
    if (ans != 0)stack.push(ans);
    ans = 0;
    while (!stack.isEmpty()){
        ans = ans*10 + stack.pop();
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6、表达式求值

int main() {
    //定义字符，用来接收用户输入的字符
	char ch;
    //初始化栈
	Stack<double> stack;
	//循环接受用户输入的数据
	while (scanf("%c", &ch) != '$') {
        //如果是空字符，什么都不干
		if (ch == ' ')
			continue;
        //如果是数字则将数字入栈
		if (ch != '+' && ch != '*' && ch != '/' && ch != '-') {
			stack.push(charToDouble(ch)); //其中charToDouble函数用来将字符转换成数字
        //如果是操作符，那么从栈中取出两个元素并进行相应的计算，计算完成后将结果存入栈中
		} else if (ch == '+') {
			stack.push(stack.pop() + stack.pop());
		} else if (ch == '-') {
			double d1 = stack.pop();
			double d2 = stack.pop();
			stack.push(d2 - d1);
		} else if (ch == '*') {
			stack.push(stack.pop() * stack.pop());
		} else if (ch == '/') {
			double d1 = stack.pop();
			double d2 = stack.pop();
			stack.push(d2 / d1);
		}
	}
	return stack.pop();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

7、计算器

8、判断进出栈顺序

public static boolean isValid(int[] arrays){
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < arrays.length; i++) {
        if (arrays[i] == 0 && stack.isEmpty()){
            return false;
        }else if (arrays[i] == 1)stack.push(1);
    }
    return stack.isEmpty();
}
1
2
3
4
5
6
7
8
9

队列相关

1、舞伴问题

public static void partnerQuestion(Person[] persons){
    //初始化两个队列,一个队列用来存放女士，一个队列用来存储男士
    Queues men = new Queues();
    Queues women = new Queues();
    //循环遍历数组，判断性别并存入相应的队列中
    for (int i = 0; i < persons.length; i++) {
        if (persons[i].gender == 1)men.add(persons[i]);
        else women.add(persons[i]);
    }
    //如果
    while(!men.isEmpty() && !women.isEmpty()){
        men.pop();
        women.pop();
    }
    System.out.println(men.isEmpty()?women.pop().name:men.pop().name);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、使用tag标记的循环队列

class Queue{
    static int MAXSIZE = 16;
    int front;
    int rear;
    int tag;
    int[] Q = new int[16];
    //判断队列是否为空
    public boolean isEmpty(){
        if (this.rear == front && tag == 0)return true;
        return false;
    }
    public boolean isFull(){
        if (rear == front && tag == 1)return true;
        else return false;
    }
    
    //入队操作
    public int dequeue(){
        if (isFull())return -1;
        front = (front+1)%MAXSIZE;
        tag = 0;
        return Q[front];
    }
    //出队操作
    public boolean enqueue(int elem){
        if (isEmpty())return false;
        rear = (rear+1)%MAXSIZE;
        this.Q[rear] = elem;
        tag = 1;
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

递归相关

public static int ACK(int m,int n){
    if (m == 0)return n+1;
    else if (m != 0 && n == 0)return ACK(m-1,1);
    else if (m != 0 && n != 0)return ACK(m-1,ACK(m,n-1));
    return -1;
}
1
2
3
4
5
6

（2）https://blog.csdn.net/qq_39082463/article/details/85089500