Java Tutorial/Collections/Your Stack
Содержание
A stack allows access to only one data item: the last item inserted
- Push: To insert a data item on the stack
- Pop : To remove a data item from the top of the stack
- Peek: Read the value from the top of the stack without removing it.
<source lang="java">
class Stack {
private int maxSize; private double[] stackArray; private int top; public Stack(int s) { maxSize = s; stackArray = new double[maxSize]; top = -1; } public void push(double j) { stackArray[++top] = j; } public double pop() { return stackArray[top--]; } public double peek() { return stackArray[top]; } public boolean isEmpty() { return (top == -1); } public boolean isFull() { return (top == maxSize - 1); }
} public class MainClass {
public static void main(String[] args) { Stack theStack = new Stack(10); theStack.push(20); theStack.push(40); theStack.push(60); theStack.push(80); while (!theStack.isEmpty()) { double value = theStack.pop(); System.out.print(value); System.out.print(" "); } System.out.println(""); }
}</source>
80.0 60.0 40.0 20.0
Demonstrating a stack implemented as a list
<source lang="java">
class Link {
public int iData; public Link next; public Link(int id) { iData = id; } public String toString() { return "{" + iData + "} "; }
} class LinkList {
private Link first; public LinkList() { first = null; } public boolean isEmpty() { return (first == null); } public void insertFirst(int dd) { Link newLink = new Link(dd); newLink.next = first; first = newLink; } public int deleteFirst() { Link temp = first; first = first.next; return temp.iData; } public String toString() { String str=""; Link current = first; while (current != null) { str += current.toString(); current = current.next; } return str; }
} class LinkStack {
private LinkList theList; public LinkStack() { theList = new LinkList(); } public void push(int j) { theList.insertFirst(j); } public double pop() { return theList.deleteFirst(); } public boolean isEmpty() { return (theList.isEmpty()); } public String toString() { return theList.toString(); }
} public class MainClass {
public static void main(String[] args) { LinkStack theStack = new LinkStack(); theStack.push(20); theStack.push(40); System.out.println(theStack); theStack.push(60); theStack.push(80); System.out.println(theStack); theStack.pop(); theStack.pop(); System.out.println(theStack); }
}</source>
{40} {20} {80} {60} {40} {20} {40} {20}
Stack Example: Delimiter Matching
This time we use the Stack class from Java library.
Using stack to check matching brackets
Examples:
- c[d] // correct
- a{b[c]d}e // correct
- a{b(c]d}e // not correct; ] doesn"t match (
- a[b{c}d]e} // not correct; nothing matches final }
- a{b(c) // not correct; Nothing matches opening {
<source lang="java">
import java.util.Stack; class BracketChecker {
private String input; public BracketChecker(String in) { input = in; } public void check() { Stack<Character> theStack = new Stack<Character>(); for (int j = 0; j < input.length(); j++) { char ch = input.charAt(j); switch (ch) { case "{": case "[": case "(": theStack.push(ch); break; case "}": case "]": case ")": if (!theStack.isEmpty()) { char chx = theStack.pop(); if ((ch == "}" && chx != "{") || (ch == "]" && chx != "[") || (ch == ")" && chx != "(")) System.out.println("Error: " + ch + " at " + j); } else System.out.println("Error: " + ch + " at " + j); break; default: break; } } if (!theStack.isEmpty()){ System.out.println("Error: missing right delimiter"); } }
} public class MainClass {
public static void main(String[] args) { String input; input = "[]]()()"; BracketChecker theChecker = new BracketChecker(input); theChecker.check(); }
}</source>
Error: ] at 2
Using stack to reverse a string
<source lang="java">
class Stack {
private int maxSize; private char[] stackArray; private int top; public Stack(int s) { maxSize = s; stackArray = new char[maxSize]; top = -1; } public void push(char j) { stackArray[++top] = j; } public char pop() { return stackArray[top--]; } public char peek() { return stackArray[top]; } public boolean isEmpty() { return (top == -1); } public boolean isFull() { return (top == maxSize - 1); }
} public class MainClass {
public static void main(String[] args) { String input = "input"; int stackSize = input.length(); Stack theStack = new Stack(stackSize); for (int j = 0; j < input.length(); j++) { char ch = input.charAt(j); theStack.push(ch); } while (!theStack.isEmpty()) { char ch = theStack.pop(); System.out.println(ch); } }
}</source>
t u p n i