drop-out栈_牛客博客

<h2>1、drop-out栈能够用来做什么？</h2> 　　在许多提供编辑功能的软件，如word、ps、画图，都会提供“撤销”和“恢复”功能，使用drop-out能够实现这些功能。   <h2>2、drop-out栈特性</h2> 　　drop-out栈是一种特殊的栈，具有如下特征： 　　1、栈的大小固定 　　2、如果在栈满的情况下希望往栈中压入一个数据，栈底的数据会被清除以腾出空间容纳要新的数据。   <h2>3、drop-out栈实现</h2> 　　在此提供一种drop-out栈的实现方法：循环队列 <img src="https://uploadfiles.nowcoder.com/images/20200504/352511047_1588521761150_7BCD8865475F5D831184973C19E04B90"> <img src="https://uploadfiles.nowcoder.com/images/20200504/352511047_1588521761256_90AE86D0581892763489F62D23A8A1CB">             <pre>package learnspring.learnspring.normalJava; import java.awt.datatransfer.StringSelection; /** * @author 肖政宇 * @date 2019-09-28 21:21 * 说明：drop-out栈具有这样的特性：栈满以后，如果试图向栈中压入数据， * 栈底的数据会自动被弹出。 */ public class DropOutStack { /** * size - 栈大小 * stack - 栈 * top - 栈顶（当前能够插入数据的位置） * bottom - 栈底 * total - 栈内数据总数 */ private final int size; private Object[] stack; private int top; private int bottom; private int total; /** * constructor * * @param stackSize - the size of the stack * @throws Exception - wrong size */ public DropOutStack(int stackSize) throws Exception { if (stackSize <= 1) { throw new Exception("wrong value！" + stackSize); } this.size = stackSize; this.stack = new Object[stackSize]; this.top = 0; this.bottom = 0; this.total = 0; } /** * get the size of the stack * * @return - the size of the stack */ public int size() { return size; } /** * push a data into the stack * * @param object = data that you want to push onto the stack * @return - true or false */ public Boolean push(Object object) { try { stack[top] = object; top = (top + 1) % size; //stack is full if (total == size) { //the bottom element have been drop bottom = (bottom + 1) % size; } else {//stack is not full yet total++; } return true; } catch (Exception e) { e.printStackTrace(); return false; } } /** * get the data from the top of the stack * * @return - a data from the top of the stack * @throws Exception - the stack is empty */ public Object peek() throws Exception { if (total == 0) { throw new Exception("the stack is empty!"); } //get the data from the top of the stack top = top == 0 ? size - 1 : top - 1; return stack[top]; } /** * drop a data from the top of the stack * * @return - a data from the top of the stack * @throws Exception - the stack is empty */ public Object pop() throws Exception { if (total == 0) { throw new Exception("the stack is empty!"); } //get the data from the top of the stack top = top == 0 ? size - 1 : top - 1; Object object = stack[top]; //delete the data from the top of the stack stack[top] = null; //change the number of elements in the stack total--; return object; } /** * Is the stack empty？ * * @return - true or false */ public Boolean isEmpty() { return total == 0; } @Override public String toString() { StringBuilder stringStack = new StringBuilder(); stringStack.append('['); for (int i = 0; i < size; i++) { if (stack[i] != null) { stringStack.append(stack[i]); } else { stringStack.append("null"); } if (i + 1 < size) { stringStack.append(','); } } stringStack.append(']'); return stringStack.toString(); } } </pre>