栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶。对栈的操作有进栈(push)和出栈(pop),前者相当于插入,后者则是删除最后插入的元素。最后插入的元素可以通过使用top在执行pop之前进行考查。对空栈进行的pop或top一般被认为是栈的ADT中的错误。
栈有时又叫做LIFO(后进先出)表。如图描述的模型只象征着push是输入操作而pop和top是输出操作。普通的清空栈的操作和判断是否为空栈的测试都是栈的操作指令系统的一部分,只不过我们能做的也基本上就只有push和Pop操作。
由于栈是一个表,因此任何实现表的方法都能实现栈。显然,ArrayList和LinkedList都支持栈的操作。因为栈的操作时常数时间操作,所以除非在非常独特的环境下,这是不可能产生明显改进的。
栈的链表实现
栈的第一种实现方法是使用单链表。通过在表的顶端插入来实现push,通过删除表顶端元素实现pop。top操作只是考察表顶端元素并返回值。有时Pop和top操作合二为一。
package taxus.list;
public interface Stack {
//返回堆栈大小
public int getSize();
//判断堆栈是否为空
public boolean isEmpty();
//元素e入栈
public void push(Object e);
//栈顶元素出栈
public Object pop() throws StackEmptyException;
//获取栈顶元素
public Object peek() throws StackEmptyException;
}
空栈异常类
package taxus.list;
@SuppressWarnings("serial")
public class StackEmptyException extends Exception {
public StackEmptyException(String err){
super(err);
}
}
package taxus.list;
public class StackSLinked implements Stack {
private SLNode top; //链表首节点引用
private int size; //栈大小
public StackSLinked(){
top = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void push(Object e) {
SLNode q = new SLNode(e, top);
top = q;
size++;
}
public Object pop() throws StackEmptyException {
if (size < 1) {
throw new StackEmptyException("Stack empty error");
}
Object o = top.getData();
top = top.getNext();
size--;
return top;
}
public Object peek() throws StackEmptyException {
if (size < 1) {
throw new StackEmptyException("Stack empty error");
}
return top.getData();
}
}
栈的数组实现
另一种实现方法避免的链而且可能是更流行的方式。由于模仿ArrayList的add操作,因此相应的实现方法非常简单。与每个栈相关联的操作时theArray和topOfStack,对于空栈他是-1(这就是空栈初始化做法)。为将某个元素x推入栈中,我们使topOfStack增1然后设置theArray[topOfStack]=x.为了弹出栈元素,我们设置返回值theArray[topOfStack]然后使topOfStack减1.
注意,这些操作不仅以常数时间运行,而且是以非常快的常数时间运行。
package taxus.list;
public class StackArray implements Stack {
private final int LEN = 8; //数组初始大小
private Object[] elements; //存放数据的数组
private int top; //栈顶指针
public StackArray(){
top = -1;
elements = new Object[LEN];
}
//返回堆栈大小
public int getSize() {
return top + 1;
}
//判断堆栈是否为空
public boolean isEmpty() {
return top < 0;
}
//元素e入栈
public void push(Object e) {
if (getSize() >= elements.length) {
expandSpace();
}
elements[++top] = e;
}
private void expandSpace(){
Object[] a = new Object[elements.length * 2];
for (int i = 0; i < elements.length; i++) {
a[i] = elements[i];
}
elements = a;
}
//栈顶元素出栈
public Object pop() throws StackEmptyException {
if (getSize() < 1) {
throw new StackEmptyException("Stack empty error");
}
Object e = elements[top];
elements[top--] = null;
return e;
}
//获取栈顶元素
public Object peek() throws StackEmptyException {
if (getSize() < 1) {
throw new StackEmptyException("Stack empty error");
}
return elements[top];
}
}
- 大小: 37.7 KB
分享到:
相关推荐
数据结构--栈和数组--思维导图.pdf
栈和对列是两种操作特殊的线性表,在实际中应用相当广泛。本实验的目的在于使学生 深入理解栈的特性,熟悉栈的基本操作,以便在实际问题背景下...这种结构的构造方法和掌握其运行过程,了解较复杂问题的递归算法设计。
前面上传了线性表的顺序存储和链式存储,是为了方便学习数据结构的(喜欢用c语言描述版本)的朋友,现在把栈的顺序存储和链式存储上传,希望为同学们提供一个系统的学习数据结构的地方。
数据结构实验报告-栈进制转换.docx
简单的介绍了队列的实现原理,和一些开发中的考量
这份资料里面讲解的很清楚详细,易懂,对正在学习编程的同学特别是对正在找工作的同学非常有帮助。
栈(Stack):具有后进先出(LIFO)特性的数据结构,只允许在栈顶进行插入和删除操作。可以使用数组或链表实现。 队列(Queue):具有先进先出(FIFO)特性的数据结构,允许在队尾插入元素,在队头删除元素。可以...
数据结构-栈十进制转八进制的算法详解(已测试过).doc
PPT内容是数据结构中有关栈和队列的知识,非常适合正在学习数据结构基础的同学
数据结构实验报告-栈和队列.doc
图的遍历 数的搜索 栈和队列 哈希表 排序 数据结构实验指导书
数据结构练习题-第三章-栈、队列和数组-习题及答案.doc
使用C++模版写的简单栈,适用于C++数据结构的学习参考。
编写程序,建立容量为n(建议n=8)的循环队列,完成以下程序功能。输入字符#,执行一次出队操作,屏幕上显示出队字符;输入字符@,队列中所有字符依次出队并按出队次序在屏幕上显示各字符;输入其它字符,则输入的字符...
该代码主要完成数据结构中关于栈的一些操作函数,包括初始化栈,压栈,出栈等操作,本代码还对栈的具体应用给予举例,来完成进制数据之间的转换,包括将十进制数转换为二进制数和八进制数,希望对学习数据结构的同志...
这是我学习 严蔚敏版 《数据结构》(c语言版)时自己写的源代码,都是经过调试的。 通过自己实现这些和调试程序,你会学到很多
通过该题目的设计过程,可以加深理解线性表及栈的逻辑结构、存储结构,掌握线性表及栈上基本运算的实现,进一步理解和熟练掌握课本中所学的各种数据结构,学会如何把学到的知识用于解决实际问题,培养学生的动手能力...
数据结构基础知识:介绍数据结构的基本概念、分类、特点等内容,包括数组、链表、栈、队列、树、图等。 2. Python数据结构:介绍Python中常用的数据结构,包括列表、元组、字典、集合等,以及它们的特点、使用方法...