`
isiqi
  • 浏览: 15949136 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

(七)抽象数据结构—栈

阅读更多

一、抽象数据结构说明:

1. 栈、队列和优先级队列是比数组和其他数据结构更为抽象的结构。它们主要是作为构思算法的辅助工具,而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短得多。在程序执行期间它们才被创建,通常用他们去执行某项特殊的任务;当完成任务之后他们就被销毁。

2. 此外,它们的访问时受限制的,即在特定的时刻只有一个数据项可以被读取或者被删除。访问其他数据项,理论上是不允许的。栈只允许访问一个数据项,即最后插入的数据项。移除这个数据项后,才能访问倒数第二个插入的数据项,依次类推。

3. 栈的应用非常的广泛:检验源代码中括号的匹配问题、解析表达式、遍历树的节点和查找图的节点等等。

4. 理论上说,ADT定义的栈是不会满的,但是数组实现的栈会满,我们这里用数组来模拟一下栈。

二、Java语言模拟栈:

package com.solid.stack;

public class StackX {

//数组

private long[] stackArray;

//栈顶

int top;

//最大容量

int maxSize;

/**

* 构造方法

* @param maxSize

*/

public StackX(int maxSize) {

this.maxSize = maxSize;

stackArray = new long[maxSize];

top = -1;

}

/**

* 入栈操作

* @param value

*/

public void push(long value) {

stackArray[++top] = value;

}

/**

* 出栈操作

* @return

*/

public long pop() {

return stackArray[top--];

}

/**

* 判断是否为空栈

* @return

*/

public boolean isEmpty() {

return (top == -1);

}

/**

* 读取栈顶元素

* @return

*/

public long peek() {

return stackArray[top];

}

/**

* 判断是否满

* @return

*/

public boolean isFull() {

return (top == maxSize-1);

}

}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics