本文转自:疯狂Java 突破程序员基本功的16课
顺序存储结构的栈简称为顺序栈,它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈底位置固定不变,它的栈顶元素可以直接通过顺序栈底层数组的数组元素arr[size-1]来访问。
1.进栈
对于顺序栈的进栈操作而言,只需将新的数据元素存入栈内,然后再让记录栈内元素个数的变量+1,程序即可再次通过arr[size-1]重新访问新的栈顶元素。
由于顺序栈底层通常采用数组来保存数组元素,因此可能出现的情况是:当程序试图让一个数据元素进栈时,底层数组已满,那么就必须扩充底层数组的长度来容纳新进栈的数据元素。
2.出栈
对于顺序栈的出栈操作而言,需要将栈顶元素弹出栈,程序要做两件事情:
(1) 让记录栈内元素个数的变量-1
(2) 释放数组对栈顶元素的引用
对于删除操作来说,只要让记录栈内元素个数的size减少1,程序即可通过arr[size-1]访问到新的栈顶元素。但不要忘记释放原来栈顶元素的数组引用,否则会引起内存泄露。
SequenceStack.javapackage com.syc.crazejava.chapter10;
import java.util.Arrays;
public class SequenceStack<T> {
private int DEFAULT_SIZE = 10;
// 保存数组的长度
private int capacity;
// 定义当底层数组容量不够时,程序每次增加的数组长度
private int capacityIncrement = 0;
// 定义一个数组用于保存顺序栈的元素
private Object[] elementData;
// 保存顺序栈中元素的当前个数
private int size = 0;
// 以默认数组长度创建空顺序栈
public SequenceStack(){
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
// 以一个初始化元素来创建顺序栈
public SequenceStack(T element){
this();
elementData[0] = element;
size ++;
}
/**
* 以指定长度的数组来创建顺序栈
* @param element 指定顺序栈中第一个元素
* @param initSize 指定顺序栈底层数组的长度
*/
public SequenceStack(T element,int initSize){
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
size ++;
}
/**
* 以指定长度的数组来创建顺序栈
* @param element
* @param initSize
* @param capacityIncrement
*/
public SequenceStack(T element,int initSize,int capacityIncrement){
this.capacity = initSize;
this.capacityIncrement = capacityIncrement;
elementData = new Object[capacity];
elementData[0] = element;
size ++;
}
// 获取顺序栈的大小
public int length(){
return size;
}
// 入栈
public void push(T element){
ensureCapacity(size + 1);
elementData[size++] = element;
}
// 很麻烦,而且性能很差
private void ensureCapacity(int minCapacity){
// 如果数组的原有长度小于目前所需的长度
if(minCapacity > capacity){
if(capacityIncrement > 0){
while(capacity < minCapacity){
// 不断地将capacity长度加capacityIncrement
// 直到capacity大于minCapacity为止
capacity += capacityIncrement;
}
}else{
// 不断地将capacity*2,直到capacity大于minCapacity为止
while(capacity < minCapacity){
capacity <<= 1;
}
}
}
elementData = Arrays.copyOf(elementData, capacity);
}
// 出栈
@SuppressWarnings("unchecked")
public T pop(){
T oldValue = (T) elementData[size - 1];
// 释放栈顶元素
elementData[--size] = null;
return oldValue;
}
// 返回栈顶元素,但不删除栈顶元素
@SuppressWarnings("unchecked")
public T peek(){
return (T) elementData[size - 1];
}
// 判断顺序栈是否为空栈
public boolean empty(){
return size ==0;
}
// 清空顺序栈
public void clear(){
// 将底层数组所有元素赋为null
Arrays.fill(elementData, null);
size = 0;
}
public String toString(){
if(size == 0){
return "[]";
}else{
StringBuilder sb = new StringBuilder("[");
for(int i = size - 1;i > -1; i--){
sb.append(elementData[i].toString() + ",");
}
int len = sb.length();
return sb.delete(len - 1, len).append("]").toString();
}
}
}
SequenceStackTest.java
package com.syc.crazejava.chapter10;
public class SequenceStatckTest {
/**
* @param args
*/
public static void main(String[] args) {
SequenceStack<String> stack = new SequenceStack<String>();
// 不断地入栈
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
stack.push("ddd");
// 访问栈顶元素
System.out.println("访问栈顶元素:"+stack.peek());
// 弹出一个元素
System.out.println("第一次弹出栈顶元素:"+stack.pop());
// 再次弹出一个元素
System.out.println("第二次弹出栈顶元素:"+stack.pop());
System.out.println("两次pop之后的栈:"+stack);
}
}
引用
访问栈顶元素:ddd
第一次弹出栈顶元素:ddd
第二次弹出栈顶元素:ccc
两次pop之后的栈:[bbb,aaa]
分享到:
相关推荐
数据结构栈顺序存储结构
这是数据结构中关于栈这个知识点的一个顺序存储实验的演示,是使用C++实现的,希望能够对学习数据结构中的关于栈的朋友有用。
实验目的 掌握栈的顺序存储结构; 验证栈的操作特性; 掌握栈的基本操作实现方法。 2. 实验内容 建立含有若干个元素的顺序栈; 对已建立的顺序栈实现入栈、出栈、判栈空和判栈满等基本操作。 3.设计与编码 #include...
数据结构-栈的顺序存储,进栈、出栈、取栈顶元素、判断栈是否为空、置空、 结束
二、栈和队列的顺序存储结构在教材中,我们给出了栈的链表存储结构和队列的链表存储结构及实现,下面给出的是栈的顺序存储结构及实现和队列的顺序存储结构及实现。1.栈的顺序存储结构及实现C++语言源程序。//--------...
栈的顺序存储即顺序栈是指,用一块连续的内存来存放一个栈,类似于数组,各元素在内存中是一个挨一个的。既然栈也是线性表,那么栈就可以通过线性表来实现,实现顺序栈只需在顺序表的插入删除操作时,只限定在一端...
数据结构用栈实现十进制到十六进制的数据转换, 数据结构用栈实现十进制到十六进制的数据转换。
编写函数,采用顺序存储实现栈的初始化、入栈、出栈操作。【实验要求】 1、数据要求 顺序表中的数据是图书信息(书号、书名、价格)。 2、输入要求 输入n+1行,其中前n行是n本图书的信息(书号、书名、价格),每本...
该代码实现了栈的顺序存储,包括创建栈、删除栈、清空栈、插入元素、删除元素等API函数
2.采用顺序存储实现栈的初始化、入栈、出栈操作 #include using namespace std; class sqstack { private: int top; int maxsize; int *elem; public: sqstack(int size) {maxsize=size; elem=new int...
(1) 熟悉栈的特点(先进后出)及栈的基本操作,如入栈、出栈等,掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现; (2) 熟悉队列的特点(先进先出)及队列的基本操作,如入队、出队等,掌握队列的...
需另设一个栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车,包含两个数据项:汽车的牌照号码和进入停车场的时刻。
9.定义并实现循环队列的数据结构。 10.应用队列完成Johnson问题(n个人围成一圈,每个人都有一个号码,从1..n,从1号报数,报到m号的出列,输出出列的号码顺序)。测试:10个人,报到3的出列。
数据结构中的重要基本的顺序存储表示,另外还有链式结构的实现方式,我会陆续上传
数据结构 -- C语言版 -- 栈的部分实现代码(栈的实现、栈的应用),详细介绍参考数据结构--栈的系列博文。链接为:https://blog.csdn.net/songshuai0223/category_9742561.html。
1、理解栈的逻辑结构定义及特点、掌握栈的存储结构的描述、 实现栈的基本运算。 2、理解队列的逻辑结构定义及特点、掌握循环队列存储结构及其描述方法、掌握循环队列的基本运算。 二、实验内容: 1、建立顺序栈,并...
用C语言实现了栈和队列的数据结构形式,其中包括栈和队列的初始化,压栈弹栈,进队出堆。和一些其他的基本操作!
实现基于顺序表的顺序栈(数据结构定义+基本运算) 设计算法判断一个算术表达式的圆括号是否正确配对。 第一个式子: 1*(2+3*(4*(2-1)*(3+x)+5)-6) 能够正确匹配 第二个式子: 1*(2+3*4*(2-1)*(3+x)+5)-6) 不...
2. 栈的顺序存储表示表示和实现 (1)顺序栈动态分配存储空间方法 和对栈操作设计 (2)顺序栈静态分配存储空间方法 和对栈操作设计 * 3. 栈的链式存储结构——链栈 顺序栈静态分配存储空间方法 和对栈操作设计
总的来说,通过这两次的上机实验练习,我的收获比较多,基本上掌握了队和栈的基本知识,达到了实验要求的目的。