顺序栈

顺序栈是利用一组地址连续的存储单元依次存放数据元素从栈底到栈顶，栈底位置固定不变，栈顶位置随着入栈和出栈操作而变化，类似于一维数组，那既然是数组，我们就既可以用下标，也可以用指针来操作它

*对顺序栈，我们要实现的操作有:

1 .顺序栈的初始化 Initstack，

2 .顺序栈的入栈(压栈) Push，

3 .顺序栈的出栈(弹栈) Pop,

4 .取栈顶元素GetTop *
1. 数值下标
#include <iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100

typedef int Status;
typedef int SElemtype;

既然要用数组下标，那我们就直接在栈中声明一个数组
typedef struct {
 SElemtype elem[MAXSIZE]; //存放栈元素的数组 
 SElemtype top;  //存放栈顶元素的下标 
 int stacksize;  //栈的长度 
}SqStack; 

1.栈的初始化:
Status Initstack(SqStack &s){
 s.top = -1;    //栈的初始化,如果栈顶指针 top 等于-1 则栈为空栈
 s.stacksize = MAXSIZE;  //stacksize置为栈的最大容量MAXSIZE 
 return OK;
}

栈中，当top等于-1时，则该栈就是空栈，所以初始化栈时，我们直接把top=-1即可
2.栈的压栈
Status Push(SqStack &s , SElemtype e){
 if(s.top == s.stacksize - 1)
  return ERROR; //栈满 
 s.elem[s.top++] = e;  //将元素e压入栈，top下移 
 return OK;
}


压栈时，首先验证栈是否满了，如果栈满则无法压栈。

当下标top等于stacksize-1时则栈满，
3.弹栈
Status Pop(SqStack &s, SElemtype &e){
 if(s.top == -1)
  return ERROR; //栈空
 e = s.elem[--s.top];  //top指针下移，将值赋给e
 return OK; 
}

弹栈时需注意的是，如果栈为空，那么你弹栈就会发生错误,所以需先判断栈是否为空
4.获取栈顶元素
SElemtype GetTop(SqStack &s){
 if(s.top != -1) //非空 
  return s.elem[s.top - 1]; //获取栈顶元素 
}

获取栈顶元素同样需要判断栈是否为空，如果栈为空，那么你获取的栈顶元素就不是你需要的，也是无意义的
数组下标介绍完了，那就在看下指针操作吧，读者在看的时候，只需理解其一就行，因为两种方法的思路是一样的，只是代码不同

用指针
同样，头文件，宏定义，取别名与上面的一样,那就直接看实现函数吧
typedef struct {
 SElemtype *base; //栈底指针  
 SElemtype *top;  //栈顶指针 
 int stacksize;  //栈的长度 
}SqStack;

1.初始化
Status Initstack(SqStack &s){
 s.base = new SElemtype[MAXSIZE];  //为顺序栈动态分配最大容量为MAXSIZE的数组空间
 if(!s.base)
  exit(OVERFLOW);    //存储空间分配失败 
 s.top = s.base;       //top初始化为base，此时为空栈 
 s.stacksize = MAXSIZE;  //stacksize置为栈的最大容量MAXSIZE 
 return OK;
}  

这里是用指针base开辟空间，作用与数组是一样的
2.压栈
Status Push(SqStack &s , SElemtype e){
 if(s.top - s.base == s.stacksize)
  return ERROR;  //栈满
 *(s.top++) = e;    //将原素e压入栈底，top上移
 return OK; 
}

这里判断栈满的用法是，两个指针的差值是否等于s.stacksize，

*(s.top++) = e;其实就是

*(s.top) = e;

s.top = s.top++;
3.弹栈
Status Pop(SqStack &s, SElemtype &e){
 if(s.base == s.top)
  return ERROR;  //栈空
 e = *(--s.top); //top指针下移，将值赋给e   
 return OK;
} 

这里判断栈是否为空看着有些奇怪，如果不明白就看初始化函数中 s.top = s.base; 这句，相信聪明的你已经明白了
4.去栈顶元素
SElemtype GetTop(SqStack &s){
 if(s.top != s.base)  //栈非空 
  return *(s.top - 1); //返回栈顶元素，不修改top指针 
}

这个注释就很明白了
下面看一些测试结果

当然这里是用int型数据测试的，读者也可以把 typedef int SElemtype;中的int修改为其他类型测试一下

一、分析
栈是限定仅在表的一端进行插入或删除操作的线性表，对于栈来说，操作端称为栈顶，另一端则称为栈底，栈的修改是按照后进先出的原则进行的，因此又称为后进先出的线性表。
顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
一个标准的顺序栈具有如下基本操作：
1、初始化顺序栈
2、销毁顺序栈
3、清空顺序栈
4、检测顺序栈是否为空
5、返回顺序栈中的元素个数
6、返回顺序栈的栈顶元素，不修改栈顶指针
7、向顺序栈顶中压入元素
8、从顺序栈顶中弹出元素
9、从栈底到栈顶遍历顺序栈
在Java中，可以将整个顺序栈定义成一个类，类中定义有一个数组类型的属性表示顺序存储结构来存储元素，再定义一个int类型的属性top来作为指针指示栈顶元素在数组中的位置，顺序栈的基本操作则定义成类的方法。初始化顺序栈即实例化类，销毁顺序栈即销毁实例化出来的对象。
二、实现
1、定义类属性和构造函数
1 classInitStack{2
3     private int [] stack = null;  　　　　//存储元素
4
5     private int top = 0;  　　　　　　　　　//指示栈顶元素在顺序栈中的位置
6
7     public InitStack(int max) {  　　　　　//初始化自定义大小的顺序栈
8         this.stack = new int[max];9 }10 }
2、清空顺序栈
1 public voidclearStack() {2     this.top = 0;  　　　　　　　　//直接令栈顶指针指向栈底即可
3 }
3、检测顺序栈是否为空
1 public booleanstackEmpty() {2     if(this.top == 0) {  　　　　　　//检测栈顶指针是否指向栈底即可
3         return true;4     }else{5         return false;6 }7 }
4、返回顺序栈中的元素个数
1 public intstackLength() {2     return this.top;  　　　　　　//栈顶指针的值即代表了元素个数
3 }
5、返回顺序栈的栈顶元素，不修改栈顶指针
1 public int[] getTop() {2
3     if (this.top == 0) {  　　　　　　//如果顺序栈为空，则返回空
4         return null;5 }6
7     int [] i = new int[1];8     i[0] = stack[this.top - 1]; 　  //获取栈顶元素
9
10     returni;11 }
6、向顺序栈顶中压入元素
1 public boolean push(intvalue) {2
3     if(this.top == this.stack.length) {  　　//判断顺序栈是否已满
4         return false;5 }6
7     this.stack[this.top] = value;  　　　　　 //压入元素
8     this.top++;  　　　　　　　　　　　　　　　　//栈顶指针加一
9     return true;10 }
7、从顺序栈顶中弹出元素
1 public int[] pop() {2
3     if (this.top == 0) {  　　　　//判断顺序栈是否已空
4         return null;5 }6
7     int [] i = new int[1];8     this.top--;  　　　　　　　　　 //栈顶指针减一
9     i[0] = stack[this.top];  　　//获取栈顶元素
10     returni;11 }
8、从栈底到栈顶遍历顺序栈
1 public String stackTraverse() {  　　　　　　　　　　//通过输出顺序栈元素来表示遍历
2
3     String s = "";  　　　　　　　　　　　　　　　　　 //存储要输出的元素
4
5     for (int i = 0; i < this.top; i++) {  　　　　//循环遍历
6         s += this.stack[i] + "、";7 }8
9     if(s.length() == 0) {  　　　　　　　　　　　　　//如果未获取到元素，返回空字符串
10         returns;11 }12
13     return s.substring(0,s.length() - 1);  　　　//除去最后一个顿号后返回
14 }
三、小结
以上就是顺序栈用Java的实现，由于只定义了整数的数组，因此只能操作整数数据，但顺序栈的基本思想都已实现。

栈——顺序栈
栈的定义
栈的表示和实现
顺序栈的定义
顺序栈的模块说明
栈基本操作部分算法描述

栈的定义
栈：是限定仅在表尾进行插入和删除操作的线性表，又称为后进先出的线性表（简称LIFO结构）。

栈顶：线性表的表尾。

栈底：线性表的表头。

空栈：不含元素的栈。
栈的表示和实现
和线性表类似，栈也有两种存储表示方法：顺序栈和链栈。
顺序栈：栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，通常附设指针top指示栈顶元素在顺序栈中的位置。
顺序栈的定义
typedef struct{
	SElemType *base;	//栈底指针
	SElemType *top;		//栈顶指针
	int stacksize;		//栈的最大容量
}SqStack;

顺序栈的模块说明
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct{
    int *base;
    int *top;
    int stacksize;
}SqStack;

Status InitStack(SqStack &S);				//构造一个空栈S
Status DestroyStack(SqStack &S);			//销毁栈S
Status ClearStack(SqStack &S);				//清除栈S
Status StackEmpty(SqStack S);				//若栈S为空栈，则返回TRUE，否则返回FALSE
int StackLength(SqStack S);					//返回栈S的长度
Status GetTop(SqStack S, SElemType &e);		//若栈S不为空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
Status Push(SqStack &S, SElemType e);		//插入元素e为新的栈顶元素
Status Pop(SqStack &S, SElemType &e);		//若栈S不为空，弹出栈顶元素，用e返回，并返回OK，否则返回ERROR
Status StackTraverse(SqStack S, Status (*visit)());		//从栈底到栈顶依次对栈中每一个元素调用visit()。一旦visit()失败，则操作失败

栈基本操作部分算法描述
Status InitStack(SqStack &S){
//构造一个空栈S
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base)
        exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status GetTop(SqStack S, SElemType e){
//若栈S不为空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
	if(S.top == S.base)
		return ERROR;
	e = *(S.top - 1);
	return OK;
}

Status Push(SqStack &S, SElemType e){
//插入元素e为新的栈顶元素
    if(S.top - S.base >= S.stacksize){
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!S.base)
            exit(OVERFLOW);
            
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}

Status Pop(SqStack &S, SElemType &e){
//若栈S不为空，弹出栈顶元素，用e返回，并返回OK，否则返回ERROR
    if(S.top == S.base)
        return ERROR;
    e = * --S.top;
    return OK;
}

Status StackEmpty(SqStack S){
//若栈S为空栈，则返回TRUE，否则返回FALSE
	if(S.top == S.base)
		return TRUE;
	return FALSE;
}

栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈为空栈。栈的顺序存储结构为顺序栈。通常把数组中下标为0的一端作为栈底，同时附设指针top指向栈顶元素的位置，栈空时top = -1。
以下是java实现顺序栈的代码：
package com.dhy.seqstack;
/**
* 顺序栈
* @author Administrator
*
*/
public class SeqStack {
private Object[] elementData;  //存放元素的数组
private int stackSize;  //栈的大小
private int  top; //栈顶指针，为数组元素下标
/**
* 构造一个栈
*/
public SeqStack(int size){
elementData = new Object[size];
stackSize = size;
top = -1;
}
/**
* 压栈
* @param e
* @return
*/
public boolean push(Object e){
if(top == stackSize - 1)
throw new RuntimeException("栈已满");
top++;
elementData[top] = e;;
return true;
}
/**
* 出栈
* @return
*/
@SuppressWarnings("unchecked")
public T pop(){
if(top == -1)
throw new RuntimeException("栈为空");
return (T)elementData[top--];
}
/**
* 获取栈顶元素
* @return
*/
@SuppressWarnings("unchecked")
public T get(){
if(top == -1)
throw new RuntimeException("栈为空");
return (T)elementData[top];
}
/**
* 判断栈是否为空
* @return
*/
public boolean isEmpty(){
if(top == -1)
return true;
else
return false;
}
/**
* 遍历
*/
@SuppressWarnings("unchecked")
@Override
public String toString(){
String str = "[";
for(int i=top;i>=0;i--){
if(i == 0)
str = str + (T)elementData[i];
else
str = str + (T)elementData[i] + ",";
}
str = str + "]";
return str;
}
}