1 栈的多种存储结构以及实现
栈有两种实现方式一种是顺序存储结构、还有一种是链式存储结构。这两种存储结构对应两种存储的数据结构：数组和链表。数组和链表的相关内容可以参考本文其他章节的内容。
1.1 栈的顺序存储结构
前面我们说了栈是数据结构中线性表的特殊存在，所以栈的顺序存储方式也就是线性表的顺序存储的方式，也就是我们接下来要讲的顺序栈，因此顺序栈的实现形式也就是线性表顺序存储的实现形式-数组。因为栈底的变化最小，所以将数组下标为 0 的一端作为栈底，同时还要定义一个变量，用来表示栈顶元素在数组中的位置。
1.2 顺序栈的各类功能实现
/*
@author youDaily
*/
//属性定义和构造函数
public class SortStack {
public Object[] data; // 数组表示栈内元素
public int maxSize; // 栈空间大小
public int top; // 栈顶指针(指向栈顶元素)
//初始化栈的长度
public SortStack(int initialSize){
if(initialSize>=0){
this.data=new Object[initialSize];
this.maxSize=initialSize;
this.top=-1;
}
else{
System.out.println("栈初始化失败!");
}
}
//判断栈是否为空
public boolean isEmpty(){
return top == -1 ? true : false;
}
//判断是否栈满
public boolean isFull(){
return top == maxSize-1 ? true : false;
}
//入栈
public void push(Object value){
if(!isFull()){
System.out.print(value+"入栈 ");
data[++top]=value;
}
else{
System.out.println("满栈，无法进行入栈操作!");
}
}
/**
*
* 先判断是否为空栈
* @return
*/
//元素出栈
public Object pop(){
Object num=null;
if(!isEmpty()){
num = data[top--];
return num;
}
else{
return "空栈，无法进行出栈操作!";
}
}
// 获取栈顶元素
public Object getPeek(){
if(top>=0){
return data[top];
}
else{
return "栈顶指针为空，无栈顶元素!";
}
}
//遍历栈内元素
public void displayStack(){
// 栈顶指针不为—1，栈内有元素，进行打印
if(top>=0){
for(int i=top;i>=0;i--){
System.out.print(data[i] + " ");
}
System.out.println();
}
else{
System.out.println("栈内元素为空！");
}
}
//获取栈顶指针为 n 的栈内元素
public Object getPeekN(int n){
if(n<top){
return data[n];
}
else{
return "error";
}
}
}
1.3 栈的链式存储结构
栈的链式结构是通过链表连接起来的。好了，我们现在再回忆一下栈的结构，栈是先进后出，所有的操作都在栈顶完成，包括插入和删除，所以要考虑一下讲栈顶放在整个链表的头部还是尾部。因为链表具体头结点，因此可以考虑将栈顶和头结点结合。我们将栈顶的元素放在一条链表的头部。所以通常来说，对于栈链来说，是不需要头结点的。
链式栈.png
而从计算机内存的角度看栈链，基本不存在栈满的情况，除非内存没有了可以使用的空间。更直观地解释栈链与数组栈之间的区别就是，一个是充分利用内存中的零碎空间，还有一个是占据内存中的大块空间。
1.4 栈链的各类功能实现
/*
@author youDaily
*/
//属性定义和构造函数
class InitStack{
private int [] data = new int[1]; //存储元素值
private InitStack nextStack; //存储下一地址
public InitStack() { //用于生成头结点
this.data = null;
this.nextStack = null;
}
public InitStack(int data) { //用于生成链栈结点
this.data[0] = data;
this.nextStack = null;
}
}
//清空栈链
public void clearStack() {
this.nextStack = null; //令头结点的下一地址为空，链栈即被清空
}
// 检查栈链是否为空
public int stackLength() {
InitStack theStack = this.nextStack; //获取头结点的下一地址即链栈的第一个结点
int i = 0; //初始化计数器
for (i = 0; theStack != null; i++) { //循环判断如不为空，则计数器加一
theStack = theStack.nextStack;
}
return i;
}
// 获取栈顶元素
public int [] getTop() {
if(this.nextStack == null) { //判断是否为空栈
return null;
}
return this.nextStack.data;
}
// 进行压栈
public void push(int input) {
InitStack initStack = new InitStack(input);
initStack.nextStack = this.nextStack;
this.nextStack = initStack;
}
//元素出栈
public int [] pop() {
if (this.nextStack == null) { //判断栈是否为空
return null;
}
int [] i = this.nextStack.data; //获取栈顶元素值
this.nextStack = this.nextStack.nextStack; //删除栈顶元素
return i;
}
//栈顶到栈底遍历栈
public String stackTraverse() { //这里通过输出栈元素值来表示遍历
InitStack theStack = this.nextStack;
String s = "";
while(theStack != null) { //循环遍历栈
s = theStack.data[0] + "、" + s;
theStack = theStack.nextStack;
}
if(s.length() == 0) { //如果未获得值，则直接输出空字符串
return s;
}
return s.substring(0,s.length() - 1); //除去最后的顿号后返回字符串
2 队列的多种存储结构以及实现
和栈一样，队列也有两种实现的方式，顺序队列和链式队列。其中顺序队列中需要注意所谓的“溢出”问题。在接下来的内容中，我将详细讲述。
网友评论