2019独角兽企业重金招聘Python工程师标准>>>

(堆)栈概述

栈是一种特殊的线性表，是操作受限的线性表

栈的定义和特点 •定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 •特点：先进后出（FILO）或后进先出（LIFO）

栈的结构

如下图所示：

线性表的操作主要包括：

（1）清空(堆)栈

（2）判断是否为空

（3）元素的个数

（4）入栈

（5）出栈

（6）取栈顶元素

接口

由此，对队列的抽象数据类型定义Queue接口如下：
package stack; /*** (堆)栈* @author Administrator**/ public interface Stack {/*** 清空堆栈*/public void clear();/*** 入栈* @param obj 入栈的元素*/public void push(Object obj);/*** 出栈* @return 出栈的结果*/public Object pop();/*** 判断是否为空* @return*/public boolean isEmpty();/*** 求元素的个数* @return 元素的个数*/public int size();/*** 取栈顶元素* @return 栈顶元素*/public Object peek();}

顺序(堆)栈

结构模型

栈顶指针top,指向实际栈顶后的空位置，初值为0。

栈的初始空间大小为M

top=0,栈空，此时出栈，则下溢（underflow)；

top=M,栈满，此时入栈，则上溢（overflow)；

源代码

package stack; /*** 顺序(堆)栈* @author Administrator**/ public class ArrayStack implements Stack{private static int DEFAULT_SIZE = 100; private int Top;Object array[];public ArrayStack() {Top = 0;array = new Object[DEFAULT_SIZE];}public boolean isEmpty() {return 0 == Top ;}public void expand() {Object[] newArray = new Object[2 * array.length];for(int i=0; i<array.length; i++) {newArray[i] = array[i];}array = newArray;}/*public void expand() {try {Object[] newArray = new Object[2*DEFAULT_SIZE];for(int i=0; i<array.length; i++) {newArray[i] = array[i];}array = newArray;}catch(OutOfMemoryError e) {System.out.println("error in expand of Stack class!");//e.printStackTrace();}DEFAULT_SIZE = 2*DEFAULT_SIZE;}*/public void push(Object obj) {if(Top == array.length) {expand();} array[Top] =obj;Top ++;}public Object pop() {if(0 == Top) throw new IllegalStateException();Object val = array[-- Top];array[Top] = null;return val;}public void clear() {for(int i=0; i<array.length; i++) {array[i] = null;Top = 0;}}public Object peek() {if(0 == Top) throw new IllegalStateException();return array[Top - 1];}public int size() {return Top;}public String toString() {String s = "[";for(int i=Top-1; i>=0 ; i--) {s = s + array[i];s = s + ", ";}s = s + "]";return s;}}

链式(堆)栈

结构模型

源代码

package stack;/*** 链式(堆)栈的结点* @author luoweifu**/ class Node{Object data; //数据元素Node next; //后驱结点public Node() {this(null);}public Node(Object data) {this.data = data;this.next = null;} }/*** 链式(堆)栈, 无头结点* @author Administrator**/ public class LinkStack implements Stack {private Node top; //栈顶指针private int size; //栈的大小public LinkStack() {top = null;size = 0;}@Overridepublic void clear() {top = null;size = 0;}@Overridepublic void push(Object obj) {Node p = new Node(obj);if(top == null) {top = p;} else {p.next = top;top = p;}size ++;}@Overridepublic Object pop() {Node p = top;top = top.next;size --;return p.data;}@Overridepublic boolean isEmpty() {if(size == 0)return true;elsereturn false;}@Overridepublic int size() {return size;}@Overridepublic Object peek() {return top.data;}public String toString() {StringBuilder sb = new StringBuilder("[");Node p = top;if(p == null) {sb.append("");} else {do{sb.append(p.data + ", ");}while((p = p.next) != null);}sb.append("]");return sb.toString();} }

测试(堆)栈

package stack;public class Test {/*** 测试堆栈* @param args*/public static void main(String[] args) {//Stack stack = new ArrayStack();Stack stack = new LinkStack();for(int i=0; i<10; i++) {stack.push(i);}System.out.println(stack.toString());Object a = stack.pop();System.out.println(a + stack.toString());stack.push(20);Object b = stack.peek();System.out.println( b + stack.toString());stack.clear();System.out.println( "数据数量：" + stack.size()+ " isEmpty? " + stack.isEmpty() + " 数据为：" + stack.toString());}}

结果

[9,  8,  7,  6,  5,  4,  3,  2,  1,  0,  ] 9[8,  7,  6,  5,  4,  3,  2,  1,  0,  ]
20[20,  8,  7,  6,  5,  4,  3,  2,  1,  0,  ]
数据数量：0  isEmpty? true  数据为：[]

转载于:https://my.oschina.net/verynix/blog/365814

总结

以上是生活随笔为你收集整理的(堆)栈的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。