資訊專欄INFORMATION COLUMN
摘要：要實現，至少應該包括出棧操作，彈出棧頂元素。入棧操作查看棧頂元素棧為空另外，實現一個棧，還應該考慮到幾個問題棧的初始大小以及棧滿以后如何新增?？臻g對棧進行更新時需要進行同步有三種實現的方式，數組，容器，以及鏈表的方法。
雖是讀書筆記，但是如轉載請注明出處http://segmentfault.com/blog/exploring/
..拒絕伸手復制黨
想更一進步的支持我，請掃描下方的二維碼，你懂的~
棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。
java 沒有棧這樣的數據結構，如果想利用先進后出（FILO）這樣的數據結構，就必須自己實現。
要實現Stack，至少應該包括：
1. pop() 出棧操作，彈出棧頂元素。
2. push(E e) 入棧操作
3. peek() 查看棧頂元素
4. isEmpty() 棧為空
另外，實現一個棧，還應該考慮到幾個問題：
1. 棧的初始大小以及棧滿以后如何新增?？臻g
2. 對棧進行更新時需要進行同步
有三種實現的方式，數組，容器，以及鏈表的方法。
數據：
javapackage gsm;
import java.util.*;
public class StackArray{
private int[] array;//用數組實現
private int top; //棧頂指針
private final static int size = 100;
public StackArray(){
array = new int[size];
top = -1; //?？盏臅r候
}
//壓棧
public void push(int element){
if(top == size-1){
throw new StackOverflowError();
}
else
array[++top] = element;
}
//彈棧
public int pop(){
if(top == -1){
throw new EmptyStackException();
}
return array[top--];
}
//判斷是否為空
public boolean isEmpty(){
return top == -1;
}
//返回棧頂元素
public Integer peek(){
if(top == -1){
throw new EmptyStackException();
}
return array[top];
}
}
容器
javapackage gsm; public interface Stack{ public T pop(); public void push(T element); public boolean isEmpty(); public T peek(); } package gsm; import java.util.*; public class StackList implements Stack { private List list ; //用容器實現 StackList(){ list = new ArrayList (); } //彈棧 public T pop(){ if(this.isEmpty() == true){ throw new EmptyStackException(); } return list.remove(list.size()-1); } //壓棧 public void push(T element){ list.add(element); } //判斷是否為空 public boolean isEmpty(){ return list.size() == 0; } //返回棧頂元素 public T peek(){ if(this.isEmpty() == true){ throw new EmptyStackException(); } return list.get(list.size()-1); } }
鏈表
javapackage gsm; import java.util.EmptyStackException; public class LinkedStackimplements Stack { //不用容器或者數組等數據結構存儲節點 //Node定義一個節點類 private static class Node{ private U item; //存儲的data private Node next; //類似指針 Node(){ this.item = null; this.next = null; } Node(U item, Node next){ this.item = item; this.next = next; } boolean end(){ return item == null && next == null; } } private Node top ; //棧頂指針 LinkedStack(){ top = new Node (); } //彈棧 public T pop(){ if(this.isEmpty() == true){ throw new EmptyStackException(); } T result = top.item; if(!top.end()) { top = top.next; } return result; } //壓棧 public void push(T element){ top = new Node (element, top); } //判斷是否為空 public boolean isEmpty(){ return top.end(); } //返回棧頂元素 public T peek(){ if(this.isEmpty() == true){ throw new EmptyStackException(); } T result = top.item; return result; } }
可以發現容器果然是java的一個利器，方便高效。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64250.html
摘要：常見數據結構分析及實現說明本文中的代碼是參考編程思想某培訓機構。同時還要分析這些數據結構在時間和空間上的開銷。這種專門研究應用程序中的數據之間的邏輯關系，存儲方式及其操作的學問就是數據結構。 常見數據結構分析及實現 說明 本文中的代碼是參考《Java編程思想》、某培訓機構。 文中的代碼放Github了，有興趣的可以看看，點歌star鼓勵下我。 代碼在Sublime中敲的，坑爹的GBK...
Java是面向對象的語言，對象時Java不可或缺的一個元素，基本數據類型有數組用來存儲，那么對象元素有什么存儲呢，這就是集合，集合是Java非常重要的一塊知識，Java編程思想中的持有對象簡述了集合的相關知識，下面簡述集合的相關功能： showImg(/img/bVC153); 集合類我們通常稱為容器 其實容器只有四種：Map、List、Set和Queue 常用的容器有ArrayList、Lin...
摘要：在改進前使用數組的一個缺點是必須聲明數組的大小，所以棧有確定的容量。待解決的問題建立一個能夠增長或者縮短到任意大小的棧。下邊的圖是觀察時間開銷的另一種方式，表示了入棧操作需要訪問數組的次數。 前言 上一篇：算法分析下一篇：基本排序 本篇內容主要是棧，隊列 (和包)的基本數據類型和數據結構文章里頭所有的對數函數都是以 2 為底關于性能分析，可能還是需要一些數學知識，有時間可以回一下在很多...
閱讀 1525·2023-04-26 00:25
閱讀 917·2021-09-27 13:36
閱讀 933·2019-08-30 14:14
閱讀 2177·2019-08-29 17:10
閱讀 1014·2019-08-29 15:09
閱讀 1949·2019-08-28 18:21
閱讀 970·2019-08-26 13:27
閱讀 977·2019-08-26 10:58
