数据结构专题（二）——栈与队列

古城微笑少年丶 2022-04-23 09:06 259阅读 0赞

**什么是栈？**

其实栈就是一种后进先出的结构，就像一沓书本，每次取书本只能从最上面取，那么压在最底下的书本肯定是最先摆放在桌面上的，自然而然肯定是最后被取走的。

**什么是队列？**

队列是一种先进先出的结构，队列在生活中的例子就更多了，火车站排队，食堂买盒饭的队伍，其实都可以抽象成一个队列，每当一个人买完票或者拿到盒饭就会离开队列，先来到售票或者食堂窗口的人肯定是先买到票或者吃饭的。

数据结构其实充满了生活的影子，它们都是实际生活中抽象出来供人们更好理解计算机的工具而已。那栈与队列有什么用处呢？

先说栈吧，栈可以用来实现图的搜索算法以及括号匹配，表达式计算等功能，正因为有栈，才有现在众多能够实现括号匹配功能的开发软件，网络页面搜索等。队列正因为有先进先出的功能，可以用来实现操作系统中的消息队列功能等。

## **关于栈与队列的面试题** ##

## **　　（1）栈的创建** ##

## **　　（2）队列的创建** ##

## **　　（3）两个栈实现一个队列** ##

## **　　（4）两个队列实现一个栈** ##

## **　　（5）设计含最小函数min()的栈，要求min、push、pop、的时间复杂度都是O(1)** ##

## **　　（6）判断栈的push和pop序列是否一致** ##

## **       （7）计算表达式的值** ##

## **1. 栈的创建** ##

在Java的API本来就已经有栈与队列的对象，所以我们只需要使用已有的工具进行构造。但是若想要自己构建这两种数据结构，具体实现可以使用数组或者链表，通过设置元素的添加与删除顺序就可以形成栈或者队列的结构。接下来我将使用Java自己创建栈与队列。

class Stack {
        final int MAX_SIZE = 10;
        int[] stack;
        int top;
     
        public Stack() {
            stack = new int[MAX_SIZE];
            top = -1;
        }
     
        public void push(int data) {
            stack[++top] = data;
        }
     
        public int pop() {
            return stack[top--];
        }
     
        //查看栈顶元素
        public int peek() {
            return stack[top];
        }
     
        public boolean isEmpty() {
            return top == -1;
        }
    }

## **2. 队列的创建** ##

关于队列的创建可以使用上一章内容的链表结构，通过设置头节点与尾节点来控制链表的操作。至于Node<T>对象可以参照

数据结构（一）——数组与链表（问题解决与总结）中构建节点对象的过程。

class Queue{
    	
    	Node<Integer> front;
    	Node<Integer> rear;
    	int size = 0;
    	
    	public Queue(){
    	    front = null;
    	    rear = null;
    	}
    	
    	//队列尾部增加元素
    	public void insert(Node<Integer> newNode) {
    		
    		if(isEmpty()) {
    			front = newNode;
    		}else {
    			rear.next = newNode;
    		}
    		rear = newNode;
    		size++;
    	}
    	
    	//队头删除元素
    	public int remove() {
    		
    		int temp = 0;
    		
    		if(isEmpty()) {
    			System.out.print("the queue is empty");
    		}else {
    			
    			temp = front.data;
    			front = front.next;
    			size--;	
    		}
    		return temp;
    	}
    	
    	//取出队头元素进行查看
    	public int poll() {
    		return front.data;
    	}
    	
    	public boolean isEmpty() {
    		return front == null;
    	}
    }

## **3. 两个栈实现一个队列** ##

两个栈实现一个队列：通过绘图我们可以很清楚看到解决办法，栈1用来存储数据，栈2用来取出数据。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjM4ODYz_size_16_color_FFFFFF_t_70][]

public void stackToQueue(int[] arr) {
    		
    		Stack stack1 = new Stack();
    		Stack stack2 = new Stack();
    		
    		for(int i = 0; i < arr.length; i++) {
    			stack1.push(arr[i]);
    		}
    		
    		if(stack2.isEmpty()) {
    			while(!stack1.isEmpty()) {
    				stack2.push(stack1.pop());
    			}
    			while(!stack2.isEmpty()) {
    				System.out.println(stack2.pop());
    			}
    			
    		}
    	}

## **4. 两个队列实现一个栈** ##

思路：两个队列交替进行进队出队操作，具体的可以通过步骤示意图来进行了解。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjM4ODYz_size_16_color_FFFFFF_t_70 1][]

具体的代码实现如下：

public class queueToStack {
    	
    	Queue q1 = new Queue();
    	Queue q2 = new Queue();
    	
    	//假设队列1中有n个元素，在取数据时，需要将队列1中的n-1个元素放到队列2中存储，队列一最后一个元素则进行出队操作，该元素出队后的队列1为空
    	//此时再将队列2中的n-2个数据存储到队列1中，队列2执行出队操作，于是第二个元素就被取出，初步完成栈的操作。
    	//存储+取出的过程由两个队列交替完成。
    
    	public int pop() {
    
    		int result = 0;
    		
    		//pop操作 先判断两个队列的状态，如果q1，q2都为空，那么就没有值可以返回，此时可以设置返回-1表示异常
    		if(q1.isEmpty() && q2.isEmpty()) {
    			return -1;
    		}
    		//如果q1为空，q2不为空，那么就先操作q2
    		if(q1.isEmpty() && !q2.isEmpty()) {
    			//若q2里有多个元素，那么需要全部移动到q1中去，使得q2中只留下最后一个元素，那么这是第一个应该输出的元素
    			while(!q2.isEmpty()) {
    				result = q2.remove();
    				if(!q2.isEmpty()) {
    					q1.insert(new Node<Integer>(result));
    				}	
    			}
    		//若q1里本来有多个元素，那么需要借助q2去存储，使得q1只剩下最后一个元素的时候，那就是第一个输出元素，基本原理和上步骤一致
    		}else if(!q1.isEmpty() && q2.isEmpty()) {
    			while(!q1.isEmpty()) {
    				result = q1.remove();
    				if(!q1.isEmpty()) {
    					q2.insert(new Node<Integer>(result));
    				}
    			}
    		}
    		return result;
    	}	
    	
    	public void push(Node<Integer> newNode) {
    		
    		if(q1.isEmpty() && q2.isEmpty()) {
    			q1.insert(newNode);
    		}
    		
    		if(!q1.isEmpty() && q2.isEmpty()) {
    			q1.insert(newNode);
    		}
    		
    		if(q1.isEmpty() && !q2.isEmpty()) {
    			q2.insert(newNode);
    		}
    	}
    
    }

## **5. 设计含最小函数min()的栈，要求min、push、pop、的时间复杂度都是O(1)** ##

具体思路可以使用空间换取时间的策略，通过制造一个新的栈去比较存储最小值，每次进行进栈操作的时候都与存储在另一个栈中的最小值进行比较，对结果进行不断的更新，最后调用getMin()函数时，弹出最小栈中的值。

代码实现如下：

public class MinStack {
    	
    	Stack mainStack = new Stack();
    	Stack minStack = new Stack();
    	
    	public int pop() {
    		if(mainStack.peek() == minStack.peek()) {
    			return minStack.pop();
    		}
    		return mainStack.pop();
    	}
    	
    	public void push(int data) {
    		mainStack.push(data);
    		int min = 0;
    		if(minStack.isEmpty() || minStack.peek() >= data) {
    			min = mainStack.peek();
    			minStack.push(min);
    		}
    	}
    	
    	public int getMin() {
    		return minStack.peek();
    	}
    }

## **（6）判断栈的push和pop序列是否一致** ##

题目要求是判断栈的push与pop是否一致。要求函数接受两个整数数组的输入（两组整数对应的分别是push顺序与pop顺序），然后判断在该push顺序下是否存在输入的pop顺序。

最容易想到的解决方式就是构造一个栈模拟输入，看是否能够得到输入的pop顺序。

public void judgeStack(int[] input, int[] sample) {
    		
    		Stack s = new Stack();
    		
    		int i = 0, j = 0;
    		List<Integer> ans = new ArrayList<Integer>();
    	
    		//算法思想：设立两个指针，分别指向这两个数组，注意指针角标移动的位置，避免出现空指针异常。
    		while(i <= input.length - 1) {
    			if(input[i] != sample[j]) {
    				s.push(input[i]);
    				i++;
    			}else{
    				ans.add(sample[j]);
    				i++;
    				j++;
    			}
    		}
    		
    		while(!s.isEmpty()) {
    			int temp = s.pop();
    			ans.add(temp);
    		}
    		
    		for(int k = 0; k < ans.size(); k++) {
    			System.out.println(ans.get(k));
    		}
    	}

以上的算法占用的资源是比较大的，也许会有更好的解法，希望读者能给出更好的意见哈～

## **7. 计算表达式的值** ##

这道题目使我发自内心喜欢Python的简介，真的是“人生苦短，我用python”的真实反映了。

如果选择用python实现这个功能，那么代码将只有如下两行：

s=input()
    print(s)

这就是python非常强大的地方，如果使用Java实现，那么代码量可能就是大几十行，可能超过一百行。计算表达式的数据结构也是基于栈。首先我们需要了解的知识点有前缀，中缀与后缀表达式。

人们最常用的表达式是中缀表达式，运算符号在数字之间，需要使用括号来确定运算次序，例如：（1+2）\*3

中缀表达式符合人类的习惯，但是对于计算机来说去没有这么容易理解，所以很多时候人们会将中缀表达式变形为前缀与后缀表达式，从而让计算机更好的进行计算工作。

前缀表达式又称为“波兰式”（发明者是一位波兰科学家）其特征就是没有括号，运算符都在数字前面，例如：\* 3 + 1 2

后缀表达式的特征也是没有括号，但运算符都在数字后面，例如：3 \* 2 1 +

使用栈实现计算机的一种方法就是狄杰斯特拉的双栈模型，即创建两个栈，一个用来存在数字，另外一个用于存储各种运算符号。具体的解决过程网络上有很多啦，请读者自己查阅。

栈与队列的内容先到这儿，后期若有新的思路会进一步进行补充，以上的解法有很多可以改进的地方，希望各位读者给出宝贵的意见，共同进步，一起发展！

最后还要祝各位读者猪年大吉，幸福安康：>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjM4ODYz_size_16_color_FFFFFF_t_70]: /images/20220321/fd07924fc474426e81e3077da52856b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjM4ODYz_size_16_color_FFFFFF_t_70 1]: /images/20220321/51833e9c219e4192bf7f19f4f4b00c64.png