链式栈实现java代码 链栈的基本操作代码

java 用栈实现（(a+b)+c）计算

楼主您好！

在张北等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供做网站、成都网站制作 网站设计制作按需定制网站,公司网站建设,企业网站建设,品牌网站建设,网络营销推广,外贸营销网站建设,张北网站建设费用合理。

友情提示：

一.在复制代码前需要自己添加类。

二.调用方法都为静态，请你仔细查看代码并以修改。

三.注意我的包名。

ParseExpression.calculateExp(postExperssion.toString());

请把上句的引用改为你的类名。

代码欣赏：

package com.qs.impStackCode;

public class Stack {

/**

* @param args

*/

private int maxsize;

int[] stackArray;

int top = -1;

public Stack(int s){

maxsize = s;

stackArray = new int[maxsize];

}

protected void push(int value){

if(top = maxsize)

System.out.println("您存放的存储空间栈已经装满了。");

else

stackArray[++top] = value;

}

protected int pop(){

if(top 0){

System.out.println("当前的栈无数据，已经空了。");

return -1;

}

return stackArray[top--];

}

public long peek(){

return stackArray[top];

}

protected boolean isEmpty(){

return (top == -1);

}

protected boolean isFull(){

return (top == maxsize - 1);

}

//判断操作符号

public boolean isOperator(int operator){

if(operator == 42 || operator == 43 ||

operator == 45 || operator == 47 ||

operator == 41 || operator == 40)

return true;

else

return false;

}

//设置操作符的优先级

public int priority(int operator){

if(operator == 43 || operator == 45 || operator == 40)

return 1;

else if(operator == 42 || operator == 47)

return 2;

else

return 0;

}

public int result(int operator, int operand1, int operand2){

switch(operator){

case 43:

return (operand2 + operand1);

case 45:

return (operand2 - operand1);

case 42:

return (operand2 * operand1);

case 47:

return (operand2 / operand1);

}

return 0;

}

}

以上是栈类。

以下是逻辑类。

package com.qs.impStackCode;

import java.io.*;

public class ParseExpression {

/**

* @param args

*/

protected static String getStr() throws IOException{

BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

return read.readLine();

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Stack operator = new Stack(20);

String experssion = null;

//由于我们在数学应中采用都是前序表达所以不得不把它转换成后序或是中序便于处理，

//所以你在代码中看到的postExperssion.append()就是解析好后的后序表达式

StringBuffer postExperssion = new StringBuffer();

int position = 0;

int operator1;

System.out.print("请您输入前序表达试：");

/*

* 读取的是操作数就直接输出。读取的是运算符，该运算符是左括号 ‘（’就把运算符临时存

* 于堆栈中等到循环过程中遇见‘）’就把运算符号从堆栈中取出来。

* 若该运算符不是括号‘（）’那么就对操作符“+ - * \/”号进行比较，当前比较的运算符号较低时

* 就停致备用，和下个运算符号进行比较，如果相反则存入堆栈中。直到所有算术式解析完为止

*/

try {

experssion = ParseExpression.getStr();

while(true){

//判断是否是运算符

if(operator.isOperator((int) experssion.charAt(position))){

if(operator.top == -1 || (char) experssion.charAt(position) == '('){

//把运算符存入堆栈中

operator.push(experssion.charAt(position));

}else{

if((char) experssion.charAt(position) == ')'){

//取出运算符直到去出'('

if(operator.stackArray[operator.top] != 40){

operator1 = operator.pop();

postExperssion.append((char)operator1);

}

}else{

if(operator.priority((int) experssion.charAt(position))

= operator.priority(operator.stackArray[operator.top])

operator.top != -1){

operator1 = operator.pop();

if(operator1 != 40)

postExperssion.append((char)operator1);

}

operator.push(experssion.charAt(position));

}

}

}else

postExperssion.append(experssion.charAt(position));

position++;

if(position = experssion.length()) break;

}

} catch (IOException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

while(operator.top != -1){//取出在堆栈中的所有运算符

operator1 = operator.pop(); postExperssion.append((char)operator1);

} //System.out.println(postExperssion.toString()); ParseExpression.calculateExp(postExperssion.toString());

}

//这个方法属于后续运算方法，就是表达式解析为后序的式子

//如：8/7+(7-2)*4 解析后变成这样 87/72-4*+

/*

* 算法解释：从左至右读取运算单元

* 读取操作数存入堆栈，读取运算符取出操作数进行运算

* 当操作数读完后，即为表达式运算结果

*/

public static void calculateExp(String experssion){

Stack operand = new Stack(20);

int position = 0;

int operand1 = 0;

int operand2 = 0;

int executeResult = 0;

while(true){

if(operand.isOperator(experssion.charAt(position))){

operand1 = operand.pop();

operand2 = operand.pop();

operand.push(operand.result(experssion.charAt(position),

operand1, operand2));

}else

//存入操作数需要做ASCII转换，在这我把其它符号的ASCII

//一并写出来 '[' 91 ']' 93 '{' 123 '}' 125

operand.push(experssion.charAt(position) - 48);

position++;

if(position = experssion.length())

break;

}

executeResult = operand.pop();

System.out.print("被计算的表示式：" + experssion + " ");

System.out.println("运算结果 = " + executeResult);

}

}

再次感谢楼主加分，如果需要扩展加入‘}’‘]’

这时需要在我的两个类中加入相应条件语句和合理的

if判断OK

实现链式栈的基本操作：入栈、出栈、取栈顶元素、判定栈空、栈满。

#include stdio.h

#include malloc.h

struct stack

{

int number;

struct stack *next;

};

struct stack *top;//指向栈顶

struct stack *p;//临时指针

//创建链栈

void create(int first_value)

{

p = (struct stack*)malloc(sizeof(struct stack));//申请内存空间

p-number = first_value;//给栈底赋值

p-next = NULL;//栈底的指针为空

top = p;//栈顶指向栈底

}

//进栈

void input(int value)

{

p = (struct stack*)malloc(sizeof(struct stack));//申请内存空间

p-number = value;//赋值

p-next = top;//指向原来的栈顶

top = p;//栈顶往上移动一位

}

//出栈

void output()

{

p = top;//p = 栈顶

top = top-next;//栈顶往下移动一位

free(p);//释放p

}

//清空栈

void clear()

{

while(top-next != NULL)//如果不是栈底

output();//出栈

free(top);//释放栈顶

}

//取栈顶元素

int topElement()

{

return top-number;

}

int main()

{

int i;

create(0);

for(i=1;i=10;i++)

input(i);

//clear();

printf("\n栈的内容：\n");

for(p=top;;p=p-next)

{

printf("%d\n",p-number);

if(p-next == NULL)

break;

}

printf("栈顶元素=%d\n",topElement());

}

java语言中用LinkList实现堆栈

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。

LinkedList数据结构是一种双向的链式结构，每一个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素，和数组的顺序存储结构（如：ArrayList）相比，插入和删除比较方便，但速度会慢一些。

栈的定义

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。

(2)当表中没有元素时称为空栈。

(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。

栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

实现代码：

package com.weisou.dataStruct;

import java.util.LinkedList;

@SuppressWarnings("unchecked")

public class MyStack {

LinkedList linkList = new LinkedListObject();

public void push(Object object) {

linkList.addFirst(object);

}

public boolean isEmpty() {

return linkList.isEmpty();

}

public void clear() {

linkList.clear();

}

// 移除并返回此列表的第一个元素

public Object pop() {

if (!linkList.isEmpty())

return linkList.removeFirst();

return "栈内无元素";

}

public int getSize() {

return linkList.size();

}

public static void main(String[] args) {

MyStack myStack = new MyStack();

myStack.push(2);

myStack.push(3);

myStack.push(4);

System.out.println(myStack.pop());

System.out.println(myStack.pop());

}

}

队列定义

队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表

（1）允许删除的一端称为队头（Front）。

（2）允许插入的一端称为队尾（Rear）。

（3）当队列中没有元素时称为空队列。

（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。

实现代码：

package com.weisou.dataStruct;

import java.util.LinkedList;

/**

*

* @author gf

* @date 2009-11-13

*/

public class MyQueue {

LinkedList linkedList = new LinkedList();

//队尾插

public void put(Object o){

linkedList.addLast(o);

//队头取 取完并删除

public Object get(){

if(!linkedList.isEmpty())

return linkedList.removeFirst();

else

return "";

}

public boolean isEmpty(){

return linkedList.isEmpty();

}

public int size(){

return linkedList.size();

}

public void clear(){

linkedList.clear();

}

/**

* @param args

*/

public static void main(String[] args) {

MyQueue myQueue= new MyQueue();

myQueue.put(1);

myQueue.put(2);

myQueue.put(3);

System.out.println(myQueue.get());

}

}