admin 管理员组文章数量: 1087582
顺序栈结构
栈结构
栈结构是一种线性结构，栈结构包括两类：
1. 顺序栈结构：即使用一组地址连续的内存单元依次保存栈中的数据。在程序中，可以定义一个指定大小的结构数组来作为栈，序号为0的元素就是栈底，再定义一个变量top保存栈顶的序号即可。
2. 链式栈结构：即使用链表形式保存栈中各元素的值。链表首部（head引用所指向元素）为栈顶，链表尾部（指向地址为null）为栈底。
栈结构是按照“后进先出”的原则处理节点数据的。在栈结构中，只有栈顶元素是可以访问的。一般栈结构的基本操作有两个：
1. 入栈（Push）：将数据保存到栈顶的操作。进行入栈操作前，先修改栈顶引用，使其向上移一个元素，然后将数据保存到栈顶引用所指的位置。
2. 出栈（Pop）：将栈顶的数据弹出的操作。先取出栈顶指针所指位置的数据，再通过 修改栈顶引用，使其指向栈中的下一个元素。
准备数据
class DATA{String name;int age;
}/** 顺序栈结构*/
class StackType{ static final int MAXLEN = 50;DATA[] data = new DATA[MAXLEN+1]; // 构建栈结构int top; // 栈顶
}在上述代码中，定义了栈结构的最大长度MAXLEN，栈结构数据元素的类DATA及栈结构的类StackType。在类StackType中，data为数据元素，top为栈顶的序号。当top=0时表示栈为空，当top=SIZE时表示栈满。
Java语言中数组都是从下标0开始的。在这里，为了讲述和理解的方便，从下标1开始记录数据结点，下标0的位置不使用。
初始化栈结构
顺序栈的初始化操作步骤：
1. 按符号常量SIZE指定的大小申请一片内存空间，用来保存栈中的数据。
- 设置栈顶引用的值为0，表示一个空栈。
StackType STInit(){ // 栈的初始化StackType p;if((p=new StackType())!=null){ // 申请栈内存p.top = 0; // 设置栈顶为0return p; // 返回指向栈的引用}return null;
}判断空栈
判断空栈即判断一个栈结构是否为空。如果是空栈，则表示该结构中没有数据。此时可以进行入栈操作，但不可以进行出栈操作。
boolean STIsEmpty(StackType s){ // 判断栈是否为空return s.top==0;
}判断满栈
如果是满栈，则表示该结构中没有多余的空间来保存额外数据。此时不可以进行入栈操作，但是可以进行出栈操作。
boolean STIsFull(StackType s){ // 判断栈是否已满return s.top==MAXLEN;
}清空栈
清空栈即清除栈中的所有数据，在程序中简单地将栈顶引用top设置为0，表示执行清空栈操作。
void STClear(StackType s){ // 清空栈s.top = 0;
}释放空间
释放空间即释放栈结构所占用的内存单元，程序中，直接赋值null操作释放所分配的内存。一般在不需要使用栈结构的时候使用，特别是程序结束时。
void STFree(StackType s){ // 释放栈所占用的空间if(s != null){s = null;}
}入栈
入栈（Push）是栈结构的基本操作，主要操作是将数据元素保存到栈结构。
1. 首先判断栈顶top，如果top大于等于SIZE，则表示溢出，进行出错处理；否则执行以下操作。
2. 设置top=top+1（栈顶引用加1，指向入栈地址）。
3. 将入栈元素保存到top指向的位置。
int PushST(StackType s, DATA data){ // 入栈if(s.top+1 > MAXLEN){System.out.println("栈溢出!\n");return 0;}s.data[++s.top] = data; // 元素入栈，top指针+1return 1;
}出栈
出栈（Pop）是栈结构的基本操作，主要操作与入栈相反，其操作是栈顶弹出一个数据元素。出栈操作的基本步骤如下：
1. 判断栈顶top，如果top等于0，则表示为空栈，进行出错处理；否则，执行下面的步骤。
2. 将栈顶引用top所指位置的元素返回。
3. 设置top=top-1，也就是使栈顶引用减1，指向栈的下一个元素，原来栈顶元素被弹出。
DATA PopST(StackType s){ // 出栈if(s.top==0){System.out.println("栈为空!\n");return null;}return s.data[s.top--]; // 元素出栈，top指针-1
}读结点数据
读结点数据即读取栈结构中结点的数据。由于栈结构只能在一段进行操作，因此这里的读操作其实就是读取栈顶的数据。
需要注意的是，读结点数据的操作和出栈的操作不同。读结点数据的操作仅显示栈顶结点数据的内容，而出栈操作则是将栈顶数据弹出，该数据不再存在了。
DATA PeekST(StackType s){ // 读栈顶数据if(s.top==0){System.out.println("栈为空! 出栈失败!\n");System.exit(0);}return s.data[top];
}栈结构操作实例
package dataStructure.stack;import java.util.Scanner;class DATA{String name;int age;
}/** 顺序栈结构*/
class StackType{ static final int MAXLEN = 50;DATA[] data = new DATA[MAXLEN+1]; // 构建栈结构int top; // 栈顶StackType STInit(){ // 栈的初始化StackType p;if((p=new StackType())!=null){ // 申请栈内存p.top = 0; // 设置栈顶为0return p; // 返回指向栈的引用}return null;}boolean STIsEmpty(StackType s){ // 判断栈是否为空return s.top==0;}boolean STIsFull(StackType s){ // 判断栈是否已满return s.top==MAXLEN;}void STClear(StackType s){ // 清空栈s.top = 0;}void STFree(StackType s){ // 释放栈所占用的空间if(s != null){s = null;}}int PushST(StackType s, DATA data){ // 入栈if(s.top+1 > MAXLEN){System.out.println("栈溢出!\n");return 0;}s.data[++s.top] = data; // 元素入栈，top指针+1return 1;}DATA PopST(StackType s){ // 出栈if(s.top==0){System.out.println("栈为空!\n");return null;}return s.data[s.top--]; // 元素出栈，top指针-1}DATA PeekST(StackType s){ // 读栈顶数据if(s.top==0){System.out.println("栈为空! 出栈失败!\n");System.exit(0);}return s.data[top];}
}/*** 测试用例* @author elon@elon33**/
public class Stack {public static void main(String[] args) {StackType st = new StackType();DATA data1 = new DATA();StackType stack = st.STInit(); // 初始化栈Scanner input = new Scanner(System.in);System.out.println("入栈操作：");System.out.println("输入姓名 年龄进行入栈操作,输入0 结束入栈操作：");do{DATA data = new DATA();data.name = input.next();data.age = input.nextInt();if(data.name.equals("0")){break;}else{st.PushST(stack, data);}}while(true);String temp = "1";System.out.println("出栈操作：按任意非0键进行出栈操作：");temp=input.next();while(!temp.equals("0")){data1=st.PopST(stack);if(data1==null){break;}System.out.println("出栈的数据是："+data1.name+","+data1.age);temp=input.next();}System.out.println("测试结束!");st.STFree(st); // 释放栈所用的空间 }}
本文标签： 顺序栈结构
版权声明：本文标题：顺序栈结构 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700299922a386396.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论