栈和队列

1.用两个栈实现队列
2.包含min函数的栈
3.栈的压入弹出序列

正文

栈和队列

1. 用两个栈实现队列

题目表述

用两个栈实现一个队列。队列的声明如下:请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。

解题思路

一个栈用来存储插入队列数据，一个栈用来从队列中取出数据。从第一个栈向第二个栈转移数据的过程中：数据的性质已经从后入先出变成了先入先出。

代码

import java.util.Stack;
public class  {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void appendTail(int node) {
        stack1.push(node);
    }
    
    public int deleteHead() {
        if(stack2.isEmpty())
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
        if(stack2.isEmpty())
            throw new RuntimeException("queue is empty");
        return stack2.pop();
    }
}

2. 包含min函数的栈

题目表述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push 及 pop 的时间复杂度都是 O（1）。

解题思路

有关栈的题目，可以考虑使用“辅助栈”，即利用空间换时间的方法。

这道题就是借助“辅助栈”来实现。当有新元素被 push 进普通栈的时候，程序比较新元素和辅助栈中的原有元素，选出最小的元素，将其放入辅助栈。

根据栈的特点和操作思路，辅助栈顶的元素就是最小元素。并且辅助栈的元素和普通栈的元素是“一一对应”的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24< 大专栏  面试准备之刷题总结：栈和队列/span>

import java.util.Stack;

public class  {

    private Stack<Integer> dataStack = new Stack<Integer>();
    private Stack<Integer> minStack = new Stack<Integer>();
    public void push(int node) {
        dataStack.push(node);
        minStack.push(minStack.isEmpty()?node:Math.min(minStack.peek(),node));
    }
    
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

3. 栈的压入弹出序列

题目表述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列 1、2、3、4、5 是某栈的压栈序列，序列 4、5、3、2、1 是该压栈序列对应的一个弹出序列，但 4、3、5、1、2 就不可能是该压栈序列的弹出序列。

解题思路

栈的题目还是借助“辅助栈”。大体思路如下：
1. 入栈序列的元素入栈
2. 检查栈顶元素和弹栈序列元素是否一致

元素一致，弹出栈元素，弹栈序列指针后移
不一致，回到第一步

最后判断栈是否为空。

代码

import java.util.ArrayList;
import java.util.Stack;
public class  {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<Integer>();
        int n = pushA.length;
        for(int pushindex=0,popindex=0;pushindex<n;pushindex++){
            stack.push(pushA[pushindex]);
            while(popindex<n&&!stack.isEmpty()&&stack.peek()==popA[popindex]){
                stack.pop();
                popindex++;
            }
        }
        return stack.isEmpty();
    }
}