栈的基本概念
是一个只能在某一端进行插入、删除操作的线性表。通常在线性表的尾端，或称栈顶。
由此我们知道栈是一个后进先出（LIFO，Last In First Out）的线性表
从栈顶插入一个元素称之为入栈（push）
从栈顶删除一个元素称之为出栈（pop）
栈的相关操作
因为栈是一个被限制了的线性表，通过索引来插入、删除、访问等操作在栈中是不支持的。
栈的常用操作：
1.入栈：从栈顶插入一个元素
2.出栈：从栈顶删除一个元素
3.访问栈顶元素：访问栈顶的元素，但不删除
4.栈是否为空：判断是否为空
5.栈元素个数：返回栈里的元素个数
6.清空栈：将整个栈清空
入栈、出栈操作示意图
顺序存储实现栈
// 数组模拟栈
public class ArrayStackDemo {
public static void main(String[] args) {
//创建一个数组栈
ArrayStack stack = new ArrayStack(4);
String key="";
boolean loop=true; //控制是否退出菜单
Scanner scanner = new Scanner(System.in);
while (loop){
System.out.println("show:显示栈");
System.out.println("exit 退出程序");
System.out.println("push 入栈");
System.out.println("pop 出栈");
System.out.println("请输入你的选择");
key=scanner.next();
switch (key){
case "show":{
stack.showStack();
break;
}
case "exit":{
//关闭流
scanner.close();
loop=false;
break;
}
case "push":{
System.out.println("请输入你要插入的数据");
int val=scanner.nextInt();
stack.push(val);
break;
}
case "pop":{
try {
//因为出栈时抛出异常了，这里捕获一下比较好
int res=stack.pop();
System.out.println("出栈的数据为"+res);
}catch (Exception e){
System.out.println("异常信息:"+e.getMessage());
}
break;
}
default:{
System.out.println("输入错误,请重新输入");
break;
}
}
}
System.out.println("程序退出了");
}
}
class ArrayStack{
private int maxSize; //栈的大小
private int[] stack; //数组模拟栈，放入数据
private int top=-1; //top表示栈顶，初始化为-1
//初始化栈数据结构的大小
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack=new int[this.maxSize];
}
//栈满
public boolean isFull(){
return top==maxSize-1;
}
//栈空
public boolean isEmpty(){
return top==-1;
}
//入栈
public void push(int data){
if(isFull()){
System.out.println("栈满了");
return ;
}else{
top++;
stack[top]=data;
}
}
//出栈
public int pop(){
if(isEmpty()){
//这里抛出一个运行时异常，程序捕获不捕获都行
throw new RuntimeException("栈空");
}else {
int val=stack[top];
top--;
return val;
}
}
//遍历栈，因为栈只能从栈顶取元素注意需要从栈顶开始遍历
public void showStack(){
if (isEmpty()){
System.out.println("栈空");
return;
}else {
int temp=top;
while(temp>=0){
System.out.println("第"+temp+"个元素为"+stack[temp]);
temp--;
}
}
}
}
代码很简单，代码注释也比较详细，就不赘述了。
链式存储实现栈
public class LinkStackDemo {
public static void main(String[] args) {
//创建一个栈
LinkStack linkStack = new LinkStack();
String key="";
boolean loop=true; //控制是否退出菜单
Scanner scanner = new Scanner(System.in);
while (loop){
System.out.println("show:显示栈");
System.out.println("exit 退出程序");
System.out.println("push 入栈");
System.out.println("pop 出栈");
System.out.println("请输入你的选择");
key=scanner.next();
switch (key){
case "show":{
linkStack.showLinkStack();
break;
}
case "exit":{
//关闭流
scanner.close();
loop=false;
break;
}
case "push":{
System.out.println("请输入你要插入的数据");
int val=scanner.nextInt();
linkStack.push(val);
break;
}
case "pop":{
try {
//因为出栈时抛出异常了，这里捕获一下比较好
int res=linkStack.pop();
System.out.println("出栈的数据为"+res);
}catch (Exception e){
System.out.println("异常信息:"+e.getMessage());
}
break;
}
default:{
System.out.println("输入错误,请重新输入");
break;
}
}
}
System.out.println("程序退出了");
}
}
class LinkStack{
//栈顶，默认为空
private Node top;
//初始化
public LinkStack() {
top=null;
}
//入栈
public void push(int data){
Node node = new Node(data);
//把新节点压栈
node.setNext(top);
//更新新节点为栈顶
top=node;
}
//出栈,出栈和入栈都是在栈顶完成的
public int pop(){
if(top==null){
throw new RuntimeException("栈为空");
}else{
//保存节点信息，同时把栈顶变成当前栈顶的下一个元素
int temp=top.getData();
top=top.getNext();
return temp;
}
}
//栈是否为空
public boolean isEmpty(){
return top==null;
}
//返回栈顶元素
public int getTop(){
if(top==null){
throw new RuntimeException("栈为空");
}else{
return top.getData();
}
}
//遍历栈
public void showLinkStack(){
if(top==null){
System.out.println("栈为空");
}else{
Node temp=top;
while(temp!=null){
System.out.println(temp.getData());
temp=temp.getNext();
}
}
}
}
class Node{
//数据域
private int data;
//指针域
private Node next;
public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}Java Stack 和 LinkedList
Java 中的 Stack 底层是用数组实现的，也就是通过顺序存储的方式实现的 。继承自 Vector 类，所以它是线程安全的的。
我们前面介绍 LinkedList 的说到，java.util.LinkedList 是一个不仅实现了 List 接口，还是实现了 Deque 接口，也就是说 LinkedList 不仅是链式存储的线性表还是一个双端队列。
当然也就可以当做栈来使用，LinkedList 是链式实现的栈，LinkedList 是非线程安全的。在Java中，除了 Stack 和 LinkedList 外，ArrayDeque 也可以作为栈使用，ArrayDeque 和 LinkedList 一样，也是双端队列，一个是基于数组实现的，一个是基于链表实现的。
栈的实践
在计算机中栈的应用非常广泛，比如实现递归计算机需要用栈来存储（关于递归后面会单独用一篇文章来分析）。比如 Android 界面的管理也用栈来实现。下面使用栈来解决几个算法问题。
1.有效的括号
描述如下：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.注意空字符串可被认为是有效字符串。
这个问题通过 Stack 很好解决，先把输入的字符串转化成字符数组， 遍历字符数组，如果当前字符是左括号 '('、'{'、'[' 都push到栈中，如果当前字符是 ‘)’ 则 pop 栈顶元素是否是 ‘)’ ,如果当前字符是 ‘}’ 则 pop 栈顶元素是否是 ‘{’, 如果当前字符是 ‘]’ 则 pop 栈顶元素是否是 ‘[’，具体代码如下：
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] cs = s.toCharArray();
for (Character c : cs) {
switch (c) {
case '(':
case '{':
case '[':
stack.push(c);
break;
case ')':
if (stack.isEmpty() || stack.pop() != '(')
return false;
break;
case '}':
if (stack.isEmpty() || stack.pop() != '{')
return false;
break;
case ']':
if (stack.isEmpty() || stack.pop() != '[')
return false;
break;
}
}
return stack.isEmpty();
}
2.逆波兰计算器
我们完成一个逆波兰计算器，要求完成如下任务:
1) 输入一个表达式：1+（（2+3）*4）-5，使用栈(Stack), 计算其结果，注意需要先把给的中缀表达式转成后缀2) 支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
//使用后缀表达式和栈来完成表达式的计算
public class LastSuffixExpre {
public static void main(String[] args) {
//完成一个中缀表达式转成后缀表达式的功能
//思路分析
// 1：先将中缀字符串转换成list
// 2:将得到的中缀表达式的list变成后缀表达式，然后计算
//
String str="1+((2+3)*4)-5";
System.out.println(toInfixExpressionList(str));//字符串转list
List<String> list = parseSuffixExpList(toInfixExpressionList(str));//转成后缀表达式
System.out.println(str+"="+calculate(list));
}
//将中缀表达式转成List
public static List<String> toInfixExpressionList(String s){
//定义一个List来存储字符串
ArrayList<String> list = new ArrayList<>();
if(s!=null&&s.length()>0){
int i=0;//索引，为了遍历
String str;//拼接多位数
char c;//处理遍历的字符
do{
//如果是符号,直接放入list
if((c=s.charAt(i))<48||(c=s.charAt(i))>57){
list.add(c+"");
i++;//后移
}else {
//如果是数字，则需要判断是否为多位数，然后放入list
//先把str变为"";
str="";
while(i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57){
str+=c;//拼接
i++;//后移遍历
}
list.add(str);
}
}while(i<s.length());
}
return list;
}
//将中缀list变成后缀表达式
public static List<String> parseSuffixExpList(List<String> ls){
//定义两个栈，一个符号栈s1，一个存放中间结果栈s2，
// 由于第二个栈没有出栈操作，而且如果使用的是栈的话得到的
// 结果最后还需要逆序输出，所以这里可以直接使用（队列）或者List
//代替第二个栈.
Stack<String> s1 = new Stack<>();
List<String> s2 = new ArrayList<>();
//遍历list
for (String str:ls) {
//如果是一个数，直接放到s2
if(str.matches("\\d+")){
s2.add(str);
}else{
//如果是符号则需要处理
if(str.equals("(")){
//左括号直接入栈
s1.push(str);
}else if(str.equals(")")){
//如果是右括号，则从符号栈s1依次出栈到s2,直到s1出现左括号,然后丢弃这个左括号
while(!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();//丢弃左括号,实现了消除括号
}else{
//考虑完括号之后需要考虑运算符的优先级（括号不属于运算符）
//如果该运算符的优先级不高于栈顶运算符的优先级，则将栈顶的运算符弹出加入到s2
//!s1.peek().equals("("),这里是为了不比较左括号,因为栈中只可能存在左括号，不可能有右括号
while(s1.size()>0&&(Priority.prio(str)<=Priority.prio(s1.peek()))){
s2.add(s1.pop());
}
//将s1入栈
s1.push(str);
}
}
}
//最后将s1中的运算符依次弹栈加入s2
while (s1.size()>0){
s2.add(s1.pop());
}
return s2;
}
//计算
public static int calculate(List<String> list){
//创建一个栈用于存储字符,这里的栈是java.utils封装的
Stack<String> stack = new Stack<>();
//遍历list
for (String item:list) {
//使用正则表达式匹配多位数
if(item.matches("\\d+")){
//如果是数的话直接入栈
stack.push(item);
}else{
//遇到符号则弹栈计算
int num2=Integer.parseInt(stack.pop());//栈顶
int num1=Integer.parseInt(stack.pop()); //次栈顶
int res=0;
if(item.equals("*")){
res=num1*num2;
}else if(item.equals("/")){
res=num1/num2;
}else if(item.equals("+")){
res=num1+num2;
}else if(item.equals("-")){
res=num1-num2;
}else{
throw new RuntimeException("出错");
}
//把计算结果入栈
stack.push(String.valueOf(res));
}
}
//计算完成之后栈里面只有一个数，就是结果
return Integer.parseInt(stack.pop());
}
}
//定义一个类，用于比较优先级
class Priority{
private static final int ADD=1; //+
private static final int SUB=1; //-
private static final int MUI=2; //乘法
private static final int DIV=2; // 除法
public static int prio(String str){
int result=0;
switch (str){
case "+" :{
result=ADD;
break;
}
case "-" :{
result=SUB;
break;
}
case "*" :{
result=MUI;
break;
}
case "/" :{
result=DIV;
break;
}
default:
System.out.println("不存在该运算符"+str);
break;
}
return result;
}
}3.使用两个栈来实现队列
思路：假设用两个栈来模拟队列，栈是先进后出，队列是先进先出。主要实现队列的入队和出队操作。
入队算法(enQueue)：根据栈的性质，只需将元素全部压到StackA。时间复杂度为O(1)。
出队算法(deQueue)：如果StackB为空，先将StackA的元素全部输出，并压入StackB中。这样元素就正过来了，再将StackB的元素按顺序弹出。如果StackB不为空，则依次弹出StackB的栈顶元素并返回该元素，再添加StackA的元素。如下图所示：
// 使用两个栈来实现队列，让队列可以入队，出队
//思想：栈：先进后出 队列：先进先出
//只需将元素压入栈stackA。然后将stackA中的元素pop出来，push到stackB中。
//stackB栈顶出栈，就可以模拟一个队列。
public class QueueWithTwoStacks {
//这块就不用自定义栈了，使用Stack类
Stack stackA = new Stack();
Stack stackB = new Stack();
//先判断空
public boolean isEmpty(){
if(stackB.isEmpty()){
while (!stackA.isEmpty()){
stackB.push(stackA.pop());
}
}
return stackB.isEmpty();
}
//入队
public void enQueue(Object data){
stackA.push(data);
}
//出队
public Object deQueue(){
if(!stackB.isEmpty()){
return stackB.pop();
}else{
while (!stackA.isEmpty()){
stackB.push(stackA.pop());
}
return stackB.pop();
}
}
public static void main(String[] args) {
QueueWithTwoStacks test = new QueueWithTwoStacks();
test.enQueue(1);//入队四个
test.enQueue(2);
test.enQueue(3);
test.enQueue(4);
System.out.println(test.deQueue());//出队两个
System.out.println(test.deQueue());
}
}4.使用两个队列来实现栈
栈是先进后出的数据结构，所以使用两个队列来模拟栈的思路为：
入栈算法(push)：在任何一个非空队列中插入元素。检查队列A是否为空，如果queueA为空，则对queueB执行入队操作，否则对queueA执行入队操作。通过上述方法模拟入栈操作。
出栈算法(pop)：将n-1个元素移到另一个队列，删除当前队列中的最后一个元素来完成出栈操作。
如果queueA非空，那么从queueA移n-1个元素到queueB中，然后将queueA中最后一个元素出队，并返回该元素，相反也是一样。因为每次调用出栈操作，都需要从一个队列向另一个队列转移元素。如下图所示：
实现代码如下：相比上面的代码，这次将栈内剩余的元素也pop出来。
//定义了一个泛型类
public class StackWithTwoQueue<E> {
Queue<E> queue1 = new LinkedList();
Queue<E> queue2 = new LinkedList();
//添加元素的思路，先让queue1添加元素。添加的元素还没有出栈，又添加元素，往有元素的队列中添加。
public void push(E e) {
//如果队列1为空
if(queue1.isEmpty()){
System.out.println("让队列2添加元素：" + e);
queue2.add(e);
}else{
System.out.println("让队列1添加元素：" + e);
queue1.add(e);
}
}
public E pop() {
int i = 0;
if (queue2.isEmpty()) {//判断队列是否为空
int size = queue1.size();//计算queue1的长度
//然后再把queue1的元素的size-1个元素放到queue2
while (i < size - 1) {
queue2.add(queue1.remove());//queue1出队的元素进入queue2队中
i++;
}
return queue1.remove();//返回queue1内的最后一个元素
} else {//queue2里面有元素，然后也是将size-1的元素放在queue1中
int size = queue2.size();
while (i < size - 1) {
queue1.add(queue2.remove());//思想同上
i++;
}
return queue2.remove();
}
}
public boolean isEmpty(){//boolean = true
//判断栈顶是否为空，删除的时候要判断，要不然可能会异常
if(!queue1.isEmpty()) {//如果queue1不是空
return false; }
else if(!queue2.isEmpty())
return false;
return true;
}
public static void main(String[] args) {
StackWithTwoQueue stackWithTwoQueue = new StackWithTwoQueue();//泛型使用的时候不用写<E>
stackWithTwoQueue.push(1);
stackWithTwoQueue.push(2);
System.out.println(stackWithTwoQueue.pop());
stackWithTwoQueue.push(3);
stackWithTwoQueue.push(4);
System.out.println(stackWithTwoQueue.pop());
System.out.println("输出剩余栈内元素：");
while (!stackWithTwoQueue.isEmpty()){
//输出栈内剩余的元素
int value = (int)stackWithTwoQueue.pop();
System.out.print(value+" ");
}
}
}
全部评论