建站
咨詢
售后
建站咨詢
新聞中心
棧的實現(xiàn)
我們提供的服務有：網(wǎng)站設計制作、成都做網(wǎng)站、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認證、應城ssl等。為上千余家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務，是有科學管理、有技術的應城網(wǎng)站制作公司
棧是一種先進后出的數(shù)據(jù)結構, 首先定義了棧需要實現(xiàn)的接口：
- public interface MyStack
{ - /**
- * 判斷棧是否為空
- */
- boolean isEmpty();
- /**
- * 清空棧
- */
- void clear();
- /**
- * 棧的長度
- */
- int length();
- /**
- * 數(shù)據(jù)入棧
- */
- boolean push(T data);
- /**
- * 數(shù)據(jù)出棧
- */
- T pop();
- }
棧的數(shù)組實現(xiàn)，底層使用數(shù)組：
- public class MyArrayStack
implements MyStack { - private Object[] objs = new Object[16];
- private int size = 0;
- @Override
- public boolean isEmpty() {
- return size == 0;
- }
- @Override
- public void clear() {
- // 將數(shù)組中的數(shù)據(jù)置為null, 方便GC進行回收
- for (int i = 0; i < size; i++) {
- objs[size] = null;
- }
- size = 0;
- }
- @Override
- public int length() {
- return size;
- }
- @Override
- public boolean push(T data) {
- // 判斷是否需要進行數(shù)組擴容
- if (size >= objs.length) {
- resize();
- }
- objs[size++] = data;
- return true;
- }
- /**
- * 數(shù)組擴容
- */
- private void resize() {
- Object[] temp = new Object[objs.length * 3 / 2 + 1];
- for (int i = 0; i < size; i++) {
- temp[i] = objs[i];
- objs[i] = null;
- }
- objs = temp;
- }
- @SuppressWarnings("unchecked")
- @Override
- public T pop() {
- if (size == 0) {
- return null;
- }
- return (T) objs[--size];
- }
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder();
- sb.append("MyArrayStack: [");
- for (int i = 0; i < size; i++) {
- sb.append(objs[i].toString());
- if (i != size - 1) {
- sb.append(", ");
- }
- }
- sb.append("]");
- return sb.toString();
- }
- }
棧的鏈表實現(xiàn)，底層使用鏈表：
- public class MyLinkedStack
implements MyStack { - /**
- * 棧頂指針
- */
- private Node top;
- /**
- * 棧的長度
- */
- private int size;
- public MyLinkedStack() {
- top = null;
- size = 0;
- }
- @Override
- public boolean isEmpty() {
- return size == 0;
- }
- @Override
- public void clear() {
- top = null;
- size = 0;
- }
- @Override
- public int length() {
- return size;
- }
- @Override
- public boolean push(T data) {
- Node node = new Node();
- node.data = data;
- node.pre = top;
- // 改變棧頂指針
- top = node;
- size++;
- return true;
- }
- @Override
- public T pop() {
- if (top != null) {
- Node node = top;
- // 改變棧頂指針
- top = top.pre;
- size--;
- return node.data;
- }
- return null;
- }
- /**
- * 將數(shù)據(jù)封裝成結點
- */
- private final class Node {
- private Node pre;
- private T data;
- }
- }
兩種實現(xiàn)的比較，主要比較數(shù)據(jù)入棧和出棧的速度：
- @Test
- public void testSpeed() {
- MyStack
stack = new MyArrayStack (); - int num = 10000000;
- long start = System.currentTimeMillis();
- for (int i = 0; i < num; i++) {
- stack.push(new Person("xing", 25));
- }
- long temp = System.currentTimeMillis();
- System.out.println("push time: " + (temp - start));
- while (stack.pop() != null)
- ;
- System.out.println("pop time: " + (System.currentTimeMillis() - temp));
- }
MyArrayStack中入棧和出棧10,000,000條數(shù)據(jù)的時間：
push time：936
pop time：47
將MyArrayStack改為MyLinkedStack后入棧和出棧的時間：
push time：936
pop time：126
可見兩者的入棧速度差不多，出棧速度MyArrayStack則有明顯的優(yōu)勢。
為什么測試結果是這樣的？可能有些朋友的想法是數(shù)組實現(xiàn)的棧應該具有更快的遍歷速度，但增刪速度應該比不上鏈表實現(xiàn)的棧才對。但是棧中數(shù)據(jù)的增刪具有特殊性：只在棧頂入棧和出棧。也就是說數(shù)組實現(xiàn)的棧在增加和刪除元素時并不需要移動大量的元素，只是在數(shù)組擴容時需要進行復制。而鏈表實現(xiàn)的棧入棧和出棧時都需要將數(shù)據(jù)包裝成Node或者從Node中取出數(shù)據(jù)，還需要維護棧頂指針和前驅指針。
棧的應用舉例
1. 將10進制正整數(shù)num轉換為n進制
- private String conversion(int num, int n) {
- MyStack
myStack = new MyArrayStack (); - Integer result = num;
- while (true) {
- // 將余數(shù)入棧
- myStack.push(result % n);
- result = result / n;
- if (result == 0) {
- break;
- }
- }
- StringBuilder sb = new StringBuilder();
- // 按出棧的順序倒序排列即可
- while ((result = myStack.pop()) != null) {
- sb.append(result);
- }
- return sb.toString();
- }
2. 檢驗符號是否匹配. '['和']', '('和')'成對出現(xiàn)時字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的。
遍歷字符串的每一個char, 將char與棧頂元素比較. 如果char和棧頂元素配對, 則char不入棧, 否則將char入棧. 當遍歷完成時棧為空說明字符串是合法的。
- public boolean isMatch(String str) {
- MyStack
myStack = new MyArrayStack (); - char[] arr = str.toCharArray();
- for (char c : arr) {
- Character temp = myStack.pop();
- // 棧為空時只將c入棧
- if (temp == null) {
- myStack.push(c);
- }
- // 配對時c不入棧
- else if (temp == '[' && c == ']') {
- }
- // 配對時c不入棧
- else if (temp == '(' && c == ')') {
- }
- // 不配對時c入棧
- else {
- myStack.push(temp);
- myStack.push(c);
- }
- }
- return myStack.isEmpty();
- }
3. 行編輯: 輸入行中字符'#'表示退格, '@'表示之前的輸入全都無效。
使用棧保存輸入的字符, 如果遇到'#'就將棧頂出棧, 如果遇到@就清空棧. 輸入完成時將棧中所有字符出棧后反轉就是輸入的結果：
- private String lineEdit(String input) {
- MyStack
myStack = new MyArrayStack (); - char[] arr = input.toCharArray();
- for (char c : arr) {
- if (c == '#') {
- myStack.pop();
- } else if (c == '@') {
- myStack.clear();
- } else {
- myStack.push(c);
- }
- }
- StringBuilder sb = new StringBuilder();
- Character temp = null;
- while ((temp = myStack.pop()) != null) {
- sb.append(temp);
- }
- // 反轉字符串
- sb.reverse();
- return sb.toString();
- }
網(wǎng)站題目：棧的Java實現(xiàn)和棧的應用舉例
鏈接地址：http://www.dlmjj.cn/article/djdesec.html
