我们都知道，栈的特点是后进先出，先进后出，也就是先进栈里的，最后才能出来。
用数组实现栈的结构
push方法的代码
public boolean isFull(){
//如果top指向最后，则说明栈满
return maxsize-1==top;
}
public void push(int value){
if(isFull()){
System.out.println("栈满，不能在添加元素"+value);
return;
}
//每添加一个元素，指针都要向上移动
stack[++top]=value;
System.out.println("数据"+value+"添加成功");
}
pop方法的代码
public boolean isEmpty(){
return top==-1;
}
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈空");
}
int value=stack[top];
//取出当前的元素之后，还要把指针后移！
top--;
return value;
}
遍历栈中的元素的方法
public void show(){
if(isEmpty()){
System.out.println("栈为空");
}
//遍历时，是要从栈顶开始遍历的。
for(int i=top;i>=0;i--){
System.out.println(stack[i]+"---"+i);
}
}
测试代码
package com.njupt.stack;
/**
* Creat with IntelliJ IDEA
*
* @Auther:倔强的加瓦
* @Date:2021/07/16/9:44
* @Description:
*/
public class StackDemo {
public static void main(String[] args) {
Stack stack = new Stack(10);
for (int i = 1; i <= 8; i++) {
stack.push(i);
}
stack.show();
for (int j = 1; j <= 9; j++) {
System.out.println("第" + j + "次弹栈" + stack.pop());
}
}
}
class Stack {
public int maxsize;
public int top = -1;
public int[] stack;
public Stack(int maxsize) {
this.maxsize = maxsize;
stack = new int[maxsize];
}
public boolean isFull() {
//如果top指向最后，则说明栈满
return maxsize - 1 == top;
}
public boolean isEmpty() {
return top == -1;
}
public void push(int value) {
if (isFull()) {
System.out.println("栈满，不能在添加元素" + value);
return;
}
stack[++top] = value;
System.out.println("数据" + value + "添加成功");
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈空");
}
int value = stack[top];
top--;
return value;
}
//显示栈中的所有元素
public void show() {
if (isEmpty()) {
System.out.println("栈为空");
}
for (int i = top; i >= 0; i--) {
System.out.println(stack[i] + "---" + i);
}
}
}
利用链表实现栈的结构
节点类信息
class Node {
public int no;
public Node next;
public Node(int no) {
this.no = no;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
'}';
}
和数组类似，要始终保证在插入时，一定要把插入的元素放到最前面。取元素后，也要让指针指向下一个节点。
push方法的代码
//判断栈已满
public boolean isFull() {
return maxSize == count();
}
//输出链表中有多少节点
public int count() {
int num = 0;
Node temp = head.next;
while (temp != null) {
num++;
temp = temp.next;
}
return num;
}
public void push(Node node) {
//如果是满的话，则不可以添加
if (isFull()) {
System.out.println("栈已满，不能在加");
return;
}
//如果是空的话，直接加在最后即可
if (isEmpty()) {
head.next = node;
//这里可搞死我了，忘了加一个return，也没有写else语句。。。
return;
} else {
//temp指针始终指向第一个节点
Node temp = head.next;
//先让node指向temp
node.next = temp;
//然后让头节点指向新插入的节点
head.next = node;
System.out.println(node.no + "成功入栈");
}
}
pop出栈方法
//判断为空的方法
public boolean isEmpty() {
return head.next == null;
}
public void pop() {
if (isEmpty()) {
System.out.println("栈已空");
return;
} else {
Node temp = head.next;
if (temp.next != null) {
System.out.println(head.next.no + "出栈");
head.next = temp.next;
} else {
System.out.println(temp.no + "出栈");
head.next = null;
}
}
}
遍历方法
public void show() {
if (isEmpty()) {
System.out.println("链表为空");
return;
}
Node temp = head.next;
while (true) {
System.out.println(temp);
if (temp.next == null) {
break;
}
temp = temp.next;
}
}
测试代码
package com.njupt.stack;
/**
* Creat with IntelliJ IDEA
*
* @Auther:倔强的加瓦
* @Date:2021/07/16/18:11
* @Description:使用链表实现模拟栈的结构
*/
public class ListStackDemo {
public static void main(String[] args) {
ListStack list = new ListStack(9);
for (int i = 1; i <= 10; i++) {
Node node = new Node(i);
list.push(node);
}
System.out.println("=-=====");
list.show();
System.out.println("=-=====");
for (int j = 1; j <= 12; j++) {
list.pop();
}
}
}
//知道啦！用链表的话，就相当于逆序输出。
class ListStack {
public int maxSize;
public Node head = new Node(0);
public ListStack(int maxSize) {
this.maxSize = maxSize;
}
/*public ListStack(Node node){
}*/
public boolean isEmpty() {
return head.next == null;
}
//判断栈已满
public boolean isFull() {
return maxSize == count();
}
//输出链表中有多少节点
public int count() {
int num = 0;
Node temp = head.next;
while (temp != null) {
num++;
temp = temp.next;
}
return num;
}
public void push(Node node) {
//如果是空的话，直接加在最后即可
if (isFull()) {
System.out.println("栈已满，不能在加");
return;
}
if (isEmpty()) {
head.next = node;
System.out.println(node.no+"成功入栈");
} else {
//temp指针始终指向第一个节点
Node temp = head.next;
//先让node指向temp
node.next = temp;
//然后让头节点指向新插入的节点
head.next = node;
System.out.println(node.no + "成功入栈");
}
}
public void pop() {
if (isEmpty()) {
System.out.println("栈已空");
return;
} else {
Node temp = head.next;
if (temp.next != null) {
System.out.println(head.next.no + "出栈");
head.next = temp.next;
} else {
System.out.println(temp.no + "出栈");
head.next = null;
}
}
}
public void show() {
if (isEmpty()) {
System.out.println("链表为空");
return;
}
Node temp = head.next;
while (true) {
System.out.println(temp);
if (temp.next == null) {
break;
}
temp = temp.next;
}
}
}
class Node {
public int no;
public Node next;
public Node(int no) {
this.no = no;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
'}';
}
}
测试结果
1成功入栈
2成功入栈
3成功入栈
4成功入栈
5成功入栈
6成功入栈
7成功入栈
8成功入栈
9成功入栈
栈已满，不能在加
=-=====
Node{no=9}
Node{no=8}
Node{no=7}
Node{no=6}
Node{no=5}
Node{no=4}
Node{no=3}
Node{no=2}
Node{no=1}
=-=====
9出栈
8出栈
7出栈
6出栈
5出栈
4出栈
3出栈
2出栈
1出栈
栈已空
栈已空
栈已空
Process finished with exit code 0