栈是重要的数据结构,从数据结构角度看,栈也是线性表,其特殊性在栈的基本操作是线性表的子集。Stack作为最基本的数据结构,在JDK代码中,也有它的实现,java.util.Stack类是继承了Vector类,来实现了栈的基本功能。
1.栈的基本原理
栈(Stack)是限定仅在表尾进行插入或者删除操作的线性表。因此,对于栈来说,表尾端有特殊含义,成为栈顶,表头称之为栈底。
由下图可以看出,栈的最基本的特征是LIFO(Last In First Out),因此栈又被称为后进先出 的线性表。
2.栈的基本操作
InitStack(&S)--------------构造一个空栈
IsEmpty:判断栈是否为空
ClearStack:清空栈
StackLength:栈S的元素个数,即栈的长度
GetTop:获取栈顶元素
Push:插入新的元素
Pop:删除栈顶元素
3.java.util.Stack源码解析
1)数据结构:利用Vector(动态数组)完成后进先出的操作
2)基本方法:
//初始化一个长度为10 的数组
构造器 public Stack():
//放入新元素到栈顶
public E push(E item){
//按序更新数组元素(计数器判断最后更新数组元素的索引)
addElement(item);
return item;
}
/**
*1.如果由于新增的元素导致数组的长度不够,则把原来的数组尺寸翻倍,并拷贝老数组元素到新的数组
*2.
*
*
*/
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
//pop栈顶元素
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
4.java.util.stack的缺点
上述源码分析我们知道,Stack利用Vector动态数组实现了后进先出的栈的基本功能,但是数组有下列缺陷:
1)当数组默认的容量发生改变时,push的性能会有较大降低
5.实现自己的Stack类
数组的缺点是,当数组长度发生变化时,原有的元素需要经过copy到新的数组中,这样性能有较大的损耗,而链表最大的优点是插入和删除的性能非常好,Java提供了现成的双向链表类java.util.LinkedList,通过它可以快速编写自己的Stack程序,源码如下:
public class Stack<E>{
LinkedList<E> list;
public Stack(){
list = new LinkedList();
}
public E pop(){
return list.removeLast();
}
public void push(E o){
list.add(o);
}
public E getTop(){
return list.getLast();
}
public boolean isEmpty(){
return list.size()==0;
}
public int size(){
return list.size();
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push("bottom");
stack.push("middle");
stack.push("top");
System.out.println(stack.isEmpty());
System.out.println(stack.getTop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}
1.栈的基本原理
栈(Stack)是限定仅在表尾进行插入或者删除操作的线性表。因此,对于栈来说,表尾端有特殊含义,成为栈顶,表头称之为栈底。
由下图可以看出,栈的最基本的特征是LIFO(Last In First Out),因此栈又被称为后进先出 的线性表。
2.栈的基本操作
InitStack(&S)--------------构造一个空栈
IsEmpty:判断栈是否为空
ClearStack:清空栈
StackLength:栈S的元素个数,即栈的长度
GetTop:获取栈顶元素
Push:插入新的元素
Pop:删除栈顶元素
3.java.util.Stack源码解析
1)数据结构:利用Vector(动态数组)完成后进先出的操作
2)基本方法:
//初始化一个长度为10 的数组
构造器 public Stack():
//放入新元素到栈顶
public E push(E item){
//按序更新数组元素(计数器判断最后更新数组元素的索引)
addElement(item);
return item;
}
/**
*1.如果由于新增的元素导致数组的长度不够,则把原来的数组尺寸翻倍,并拷贝老数组元素到新的数组
*2.
*
*
*/
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
//pop栈顶元素
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
4.java.util.stack的缺点
上述源码分析我们知道,Stack利用Vector动态数组实现了后进先出的栈的基本功能,但是数组有下列缺陷:
1)当数组默认的容量发生改变时,push的性能会有较大降低
5.实现自己的Stack类
数组的缺点是,当数组长度发生变化时,原有的元素需要经过copy到新的数组中,这样性能有较大的损耗,而链表最大的优点是插入和删除的性能非常好,Java提供了现成的双向链表类java.util.LinkedList,通过它可以快速编写自己的Stack程序,源码如下:
public class Stack<E>{
LinkedList<E> list;
public Stack(){
list = new LinkedList();
}
public E pop(){
return list.removeLast();
}
public void push(E o){
list.add(o);
}
public E getTop(){
return list.getLast();
}
public boolean isEmpty(){
return list.size()==0;
}
public int size(){
return list.size();
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push("bottom");
stack.push("middle");
stack.push("top");
System.out.println(stack.isEmpty());
System.out.println(stack.getTop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}
发表评论
-
初学者学习linux
2012-12-19 17:53 657http://wuhaoshu.blog.51cto.com/ ... -
jquery选择器总结
2012-11-21 11:43 9461.<script type="text/ja ... -
外网的压力测试
2012-11-07 10:32 1136外网的压力测试,可以使用apache的ab或curl-load ... -
试着学学object-c
2012-11-05 15:50 7961.http://www.neatstudio.com/sho ... -
java双括弧初始化
2012-10-22 17:39 137501. Map map = new HashMap() {{ ... -
学习java单例模式
2012-10-22 16:16 697http://calmness.iteye.com/blog/ ... -
JsonUtil错误总结
2012-09-26 10:10 1054java.lang.Integer cannot be cas ... -
struts2总结错误
2012-09-25 10:40 7241.数据类型的不对应,一般是,后台要求int而前端的zoneI ... -
Jquery总结
2012-09-18 14:08 0$.toJSON(); $.parseJson(unescap ... -
mysql学习总结
2012-08-23 17:19 8371.<![CDATA[ select ifnull(su ... -
学习强者的成长之路
2012-08-09 10:25 835http://xwnet.blog.51cto.com/233 ... -
MD5正规的写法
2012-07-20 10:26 876public static String getMD5(byt ... -
引用:异常处理!
2012-07-20 09:37 705... -
关于网站的设计
2012-07-19 10:08 740网站的性能优化:http://www.cnblogs.com/ ... -
eval用法
2012-07-12 10:12 877在函数中改变全局变量 var X2={} X2.Eval= ... -
错误总结
2012-07-11 10:38 6361.missing ) in parenthetical错误可 ... -
登录验证struts2
2012-07-09 09:40 738类需要继承ActionSupport,重写execute方法, ... -
学习js的好地方
2012-06-28 13:16 792http://www.zhuoda.org/lunzi/dir ... -
登陆页面
2012-06-26 18:42 976http://themeforest.net/item/dre ... -
学习Session 基类
2012-06-26 16:48 852package com.ruangao.framework.w ...
相关推荐
本篇将深入探讨如何使用C#实现堆栈功能,并揭示其工作原理。 首先,堆栈的基本操作包括入栈(Push)和出栈(Pop)。入栈是指向堆栈顶部添加元素,而出栈则是从顶部移除并返回元素。除此之外,还有查看堆栈顶部元素...
下面将详细解释堆栈的工作原理、主要操作以及如何在Java中实现堆栈。 1. **堆栈工作原理** 堆栈是一种特殊的线性表,只允许在表的一端(栈顶)进行插入和删除操作。栈顶元素是最后加入的,也是最早被移除的,而栈...
Java作为一种广泛使用的编程语言,提供了多种方式来实现堆栈,包括使用数组、链表以及内置的java.util.Stack类。下面我们将详细讨论如何在Java中实现堆栈,并探讨其相关知识。 首先,我们可以通过自定义一个类来...
想象一下图书馆的书架,最后一本书放在最上面,要取出最下面的书必须先移除上面的所有书,这正是堆栈的工作原理。在堆栈中,元素的添加(称为入栈或push)和删除(称为出栈或pop)都是在栈顶进行的。堆栈的主要操作...
1. **堆栈操作指令**:学习并使用汇编语言或高级语言(如C语言)实现堆栈操作,包括压栈和弹栈指令,如PUSH和POP。 2. **子程序调用**:理解如何使用堆栈来保存和恢复函数调用的上下文,包括返回地址和局部变量。在...
首先,堆栈的基本操作包括压栈(Push)、弹栈(Pop)、查看栈顶元素(Peek)以及判断栈是否为空(IsEmpty)。在C#的Stack类中,这些操作都是通过高效且线程安全的方式进行的。接下来,我们逐一分析这些方法。 1. **...
数组是实现堆栈的一种常见方式,因为它的访问效率高且易于理解。在数组中,我们可以设置一个指针(通常称为top)来跟踪堆栈的当前顶端。当进行Push操作时,将元素添加到数组的top位置,并将top加一;对于Pop操作,将...
这个简单的计算器可能只支持基本的四则运算,但对于理解堆栈工作原理和计算逻辑的实现来说,是一个很好的实例。通过扩展,可以增加对括号的支持,处理更复杂的表达式,甚至可以实现一个完整的编译器前端。
总结来说,用堆栈实现表达式的解析是编译原理中一个典型的实例,通过堆栈的特性有效地解决了运算符优先级和操作数匹配的问题,使得数学表达式的解析变得简洁高效。理解和掌握这一方法,对深入理解编译器和解释器的...
在编程领域,括号匹配是一项基础且重要的任务,它涉及到语法...这个练习不仅巩固了C++的基本语法,也加深了对数据结构(尤其是堆栈)的理解,同时还涉及到了文件处理,这对于学习和理解更复杂的编程概念是非常有益的。
- **算法思路**:清晰描述栈和队列的实现原理,以及每一步操作的逻辑。 - **流程图**:可视化地展示算法执行过程,便于理解。 - **源程序**:提供完整的C语言代码实现。 - **算法分析**:对时间复杂度和空间复杂度...
例如,在Python中,可以使用`list`作为堆栈,并利用`append()`和`pop()`方法来实现压栈和弹栈。对于较大的数据集,火车排序可能不是最高效的排序算法,因为其时间复杂度较高,但它的直观性和教育价值使其在教学中...
这篇名为“关于堆栈的论文”的研讨性文章深入探讨了堆栈的基本原理及其广泛应用。在本文中,我们将详细解析堆栈的核心概念、操作、以及它在实际编程和计算中的作用。 堆栈的基本结构可以想象为一个只能在一端进行...
### FPGA堆栈的VHDL实现 ...通过对关键代码的解析,我们不仅了解了堆栈的基本原理,还掌握了如何利用VHDL高效地实现复杂的逻辑控制。这种实现方式不仅可以应用于各种FPGA项目中,还能帮助理解其他类型的数字电路设计。
例如,栈可以用于实现表达式求值、括号匹配、函数调用堆栈、回溯算法等。在括号匹配问题中,我们可以用栈来验证一个数学或编程表达式中的左括号和右括号是否配对正确。每次遇到左括号,就将其压栈;遇到右括号时,...
### 利用堆栈实现逆波兰表达式(后缀法) #### 一、逆波兰表达式简介 逆波兰表达式,又称后缀...通过本文的介绍,我们不仅了解了逆波兰表达式的概念和计算原理,还学习了一种基本的数据结构——顺序表的实现方法。
在本实验中,我们使用数组来实现栈,定义了栈的结构体和基本操作,如InitStack、DestroyStack、ClearStack、StackEmpty、GetTop、Push和Pop等。 其中,InitStack函数用于初始化栈,DestroyStack函数用于销毁栈,...
栈的基本特点是“后进先出”(Last In First Out, LIFO),即最后进入的数据项最先被取出。在实际应用中,栈常用于表达式求值、函数调用堆栈、括号匹配等问题,同时也适用于浏览器的前进后退功能。 #### 栈的典型...
它的基本操作包括压栈(Push)、弹栈(Pop)和查看栈顶元素(Peek)。在解析后缀表达式时,我们首先遍历整个表达式字符串,遇到数字时将其转换为整型或浮点型并压栈,遇到运算符时弹出栈顶的两个元素进行相应的运算...
以上就是单链表、栈和队列的基本概念及C语言实现。理解并熟练掌握这些数据结构对编程能力的提升至关重要,因为它们在各种算法和问题解决中都有着广泛的应用,例如括号匹配、表达式求值、深度优先搜索等。通过实践和...