liddblog

## 栈

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

## 利用数组实现的栈结构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
{
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
{
return s;
}
//--------------------------------------------------------------
}  // end class BracketsApp``````

## 栈的效率

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

### liddblog

NEO改进协议提案8（NEP-8）

NEO-FANS
2018/12/17
3
0

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

2014/07/06
626
0

2014/11/24
259
0

2018/06/01
0
0

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

Riverzhou
8分钟前
4
0

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

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

11分钟前
0
0

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

26分钟前
4
0