。

进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。

栈中的数据元素遵守后进先出LIFO#xff08;Last

First

栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶另一端称为栈底。

栈中的数据元素遵守后进先出LIFOLast

First

Stack();stack.push(1);stack.push(2);stack.push(3);stack.push(4);//压栈System.out.println(stack.peek());System.out.println(stack.peek());//没有弹出元素,只是返回了栈顶元素System.out.println(stack.pop());System.out.println(stack.pop());//出栈System.out.println(stack.size());//计算栈中元素的个数System.out.println(stack.empty());//判断栈是否为空//使用Stack从Collection继承下来的方法StackInteger

stack1

Stack();stack1.add(1);stack1.add(2);stack1.add(3);stack1.add(4);//添加元素System.out.println(stack1.isEmpty());//判断是否为空}

}运行结果:

x){ensureCapacity();array[size]

x;size;}public

Arrays.copyOf(array,array.length*2);}}

public

false;//如果在匹配的时候,栈为空,说明右括号赘余}char

ch2

stack.empty();//遍历完了,栈中还有元素,说明左括号赘余}}上述代码逻辑较为复杂,我们通过一张图来理清楚:

2.2

x1*x2;}stack.push(x);//计算之后放回栈中}else

{stack.push(Integer.parseInt(s));//将字符串转化为数字}}return

stack.pop();//最后栈中的值就是最终的值}private

boolean

||s.equals(-)||s.equals(*)||s.equals(/)){return

true;}return

其实我们在电脑中或者是手机上经常用到的计算器就是这样的原理.计算机中的计算器是无法直接识别中缀表达式的,都是先转为后缀表达式,再进行运算的.

2.3

popped[j]){//每放入栈中一个元素,就和popped比较是否相等stack.pop();//如果相等,出栈j;//popped下标向后走}}while

popped.length){//i把push全部遍历完之后,Stack中可能还有元素没有与popped中的匹配完成if

(stack.peek()

popped[j]){stack.pop();j;//继续匹配操作}else

{return

false;//一旦有一个不匹配,说明popped的出栈顺序是错误的}}return

2.4

Stack();//放较小元素,栈顶元素是入stack所有元素中最小的}public

void

(stack1.empty()){//如果最小栈中没有元素,就把第一个元素放入stack1.push(val);}else{if(stack1.peek()

val){//和最小栈的栈顶元素比较大小,stack1的栈顶大于等于val的时候,入栈//等于的时候也要放入,否则pop的时候,最小栈和普通栈会不匹配stack1.push(val);}}}public

void

stack1.peek())){stack1.pop();//两栈元素相等的时候都弹出,否则只弹出普通栈中的元素}}public

int

stack.peek();//返回普通栈栈顶元素}public

int

head){//遇到null的时候往回递归printList(head.next);//没有遇到null的时候,向后递归System.out.print(head.val

);}

将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val

);}

}从上述代码,我们可以得到一个结论,栈可以替代递归思想,在我们后期学习二叉树的时候,在非递归遍历二叉树的时候,我们会频繁地用到栈.