java数组以及单向链表实现栈的push,pop
程序员文章站
2024-02-14 14:22:28
...
提示:以下是本篇文章正文内容,下面案例可供参考
一、栈是什么?
-
栈的英文为(stack)
-
栈是一个先入后出(FILO-First In Last Out)的有序列表。
-
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom)。
-
根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元
素最先删除,最先放入的元素最后删除 -
图解方式说明出栈(pop)和入栈(push)的概念
二、代码实现
1.用数组实现栈
代码如下(示例):
/**
* 数组模拟栈
*/
public class Stack {
int[] array;
int top;
int maxsize;
/**
*
* @param num是数组的长度,也是top的最大指向mxaSize-1
*/
public Stack(int num) {
array=new int[num];
maxsize=num;
top=-1;
}
//因为在push和pop之前都要检查栈是否为空或者为满,所以需要isFull和isEmpety方法
public boolean isFull(){
return top==maxsize-1;
}
public boolean isEmpety(){
return top==-1;
}
/**
* 压栈方法在 压栈之前先判断栈是否为满
* 没满的话栈针上移,赋值
* @param value
*/
public void push(int value){
if (isFull()){
System.out.println("栈已经满了");
return;
}
top++;//栈针上移动
array[top]=value;
}
/**
* 弹栈方法,弹栈前先判断是否为空,
* 不空,取值,将栈针下移,最后返回值
* @return
*/
public int pop(){
if (isEmpety()){
throw new RuntimeException("栈为空");
}
int value=array[top];
top--;
return value;
}
}
2.测试
代码如下(示例):
public class Test {
public static void main(String[] args) {
Stack stack=new Stack(5);
stack.push(5);
stack.push(4);
stack.push(3);
stack.push(2);
stack.push(1);
stack.push(0);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
该处使用的url网络请求的数据。
3用单向链表实现栈
节点类
public class Node1 {
int no;
Node1 next;
public Node1(int no) {
this.no = no;
}
@Override
public String toString() {
return "Node1{" +
"no=" + no +
'}';
}
}
代码实现
/**
* 用单向链表模拟栈
*/
public class NodeStack {
Node1 head;
public NodeStack() {
head=new Node1(0);
}
//同样,判断是否为空的方法,因为单向链表想加多少数据都行,不必写是否为满
public boolean isEpemty(){
return head.next==null;//如果头结点的下一个节点为空说明链表即是栈为空
}
/**
* //添加方法的思路:头插法 每一个新数据的查到head后面
* @param newNode 新节点
*/
public void push(Node1 newNode){
newNode.next=head.next;
head.next=newNode;
}
public Node1 pop(){
if (isEpemty()){
throw new RuntimeException("栈为空");
}
Node1 value=head.next;
head.next=head.next.next;
return value;
}
}
4测试
public class Text1 {
public static void main(String[] args) {
NodeStack nodeStack=new NodeStack();
Node1 n1=new Node1(1);
Node1 n2=new Node1(2);
Node1 n3=new Node1(3);
Node1 n4=new Node1(4);
Node1 n5=new Node1(5);
nodeStack.push(n1);
nodeStack.push(n2);
nodeStack.push(n3);
nodeStack.push(n4);
nodeStack.push(n5);
System.out.println(nodeStack.pop());
System.out.println(nodeStack.pop());
System.out.println(nodeStack.pop());
System.out.println(nodeStack.pop());
System.out.println(nodeStack.pop());
}
}