栈及其Java实现
栈（Stack）又名堆栈，是允许在同一端进行插入和删除操作的特殊线性表，采用先进后出（Last In First Out,LIFO)的数据存储方式，其中，允许进行插入和删除操作的一端叫作栈顶（Top），另一端叫作栈底（Bottom），栈底固定，每次出栈都是将栈顶的数据取出。栈中的元素个数若为0，则将其称为空栈。
入栈如下图所示：
出栈如下图所示：
关于栈应用的提示：
- 在浏览器中存在一个后退的按钮，每次点击后退都是回到上一步的操作，实际上这就是栈的应用，采用的一个先进后出的操作。
- 羽毛球筒就是一个栈，刚开始羽毛球筒是空的，也就是空栈，然后我们一个一个放入羽毛球，也就是一个一个push进栈，当我们需要使用羽毛球的时候，从筒里面拿，也就是pop出栈，但是第一个拿到的羽毛球是我们最后放进去的。
1.Stack类常用的方法
在Java中使用Stack类进行栈的操作，Stack类是Vector的子类。Stack类定义如下：
Stack常用方法如下：public class Stack<E> extends Vector<E> - public boolean empty() //测试栈是否为空
- public E peek() //返回当前栈顶的数据，但不删除
- public E pop() //出栈，同时删除
- public E push(E item) //向栈中压入一个数据，先入栈的数据在最下边
- public int search(Object o)//在栈中查找元素位置，位置从栈顶开始往下算，栈顶为1，依次往下数到所查找元素位置，如果所查找元素在栈中不存在，则返回-1。
2.栈方法具体现实过程
package person.xsc.datamanage;
import java.util.Iterator;
import java.util.Stack;
public class StackDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack<String> s = new Stack<String>();
System.out.println("---------public boolean empty()----------");//测试栈是否为空
if(s.isEmpty()==true) {
System.out.println("这是个空栈！");
}else {
System.out.println("这不是个空栈！");
}
System.out.println("---------public E push(E item)-----------");//向栈中压入一个数据，先入栈的数据在最下边
s.push("A");
s.push("B");
s.push("C");
s.push("D");
s.push("C");
StackDemo.printStack(s);
System.out.println("------------public E pop()---------------");//出栈，同时删除
String str = s.pop();
System.out.println(str);
StackDemo.printStack(s);
System.out.println("------------public E peek()--------------");//返回当前栈顶的数据，但不删除
str = s.peek();
System.out.println(str);
StackDemo.printStack(s);
System.out.println("-------public int search(Object o)-------");//在栈中查找
int i = s.search("A");
if(i!=-1) {
System.out.println("此元素在栈中的位置为："+i);
}else {
System.out.println("栈中没有此元素！");
}
}
public static void printStack(Stack<String> s){
System.out.print("栈元素:");
Iterator<String> it = s.iterator();
while(it.hasNext()){
System.out.print(it.next()+",");
}
System.out.print("\n");
}
}
输出：
---------public boolean empty()----------
这是个空栈！
---------public E push(E item)-----------
栈元素:A,B,C,D,C,
------------public E pop()---------------
C
栈元素:A,B,C,D,
------------public E peek()--------------
D
栈元素:A,B,C,D,
-------public int search(Object o)-------
此元素在栈中的位置为：4
3.利用栈实现字符串逆序
package person.xsc.datamanage;
import java.io.IOException;
public class StackDemo1 {
private static String input="https://www.helloworld.net/"; //反转前字符串
private static String output="";//反转后字符串
public StackDemo1(){} //无参构造
public StackDemo1(String inpu) {//有参构造
input = inpu;
}
public String doStr() {
int stackSize = input.length(); //获取字符串的长度
Stack stack = new Stack(stackSize); //根据字符串长度初始化栈，这里的长度就代表了栈的容量
for (int i = 0; i < input.length(); i++) {//遍历字符串，将字符入栈
char ch = input.charAt(i);
stack.push(ch);
System.out.print(ch+"入栈"+" ");
}
System.out.println("");
while (!stack.isEmpty()) {//判断栈是否为空
char ch = stack.pop(); //字符出栈
System.out.print(ch+"出栈"+" ");
output = output + ch; //字符连接
}
System.out.println("");
return output;
}
class Stack {
private int maxSize; //栈的容量
private char[] data;//定义一个数组，用来存储栈中的数据
private int top;//栈的指针
Stack(int initialSize) {
if(initialSize>=0) {
this.maxSize = initialSize;
data = new char[initialSize];
top = -1;
}else {
throw new RuntimeException("初始化大小不能小于0："+initialSize);
}
}
public void push(char j) {
if(top==maxSize-1) {//栈顶元素的指针从0开始计算
throw new RuntimeException("栈已经满了，无法将元素入栈！");
}else {
data[++top] = j;
}
}
public char pop() {//数据出栈，从栈顶移除一个数据
if(top==-1) {
throw new RuntimeException("栈为空！");
}else {
return data[top--];
}
}
public char peek() {
if(top==-1) {
throw new RuntimeException("栈为空！");
}else {
return data[top];
}
}
public boolean isEmpty() {
return (top == -1);
}
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
StackDemo1 sd = new StackDemo1(input);
output = sd.doStr();//做入栈和出栈操作
System.out.println("反转前： " + input);
System.out.println("反转后： " + output);
}
}
输出：
h入栈 t入栈 t入栈 p入栈 s入栈 :入栈 /入栈 /入栈 w入栈 w入栈 w入栈 .入栈 h入栈 e入栈 l入栈 l入栈 o入栈 w入栈 o入栈 r入栈 l入栈 d入栈 .入栈 n入栈 e入栈 t入栈 /入栈
/出栈 t出栈 e出栈 n出栈 .出栈 d出栈 l出栈 r出栈 o出栈 w出栈 o出栈 l出栈 l出栈 e出栈 h出栈 .出栈 w出栈 w出栈 w出栈 /出栈 /出栈 :出栈 s出栈 p出栈 t出栈 t出栈 h出栈
反转前： https://www.helloworld.net/
反转后： /ten.dlrowolleh.www//:sptth
4.关于Stack的面试问题
- 判断栈的push和pop序列是否一致：一个栈的输入序列为12345，下面哪个不可能是栈的输出序列？（B） A. 23415 B.54132 C.23145 D.15432
- 找出栈中的最小值
package person.xsc.datamanage; import java.util.Stack; public class MinStack { Stack<Integer> mainStack = new Stack<>();//主栈 stackstack Stack<Integer> minStack = new Stack<>();//辅助栈 minStackminStack，用于存放对应主栈不同时期的最小值。 public void push(int element){//入栈操作 mainStack.push(element); //如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈 if(minStack.empty()|| element <= minStack.peek()){ minStack.push(element); } } public Integer pop(){//出栈操作 if(mainStack.peek().equals(minStack.peek())){//如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈 minStack.pop();//辅助栈出栈，同时删除 } return mainStack.pop();//返回主栈栈顶，同时删除 } public int getMin() throws Exception{// 获取栈的最小元素 if(mainStack.empty()==true){ throw new Exception ("空栈 ！"); } return minStack.peek();//返回栈顶元素但不删除 } public static void main(String[] args) { // TODO Auto-generated method stub MinStack mainStack = new MinStack(); mainStack.push(8); mainStack.push(11); mainStack.push(5); mainStack.push(20); try { System.out.println(mainStack.getMin()); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } }
输出：5
