栈
栈的介绍
图解栈
数组实现栈
链表实现栈
栈的介绍:
??栈(stack)，是一种先入后出的有序列表，它限制了线性表中对元素的插入和删除只能在线性表的同一端进行，允许插入和删除的一端为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom).
??根据上面的定义可知，元素每次入栈时都会从栈顶入栈，最先入栈的元素会被存放在栈底，最后入栈的元素在栈顶；而出栈时的情况与入栈相反，最先入栈的元素最后一个出栈，最后入栈的元素第一个出栈，这也就是所谓的先入后出。
图解栈:
??从图上可以看到，每入栈一个元素，栈顶指针向上移动一次，栈底指针不变；每出栈一个元素，栈顶指针向下移动一次，栈底指针不变。
数组实现栈:
class Stack{
private int[] stack;
private int maxSize;
private int top = -1;//栈顶
public Stack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
//判断栈是否满
public boolean isFull(){
return top==maxSize-1;
}
//判断栈是否为空
public boolean isEmpty(){
return top==-1;
}
//向栈中添加元素
public void push(int val){
stack[++top] = val;
}
//第一个元素出栈
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈为空!");
}
int val = stack[top--];
return val;
}
//由栈顶到栈底打印栈内所有元素
public void show(){
if (isEmpty()){
System.out.println("栈为空!");
}
for(int i=top;i>-1;--i){
System.out.print(stack[i]+" ");
}
System.out.println();
}
}
public class Test {
public static void main(String[] args) {
System.out.println("请输入栈的最大容量:");
Scanner scanner = new Scanner(System.in);
Stack stack = new Stack(scanner.nextInt());
//创建菜单
while (true){
System.out.println("1. 添加元素");
System.out.println("2. 第一个元素出栈");
System.out.println("3. 打印栈");
System.out.println("4. 栈判空");
System.out.println("5. 栈判满");
System.out.println("0. 退出系统");
switch (scanner.nextInt()){
case 1:
if(stack.isFull()){
System.out.println("栈已满!");
}
else {
System.out.println("请输入需要添加的元素:");
stack.push(scanner.nextInt());
System.out.println("添加成功!");
}
break;
case 2:
try {
int val = stack.pop();
System.out.println("出栈元素为"+val);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 3:
stack.show();
break;
case 4:
if (stack.isEmpty()){
System.out.println("栈为空!");
}
else {
System.out.println("栈不为空!");
}
break;
case 5:
if (stack.isFull()){
System.out.println("栈为空!");
}
else {
System.out.println("栈不为空!");
}
break;
default:
System.exit(0);
}
}
}
}
链表实现栈:
//定义链表节点
class Node{
private int data;
public Node next;
//创建构造器
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public Node(int data) {
this.data = data;
}
//提供节点值的get和set方法
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
//定义栈类型
class Stack{
private Node bottom;//栈底，默认为null
private Node top;//栈顶，默认为null
private int maxSize;//栈的最大容量
//创建构造器
public Stack(int maxSize) {
this.maxSize = maxSize;
}
//判断栈是否满
public boolean isFull(){
Node cur = bottom;
int count = 0;
while (cur!=null){
++count;
cur = cur.next;
}
return count==maxSize;
}
//判断栈是否为空
public boolean isEmpty(){
return top==null;
}
//元素入栈
public void push (int val) {
Node node = new Node(val);
if(bottom==null){
node.next = bottom;
bottom = node;
top = node;
}
else {
top.next = node;
top = node;
}
}
//栈顶元素出栈
public int pop(){
if (isEmpty()) {
throw new RuntimeException("栈为空，无法出栈!");
}
Node cur = bottom;
int val;
if(cur.next==null){
bottom = null;
top = null;
return cur.getData();
}
while (cur.next.next!=null){
cur = cur.next;
}
val = cur.next.getData();
cur.next = null;
return val;
}
//由top向bottom打印栈内元素
public void show(){
if(isEmpty()){
System.out.println("栈为空，无法打印!");
return;
}
Node head = null;
Node cur = bottom;
while (cur!=null){
Node node1 = new Node(cur.getData());
node1.next = head;
head = node1;
cur = cur.next;
}
cur = head;
while (cur!=null){
System.out.print(cur.getData()+" ");
cur = cur.next;
}
System.out.println();
}
//打印栈顶元素
public void head(){
if(isEmpty()){
System.out.println("栈为空，无法打印!");
return;
}
System.out.println("栈顶元素为"+top.getData());
}
}
public class Test {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入栈的大小:");
Stack stack = new Stack(scanner.nextInt());
boolean loop = true;
//创建菜单
while (loop) {
System.out.println("1. 元素入栈");
System.out.println("2. 栈顶元素出栈");
System.out.println("3. 由栈顶向栈底打印栈内元素");
System.out.println("1. 打印栈顶元素");
System.out.println("0. 退出系统");
switch (scanner.nextInt()){
case 1:
if(stack.isFull()) {
System.out.println("栈已满，无法入栈!");
}
else {
System.out.println("请输入要入栈的元素:");
stack.push(scanner.nextInt());
System.out.print("入栈成功，当前栈内元素为:");
stack.show();
}
break;
case 2:
try {
int val = stack.pop();
System.out.println("出栈元素为"+val);
}catch (Exception e){
System.out.println(e.getMessage());
}break;
case 3:
stack.show();
break;
case 4:
stack.head();
break;
default:
loop = false;
}
}
}
}
The end