关键词:
1.定义
栈是仅限定在表尾进行插入和删除操作的线性表。允许进行插入和删除的一端称为栈顶(也叫表尾),另一端为栈底。栈又称为后进先出的线性表。由于栈本身是一个线性表,所以线性表的顺序存储结构和链式存储结构对于栈来说,同样是适用的。
2.栈的顺序存储结构
栈的顺序存储结构又称为顺序栈,线性表是用数组来实现的,而栈也是线性表,所以我们使用数组来实现栈。
2.1 栈的顺序存储结构实现
由于栈顶进行数据的插入和删除操作,而栈底变化不大,所以使用数组下标为0的一端作为栈底比较好。我们定义一个top变量指向栈顶元素在数组中的位置,还必须指明栈的长度StackSize,top变量需小于栈的长度。
代码实现:
class LineStack //空栈的判定条件为top=-1 int top=-1; static int maxSize=8; static Object[] array=new Object[maxSize]; public LineStack()
2.2 进栈操作
算法思路:
1. 首先判断top指针与栈长度的大小,top指针的最大值为栈长减1;
2. 进栈操作时首先将top指针增加1;
3. 给top指针指向的数组元素的位置赋值;
代码实现:
public static void pushStackTest(LineStack stack,Object e) //top指向的是元素在数组中的位置,空栈时值为-1 if(stack.top==stack.maxSize-1) System.out.println("栈满"); else //入栈:1.先将栈指针加1 stack.top=stack.top+1; //2.给指针指向的数组位置赋值 stack.array[stack.top]=e;
2.3 出栈操作
算法思路:
1. 判断是否为空栈;
2. 若栈非空,指针下移;
代码实现:
public static void popStackTest(LineStack stack) Object e=null; //判断是否为空栈 if(stack.top==-1) System.out.println("空栈"); else //弹栈元素 e=stack.array[stack.top]; System.out.println(e); //指针下移 stack.top=stack.top-1;
顺序栈进栈和出栈操作的时间复杂度分析:因为二者都没有for循环,所以时间复杂度为O[1]。
2.4 两栈共享空间
对于两个相同类型的栈,我们会为它开辟两个数组空间,但有可能是一个栈已经满了,另一个栈还有很大的存储空间,此时完全可以使用一个数组来存储两个栈。栈1的栈底作为数组的始端,即数组下标为0处,栈2的栈底为数组的末端,即数组下标为n-1处。这样进栈相当于两个指针向中间靠拢的过程,出栈相当于两个指针远离的过程。当top1=-1并且top2=n时,表示栈空;当top1+1=top2时,表示栈满。
两栈共享空间结构的代码实现:
class DoubleStack static int maxSize=14; //两栈存储在一个数组空间中 static Object[] array=new Object[maxSize]; int top1=-1; int top2=maxSize; public DoubleStack()
2.4.1 顺序栈进栈操作
算法思路:
1. 判断是否栈满,当top1+1=top2时,表示栈满;
2. 判断哪个栈有元素进栈,如果栈1进栈,top1加1后给数组赋值;若栈2进栈,top2减1后给数组赋值。
代码实现:
public static void pushDoubleStackTest(DoubleStack doubleStack,Object e,int stackNumber) //首先判断是否栈满 if(doubleStack.top1+1==doubleStack.top2) System.out.println("栈满"); else if(stackNumber==1) //栈1有元素进栈 doubleStack.top1=doubleStack.top1+1; doubleStack.array[doubleStack.top1]=e; else if(stackNumber==2) //栈2有元素进栈 doubleStack.top2=doubleStack.top2-1; doubleStack.array[doubleStack.top2]=e;
2.4.2 顺序栈出栈操作
算法思路:
1. 首先判断哪个栈出栈;
2. 若为栈1出栈,top1减1;若为栈2出栈,top2加1;
代码实现:
public static void popDoubleStackTest(DoubleStack doubleStack,int stackNumber) if(stackNumber==1) if(doubleStack.top1==-1) System.out.println("栈1为空栈"); else System.out.println("出栈元素为:"+doubleStack.array[doubleStack.top1]); doubleStack.top1=doubleStack.top1-1; else if(stackNumber==2) if(doubleStack.top2==doubleStack.maxSize) System.out.println("栈2为空栈"); else System.out.println("出栈元素为:"+doubleStack.array[doubleStack.top2]); doubleStack.top2=doubleStack.top2+1;
完整代码:
package com.java.Stack; /* * 栈的顺序存储结构及实现 * */ public class LineStackTest static LineStack stack=new LineStack(); static DoubleStack stack2=new DoubleStack(); public static void main(String[] args) pushStackTest(stack, 0); pushStackTest(stack, 1); pushStackTest(stack, 2); pushStackTest(stack, 3); for(int j=0;j<stack.maxSize;j++) System.out.println("stack:"+stack.array[j]); popStackTest(stack); popStackTest(stack); pushDoubleStackTest(stack2,"S",1); pushDoubleStackTest(stack2,"D",2); pushDoubleStackTest(stack2,"A",2); pushDoubleStackTest(stack2,"T",2); pushDoubleStackTest(stack2,"F",1); for(int j=0;j<stack2.maxSize;j++) System.out.println("stack2:"+stack2.array[j]); popDoubleStackTest(stack2,1); popDoubleStackTest(stack2,1); popDoubleStackTest(stack2,2); for(int j=0;j<stack2.maxSize;j++) System.out.println("stack2出栈:"+stack2.array[j]); //两栈共享空间的出栈操作 public static void popDoubleStackTest(DoubleStack doubleStack,int stackNumber) if(stackNumber==1) if(doubleStack.top1==-1) System.out.println("栈1为空栈"); else System.out.println("出栈元素为:"+doubleStack.array[doubleStack.top1]); doubleStack.top1=doubleStack.top1-1; else if(stackNumber==2) if(doubleStack.top2==doubleStack.maxSize) System.out.println("栈2为空栈"); else System.out.println("出栈元素为:"+doubleStack.array[doubleStack.top2]); doubleStack.top2=doubleStack.top2+1; //两栈共享空间的进栈操作 public static void pushDoubleStackTest(DoubleStack doubleStack,Object e,int stackNumber) //首先判断是否栈满 if(doubleStack.top1+1==doubleStack.top2) System.out.println("栈满"); else if(stackNumber==1) //栈1有元素进栈 doubleStack.top1=doubleStack.top1+1; doubleStack.array[doubleStack.top1]=e; else if(stackNumber==2) //栈2有元素进栈 doubleStack.top2=doubleStack.top2-1; doubleStack.array[doubleStack.top2]=e; //出栈操作 public static void popStackTest(LineStack stack) Object e=null; //判断是否为空栈 if(stack.top==-1) System.out.println("空栈"); else //弹栈元素 e=stack.array[stack.top]; System.out.println(e); //指针下移 stack.top=stack.top-1; //进栈操作 public static void pushStackTest(LineStack stack,Object e) //top指向的是元素在数组中的位置,空栈时值为-1 if(stack.top==stack.maxSize-1) System.out.println("栈满"); else //入栈:1.先将栈指针加1 stack.top=stack.top+1; //2.给指针指向的数组位置赋值 stack.array[stack.top]=e; class LineStack //空栈的判定条件为top=-1 int top=-1; static int maxSize=8; static Object[] array=new Object[maxSize]; public LineStack() class DoubleStack static int maxSize=14; //两栈存储在一个数组空间中 static Object[] array=new Object[maxSize]; int top1=-1; int top2=maxSize; public DoubleStack()
数据结构与算法栈与队列c语言版(代码片段)
...3.2栈、队列与一般线性表的区别3.3栈的表示和操作的实现顺序栈与顺序表=================顺序栈的表示顺序栈初始化判断顺序栈是否为空求顺序栈的长度清空顺序栈销毁顺序栈顺... 查看详情
数据结构学习笔记——顺序存储结构实现栈(代码片段)
目录一、栈的相关知识二、顺序栈的定义三、顺序栈的初始化四、判断顺序栈是否为空栈五、判断顺序栈是否为满栈六、进栈(插入操作)七、出栈(删除操作)八、读取顺序栈顶元素九、顺序栈的建立一个简单... 查看详情
数据结构第七章:链栈顺序栈
java实现栈(顺序栈,链栈)(代码片段)
顺序栈:packageSeqStack;publicclassStackprivateinttop;privateintbase[];privateintstackSize;publicStack()stackSize=100;base=newint[stackSize];top=-1;publicStack(intn)stackSize=n; 查看详情
顺序栈
...先出的线性表。由于栈本身是一个线性表,所以线性表的顺序存储结构和链式存储结构对于栈来说,同样是适用的。2.栈的顺序存储结构栈的顺序存储结构又称为顺序栈,线性表是用数组来实现的,而栈也是线性表,所以我们使... 查看详情
顺序栈
/* Name:顺序栈的实现 Copyright: Author: Date: Description:*/#ifndefSTACK_H_INCLUDED#defineSTACK_H_INCLUDED#include"ds.h"//forStatus,OK...#ifndefElemType#defineElemTypeint/*数据元素类型默认为 查看详情
数据结构学习笔记——栈的基本知识和顺序存储结构实现栈(顺序栈)(代码片段)
...列(三)共享栈(四)栈的常见应用二、顺序栈的定义三、顺序栈的初始化四、判断顺序栈是否为空栈五、判断顺序栈是否为满栈六、进栈(插入操作)七、出栈(删除操作)八、读取顺序栈顶元... 查看详情
顺序栈-使用顺序栈实现十进制转换二进制(代码片段)
1#include"stdio.h"2#defineMaxSize503typedefintDataType;4typedefstruct5DataTypeelem[MaxSize];6inttop;7SeqStack;8voidinitStack(SeqStack&s)910s.top=-1;1112intpush(SeqStack&s,DataTypex)1314if 查看详情
顺序栈
...借住栈<?php/***PHP实现栈*2017/9/23*/classStack{private$stack=[];//顺序栈private$top=-1;//栈顶指针publicfunction__construct(){$t 查看详情
栈基本操作(顺序栈)
#include<iostream>#include<cstdlib>usingnamespacestd;//定义初始化长度和每次增加的长度constintSTACK_INIT_SIZE=10;constintSTACK_INCREAMENT=2;structStack{int*base;//栈底int*top;//栈顶intstacksize;//已分配栈的大小};//函 查看详情
括号匹配问题(顺序栈实现)
...上传一个吧。那个有时间我再传上来~本周的要求:1.给出顺序栈的存储结构定义。2.完成顺序栈的基本操作函数。1) 初始化顺序栈2) 实现入栈和出栈操作3) 实现取... 查看详情
顺序栈链栈双端栈(代码片段)
...称为后进先出表(LastInFirstOut,简称LIFO)。栈的存储结构一:顺序存储 栈的顺序存储结构同样需要使用一个数组和一个整型变量来实现,利用数组来顺序存储栈中的所有元素,利用整型变量来存储栈顶元 查看详情
顺序栈
...须为这个结构体分配动态内存 否则无法使用 顺序栈:利用一组连续的存储单元依次存放自栈底到栈顶的数据元素;由于栈顶元素是经常变动的,所以附设top指示栈顶元素在顺序表中的位置 基本操作 1 查看详情
顺序栈stackc语言(代码片段)
顺序栈Stack【C语言】/*Byyangbocsu顺序栈Stack2021.07.21*/#include<stdio.h>#include"stdlib.h"/*预定义常量和类型*//*函数结果状态码*/#defineTRUE 1#defineFALSE 0#defineOK 1#defineERROR0 查看详情
顺序栈的基本操作
...始条件#include<stdlib.h>#include<stdio.h>#defineMAXSIZE100顺序栈的存储结构:须有一个一维数组去存放栈中的基本元素,还要栈顶指针,用来存放栈顶元素的下标typedefstructSqStack{ intelem; inttop;}SqStack,*stack_type; 接着开始栈的初始... 查看详情
栈(顺序存储结构)
...一端作插入、删除具有后入先出的特性(LastInFirstOut)分顺序存储结构、链式存储结构两种形式堆栈的顺序存储结构通常由一个一维数组和一个栈顶元素变量组成图解如下:形式一:构建结构体0、结构初始化#defineMaxSize###structStac... 查看详情
王道3.1顺序栈以及链式栈(代码片段)
顺序栈以及链式栈一、的基本概念二、栈的储存三、顺序栈的基本操作四、链式栈的基本操作一、的基本概念1.栈只允许在一段进行删除或插入操作的线性表2.三个术语①栈顶top:线性表允许进行插入删除的那一端②栈底bottom... 查看详情
数据结构(c语言版)严蔚敏->顺序栈的定义利用顺序栈解决有效的括号(代码片段)
头文件SqStack.h#ifndefSQSTACK_H_INCLUDED#defineSQSTACK_H_INCLUDED//顺序栈#defineMax_Stack_Size50typedefcharElemType;typedefstructElemTypedata[Max_Stack_Size];//存放栈中的元素inttop;//栈顶指针SqStack;voidInitSqStack(Sq 查看详情