使用数组和单链表模拟栈的基本操作_只允许在一端插入和删除的线性表允许插入和删除的一端不能称为

一、栈

栈（Stack）是只允许在一端进行插入或删除操作的线性表。线性表允许进行插入删除的一端为栈顶（Top），不允许进行插入和删除的一端为栈底（Bottom）。根据栈的定义可知， 最先放入栈中元素在栈底， 最后放入的元素在栈顶；删除元素刚好相反， 最后放入的元素最先删除， 最先放入的元素最后删除，即栈的特性是先进后出（First In Last Out,FILO）。栈的示意图如下图所示：

入栈的操作示意图如下图所示：

出栈的操作示意图如下图所示：

二、使用数组模拟栈的基本操作

1、基本定义

（1）maxSize：栈的大小（即数组的大小）
（2）arr：模拟栈的数组
（3）top：指向栈顶元素，初始化值为-1
（4）判断栈满：top==maxSize-1（数组索引下标从0开始）
（5）判断栈空：top ==-1
（6）入栈：top++; arr[top]=value;
（7）出栈：int value=stack[top]; top–; return value
（8）输出栈：for (int i = top; i >= 0; i–) 逆序遍历

2、代码实现

package fighting;
import java.util.Scanner;
public class fighting
{
	public static void main(String[] args) 
    {
		ArrayStack stack=new ArrayStack(4);//初始化栈的大小为4
		String key="";
		boolean flag=true;//控制是否退出菜单
		Scanner sc=new Scanner(System.in);
		while(flag) {
			 System.out.println("show: 显示栈");
		     System.out.println("push: 入栈");
		     System.out.println("pop: 出栈");
		     System.out.println("exit: 退出菜单");
		     System.out.println();
		     System.out.println("请输入你的选择");
		     key=sc.next();
		     switch(key) {
		     case "show":
		    	 stack.stack();
		    	 break;
		     case "push":
		    	 System.out.println("请输入入栈的数：");
		    	 int value=sc.nextInt();
		    	 stack.push(value);
		    	 break;
		     case "pop":
		    	 try {
		    		 int res=stack.pop();
		    		 System.out.printf("出栈的数据是 %d\n", res);
		    	 }catch(Exception e) {
		    		 System.out.println(e.getMessage());
		    	 }
		    	 break;
		     case "exit":
		    	 sc.close();//关闭输入流
		    	 flag=false;//修改标志位flag为false，退出菜单
		    	 break;
		     }
		}
    }
}

class ArrayStack{
	private int maxSize;//栈的大小
	private int[] stack;//数组模拟栈
	private int top=-1;//指向栈顶元素，初始化值为-1
	
	//ArrayStack的构造函数
	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 value) {
		if(isFull()) {//入栈前需要判断栈是否已满
			System.out.println("栈已满！");
			return;
		}
		top++;
		stack[top]=value;
	}
	
	//出栈
	public int pop() {
		if(isEmpty()) {//出栈前需要判断栈是否已空
			throw new RuntimeException("栈已空！");
		}
		int value=stack[top];
		top--;
		return value;
	}
	
	//输出栈
	public void stack() {
		if(isEmpty()) {
			System.out.println("栈已空！");
			return;
		}
		
		for(int i=top;i>=0;i--) {//栈的特点是先进后出，即逆序输出
			System.out.printf("stack[%d]=%d\n", i, stack[i]);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

3、运行效果

show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
show
栈已空！
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
1
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
show
stack[0]=1
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
2
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
3
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
4
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
5
栈已满！
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
show
stack[3]=4
stack[2]=3
stack[1]=2
stack[0]=1
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
出栈的数据是 4
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
出栈的数据是 3
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
出栈的数据是 2
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
出栈的数据是 1
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
栈已空！
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
show
栈已空！
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
exit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

三、使用单链表模拟栈的基本操作

1、基本定义

（1）maxSize：栈的大小（即单链表的大小）
（2）numCount：栈内元素个数
（3）top：指向栈顶元素
（4）判断栈满：maxSize == numCount
（5）判断栈空：tnumCount == 0
（6）入栈：top = new Node(value, top);
numCount++;
（7）出栈： int value = top.getNum(); top = top.next; numCount–;return value

2、代码实现

package fighting;
import java.util.Scanner;
public class fighting{
	public static void main(String[] args) {
		LinkedListStack stack=new LinkedListStack(4);//初始化单链表长度为4
		String key= "";
		boolean flag=true;//控制是否退出菜单
		Scanner sc=new Scanner(System.in);
		while(flag) {
			 System.out.println("show: 显示栈");
		     System.out.println("push: 入栈");
		     System.out.println("pop: 出栈");
		     System.out.println("exit: 退出菜单");
		     System.out.println();
		     System.out.println("请输入你的选择");
		     key=sc.next();
		     switch(key) {
		     case "show":
		    	 stack.list();
		    	 break;
		     case "push":
		    	 System.out.println("请输入入栈的数：");
		    	 int value=sc.nextInt();
		    	 stack.push(value);
		    	 break;
		     case "pop":
		    	 try {
		    		 Object res=stack.pop();
		    		 System.out.printf("出栈的数据是 %d\n", res);
		    	 }catch(Exception e) {
		    		 System.out.println(e.getMessage());
		    	 }
		    	 break;
		     case "exit":
		    	 sc.close();//关闭输入流
		    	 flag=false;//修改标志位flag为false，退出菜单
		    	 break;
		}
    }
  }
}

class LinkedListStack{
	private int maxSize;//栈大小
	private int numCount;//栈内元素个数
	private Node top;//栈顶元素
	
	//LinkedListStack的构造函数
	public LinkedListStack(int maxSize) {
		this.maxSize=maxSize;
		numCount=0;
		top=null;
	}
	
	//判断栈空
	public boolean isEmpty(){
        return numCount == 0;
    }
	
	//判断栈满
	public boolean isFull(){
        return maxSize == numCount;
    }
	
	//入栈
	public void push(int value){
        if (isFull()){
            System.out.println("栈已满！");
            return;
        }
        top = new Node(value, top);
        numCount++;
    }
	
	//出栈
	public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈已空！");
        }
        int value = top.getData(); //获取栈顶元素
        top = top.getNext(); //指针后移
        numCount--;
        return value;
    }
	
	//输出栈
	public void list(){
        if (isEmpty()){
            System.out.println("栈已空！");
            return;
        }

        Node temp = top; //辅助变量，用来遍历链表
        while (temp.getNext() != null){
            if (temp.getNext() == null){
                break;
            }
            System.out.println(temp);
            temp = temp.getNext(); //指针后移
        }
        // 当链表中只有一个元素时，不需要循环，直接输出
        System.out.println(temp);
    }
}

class Node{//单链表的结点
	private int data;//数据域存放数据
	private Node next;//指域指向下一个结点
	//ListStack的构造函数
	public Node(int data,Node next) {
		this.data=data;
		this.next=next;
	}
    //data和next的getter和setter方法
	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;
	}
	
	@Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

3、运行效果

show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
show
栈已空！
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
1
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
2
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
3
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
4
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
push
请输入入栈的数：
5
栈已满！
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
show
Node{data=4}
Node{data=3}
Node{data=2}
Node{data=1}
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
出栈的数据是 4
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
出栈的数据是 3
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
出栈的数据是 2
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
出栈的数据是 1
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
pop
栈已空！
show: 显示栈
push: 入栈
pop: 出栈
exit: 退出菜单

请输入你的选择
exit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112