栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。
2.java代码实现栈
数组实现：
package test;
public class stack {
private int maxSize;// 栈的大小
private int top;
private char[] arr;
public stack(int size) {
maxSize = size;
top = -1;
arr = new char[maxSize];
}
public void push(char value) { // 压入数据
arr[++top] = value;
}
public char pop() { // 弹出数据
return arr[top--];
}
public char peek() { // 访问栈顶元素
return arr[top];
}
public boolean isFull() { // 栈是否满了
return maxSize - 1 == top;
}
public boolean isEmpty() { // 栈是否为空
return top == -1;
}
}
利用栈实现字符串的倒叙输出
package test;
public class Reverse {
String input;
public Reverse(String input) {
this.input = input;
}
public String doReverse() {
stack s = new stack(input.length());
for (int i = 0; i < input.length(); i++) {
s.push(input.charAt(i));
}
String output = "";
while(!s.isEmpty()){
output += s.pop();
}
return output;
}
}
测试：
@Test
public void fun(){
Reverse r=new Reverse("人国中是我");
System.out.println(r.doReverse());
}
链式实现：
package test;
import java.util.LinkedList;
public class stack1 {
private LinkedList<Object> a = new LinkedList<Object>();
public void push(Object o) {
a.addFirst(o);
}
public Object pop() {
return a.removeFirst();
}
public Object peek() {
return a.getFirst();
}
public boolean empty() {
return a.isEmpty();
}
}
下面的示例演示如何通过创建用户定义的push()方法的输入元素和pop()方法用于从堆栈中弹出元素实现堆栈。
public class MyStack {
private int maxSize;
private long[] stackArray;
private int top;
public MyStack(int s) {
maxSize = s;
stackArray = new long[maxSize];
top = -1;
}
public void push(long j) {
stackArray[++top] = j;
}
public long pop() {
return stackArray[top--];
}
public long peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public static void main(String[] args) {
MyStack theStack = new MyStack(10);
theStack.push(10);
theStack.push(20);
theStack.push(30);
theStack.push(40);
theStack.push(50);
while (!theStack.isEmpty()) {
long value = theStack.pop();
System.out.print(value);
System.out.print(" ");
}
System.out.println("");
}
}
| 请您注册登录超级码客，加载全部码客文章内容... |