系统中的堆、栈和数据结构堆、栈不是一个概念。可以说系统中的堆、栈是真实的内存物理区，数据结构中的堆、栈是抽象的数据存储结构。
栈：实际上就是满足后进先出的性质，是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。
栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。
代码：
Stack的基本使用
初始化
Stack stack=new Stack
判断是否为空
stack.empty()
取栈顶值（不出栈）
stack.peek()
进栈
stack.push(Object);
出栈
stack.pop();
实例：
public class Test01 {
public static void main(String[] args) {
Stack stack=new Stack();
//1.empty()栈是否为空
System.out.println(stack.empty());
//2.peek()栈顶值 3.进栈push()
stack.push(new Integer(1));
stack.push("b");
System.out.println(stack.peek());
//4.pop()出栈
stack.pop();
System.out.println(stack.peek());
}
}
栈的主要操作
栈的辅助操作
实现
栈抽象数据类型有多种实现方式。下面是常用的方法：
1）基于简单数组实现：
public class Stack{
private int size;//栈的大小
private int top;//栈顶元素的下标
private char[] stackArray;//栈的容器
public Stack(int size){
stackArray = new char[size];
top = -1; //初始化栈的时候由于栈内没有元素，栈顶下标设为-1
this.size = size;
}
//入栈,栈顶的下标+1
public void push(char item){
stackArray[++top] = item;
}
//出栈，删除栈顶元素，栈顶元素的下标-1
public int pop(){
return stackArray[top--];
}
//查看栈顶元素，不删除
public char find(){
return stackArray[top];
}
//判空
public boolean isEmpty(){
return (top == -1);
}
//判满
public boolean isFull(){
return (top == size - 1);
}
public static void main(String[] args){
Stack stack = new Stack(5);
stack.push('a');
stack.push('b');
stack.push('c');
stack.push('d');
char ch = stack.find();
System.out.println(ch);
}
}
运行结果：
d
2）基于动态数组实现：
扩容——给我的感觉就像是在搬家，搬完了东西，还得把钥匙给主人
public class Stack {
public int size;//栈的大小
public int top;//栈顶元素的下标
public static char[] stackArray;//栈的容器
public Stack(int size){
stackArray = new char[size];
top = -1; //初始化栈的时候由于栈内没有元素，栈顶下标设为-1
this.size = size;
}
//入栈,栈顶的下标+1
public void push(char item){
if(isFull()){
doubleStack();
}
stackArray[++top] = item;
}
//模拟数组的扩容
public void doubleStack(){
char[] newStackArray = new char[size*2];
for(int i = 0;i<size;i++){
newStackArray[i] = stackArray[i];
}
size = size*2;
stackArray = newStackArray;
}
//出栈，删除栈顶元素，栈顶元素的下标-1
public int pop(){
if(isEmpty()){
System.out.println("Stack is Empty");
return 0;
}else{
return stackArray[top--];
}
}
//查看栈顶元素，不删除
public char find(){
return stackArray[top];
}
//判空
public boolean isEmpty(){
return (top == -1);
}
//判满
public boolean isFull(){
return (top == size - 1);
}
public static void main(String[] args){
Stack stack = new Stack(5);
stack.push('a');
stack.push('b');
stack.push('c');
stack.push('d');
stack.push('e');
stack.push('f');
stack.push('g');
stack.push('h');//一共8个元素
char ch = stack.find();
System.out.println(ch);
System.out.println(stackArray.length);
}
}
运行结果：
h
10
3）基于链表实现
使用链表实现栈，通过在链表的表头插入元素的方式实现push操作，删除链表的表头结点实现pop操作。表头结点即栈顶结点
import java.util.EmptyStackException;
class Link{
public char data;
public Link next;
public void show(){
System.out.println(data + " ");
}
public Link(char data){
this.data = data;
}
}
public class Stack2 {
Link head;
public int size;//栈的大小
public int top;//栈顶元素的下标
public static char[] stackArray;//栈的容器
public void push(char data){
if(head == null){
head = new Link(data);
}else{
Link node = new Link(data);
node.next = head;
head = node;
}
}
public void pop(){
if(head == null){
throw new EmptyStackException();
}else{
char dat = head.data;
head.show();
head = head.next;
}
}
public int top(){
if(head == null){
return 0;
}else{
return head.data;
}
}
public boolean isEmpty(){
if(head == null) return true;
return false;
}
public static void main(String[] args){
Stack2 stack = new Stack2();
stack.push('A');
stack.push('B');
stack.push('C');
stack.push('D');
stack.push('E');
stack.push('F');
stack.pop();
}
}
运行结果：
F
