文档章节

栈详述

liddblog
 liddblog
发布于 2017/01/08 22:38
字数 765
阅读 6
收藏 0

       栈值允许访问一个数据项:即最后插入的数据项移除这个数据项后才能访问倒数第二个插入的数据项,依次类推,这种机制在不少编程环境下都很有用。栈也是哪些应用了相当复杂的数据结构算法的便利工具,在二叉树中,用栈来辅助遍历树的节点,在图中,利用栈来辅助查找图的顶点。

利用数组实现的栈结构java代码

// stack.java
	// demonstrates stacks
	// to run this program: C>java StackApp
	////////////////////////////////////////////////////////////////
	class StackX
	   {
	   private int maxSize;        // size of stack array
	   private long[] stackArray;
	   private int top;            // top of stack
	//--------------------------------------------------------------
	   public StackX(int s)         // constructor
	      {
	      maxSize = s;             // set array size
	      stackArray = new long[maxSize];  // create array
	      top = -1;                // no items yet
	      }
	//--------------------------------------------------------------
	   public void push(long j)    // put item on top of stack
	      {
	      stackArray[++top] = j;     // increment top, insert item
	      }
	//--------------------------------------------------------------
	   public long pop()           // take item from top of stack
	      {
	      return stackArray[top--];  // access item, decrement top
	      }
	//--------------------------------------------------------------
	   public long peek()          // peek at top of stack
	      {
	      return stackArray[top];
	      }
	//--------------------------------------------------------------
	   public boolean isEmpty()    // true if stack is empty
	      {
	      return (top == -1);
	      }
	//--------------------------------------------------------------
	   public boolean isFull()     // true if stack is full
	      {
	      return (top == maxSize-1);
	      }
	//--------------------------------------------------------------
	   }  // end class StackX
	////////////////////////////////////////////////////////////////
	class StackApp
	   {
	   public static void main(String[] args)
	      {
	      StackX theStack = new StackX(10);  // make new stack
	      theStack.push(20);               // push items onto stack
	      theStack.push(40);
	      theStack.push(60);
	      theStack.push(80);
	
	      while( !theStack.isEmpty() )     // until it's empty,
	         {                             // delete item from stack
	         long value = theStack.pop();
	         System.out.print(value);      // display it
	         System.out.print(" ");
	         }  // end while
	      System.out.println("");
	      }  // end main()
	   }  // end class StackApp

利用栈使单词逆序的算法

class Reverser
	   {
	   private String input;                // input string
	   private String output;               // output string
	//--------------------------------------------------------------
	   public Reverser(String in)           // constructor
	      { input = in; }
	//--------------------------------------------------------------
	   public String doRev()                // reverse the string
	      {
	      int stackSize = input.length();   // get max stack size
	      StackX theStack = new StackX(stackSize);  // make stack
	
	      for(int j=0; j<input.length(); j++)
	         {
	         char ch = input.charAt(j);     // get a char from input
	         theStack.push(ch);             // push it
	         }
	      output = "";
	      while( !theStack.isEmpty() )
	         {
	         char ch = theStack.pop();      // pop a char,
	         output = output + ch;          // append to output
	         }
	      return output;
	      }  // end doRev()
	//--------------------------------------------------------------
	   }  // end class Reverser
	////////////////////////////////////////////////////////////////
	class ReverseApp
	   {
	   public static void main(String[] args) throws IOException
	      {
	      String input, output;
	      while(true)
	         {
	         System.out.print("Enter a string: ");
	         System.out.flush();
	         input = getString();          // read a string from kbd
	         if( input.equals("") )        // quit if [Enter]
	            break;
	                                       // make a Reverser
	         Reverser theReverser = new Reverser(input);
	         output = theReverser.doRev(); // use it
	         System.out.println("Reversed: " + output);
	         }  // end while
	      }  // end main()
	//--------------------------------------------------------------
	   public static String getString() throws IOException
	      {
	      InputStreamReader isr = new InputStreamReader(System.in);
	      BufferedReader br = new BufferedReader(isr);
	      String s = br.readLine();
	      return s;
	      }
	//--------------------------------------------------------------
	   }  // end class ReverseApp

利用栈实现分隔符匹配的算法

class BracketChecker
	   {
	   private String input;                   // input string
	//--------------------------------------------------------------
	   public BracketChecker(String in)        // constructor
	      { input = in; }
	//--------------------------------------------------------------
	   public void check()
	      {
	      int stackSize = input.length();      // get max stack size
	      StackX theStack = new StackX(stackSize);  // make stack
	
	      for(int j=0; j<input.length(); j++)  // get chars in turn
	         {
	         char ch = input.charAt(j);        // get char
	         switch(ch)
	            {
	            case '{':                      // opening symbols
	            case '[':
	            case '(':
	               theStack.push(ch);          // push them
	               break;
	
	            case '}':                      // closing symbols
	            case ']':
	            case ')':
	               if( !theStack.isEmpty() )   // if stack not empty,
	                  {
	                  char chx = theStack.pop();  // pop and check
	                  if( (ch=='}' && chx!='{') ||
	                      (ch==']' && chx!='[') ||
	                      (ch==')' && chx!='(') )
	                     System.out.println("Error: "+ch+" at "+j);
	                  }
	               else                        // prematurely empty
	                  System.out.println("Error: "+ch+" at "+j);
	               break;
	            default:    // no action on other characters
	               break;
	            }  // end switch
	         }  // end for
	      // at this point, all characters have been processed
	      if( !theStack.isEmpty() )
	         System.out.println("Error: missing right delimiter");
	      }  // end check()
	//--------------------------------------------------------------
	   }  // end class BracketChecker
	////////////////////////////////////////////////////////////////
	class BracketsApp
	   {
	   public static void main(String[] args) throws IOException
	      {
	      String input;
	      while(true)
	         {
	         System.out.print(
	                      "Enter string containing delimiters: ");
	         System.out.flush();
	         input = getString();     // read a string from kbd
	         if( input.equals("") )   // quit if [Enter]
	            break;
	                                  // make a BracketChecker
	         BracketChecker theChecker = new BracketChecker(input);
	         theChecker.check();      // check brackets
	         }  // end while
	      }  // end main()
	//--------------------------------------------------------------
	   public static String getString() throws IOException
	      {
	      InputStreamReader isr = new InputStreamReader(System.in);
	      BufferedReader br = new BufferedReader(isr);
	      String s = br.readLine();
	      return s;
	      }
	//--------------------------------------------------------------
	   }  // end class BracketsApp

栈的效率

       StackX类中实现的栈,数据项入栈和出栈的时间复杂度都为常数O(1),这也就是说,栈操作所耗的时间不依赖于栈中数据项的个数,因此操作时间很短,栈不需要比较和移动操作。

© 著作权归作者所有

上一篇: 队列详述
下一篇: 插入排序详述
liddblog
粉丝 4
博文 70
码字总数 65593
作品 0
海淀
程序员
私信 提问
NEO改进协议提案8(NEP-8)

文章目录 摘要 动机 原理 详述 CALL_I CALL_E CALL_ED CALL_ET CALL_EDT 向后兼容性 实现 摘要 本NEP提议NeoVM计算栈堆栈隔离,以确保动态调用的安全性,并为将来的新功能提供支持。 动机 现...

NEO-FANS
2018/12/17
3
0
了解递归的几种姿势 - 函数式编程

什么是递归 递归和迭代是一枚硬币的两面,在不可变的条件下,递归提供了一种更具表现力、强大且优秀的迭代替代方法 递归函数由以下两个主要部分组成: 基准 递归条件 递归主要的核心思想是将...

苏里
06/13
0
0
Python数据结构总结篇

数据结构篇主要是阅读[Problem Solving with Python]( http://interactivepython.org/courselib/static/pythonds/index.html)时写下的阅读记录,当然,也结合了部分[算法导论]( http://en.wi...

宅男潇涧
2014/07/06
626
0
串行(Sequential)、并发(Concurrent)、并行(parallel)与分布式

Table of Contents 1 串行(Sequential) 2 并发(Concurrent) 3 并行(parallel) 4 分布式(distributed) 5 《编译点滴》评 1 串行(Sequential) 串行程序中,程序会顺序的执行每一条指...

雍雍_yoyo
2014/11/24
259
0
学习JavaScript数据结构和算法(第二版) 读后感

总体概述 本书是由[巴西] 格罗纳(Loiane Groner)[著作],全书总共238页; 本书从介绍javascript语言入手,然后分别介绍了数组(列表)、栈、队列、链表等顺序数据结构,然后依次介绍了集合、...

张蕾_
2018/06/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

006-Sigle-基于blockstack去中心化博客

本篇文章主要讲解有关基于Blockstack的Sigle是一个去中心化的博客项目; 官网地址:https://www.sigle.io/ Github地址:https://github.com/pradel/sigle 页面展示: 介绍: A beautiful de...

Riverzhou
8分钟前
4
0
驰骋工作流引擎开发平台属性功能的隐藏显示介绍

关键字: 工作流程管理系统 工作流引擎 asp.net工作流引擎 java工作流引擎. 表单引擎 工作流功能说明 工作流设计 工作流快速开发平台 业务流程管理 bpm工作流系统 java工作流主流框架 自定义...

孟娟
9分钟前
4
0
MyBatis binding 模块分析

MyBatis binding 模块分析 binding功能代码所在包 org.apache.ibatis.binding binding模块作用 封装ibatis编程模型 ibatis编程模型中,SqlSession作为sql执行的入口,实用方法为sqlSession.se...

红妍落日
11分钟前
0
0
网易互娱的数据库选型和 TiDB 应用实践

作者介绍:李文杰,网易互娱计费组,高级数据库管理工程师,TiDB User Group Ambassador。 一、业务架构简介 计费组是为网易互娱产品提供统一登录和支付高效解决方案的公共支持部门,对内是互...

TiDB
18分钟前
0
0
Debezium接入Mysql遇到到的Tinyint坑

问题背景: 在Debezium做数据初始化的时候,对于一些tinyint字段的值,出现0,1的值的异常。 经过源码排查,数据在JDBC上面,读取到的数据是Boolean值。 通过排查,原来是MYSQL特有的数据问题...

吐槽的达达仔
26分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部