A. java 基礎堆棧
你就簡單的來理解就可以了
堆棧就是兩種存放數據的方式
不要new直接來定義的是棧
用new來定義的就是堆
首先來講解棧
棧的優勢是，存取速度比堆要快。但缺點是缺乏靈活性
而堆測試速度慢
但是靈活性好
比如八大基本數據類型
在你int
sum
=
0;的時候
就是sum是一個指向
int
類型的引用，指向0這個字面值
你在頂一個
int
i=0;他會去找有沒有0
有的話就會指向它
所以棧具有共享數據的特性
而當你String
str
=
new
String("a");的時候
它就會在堆中建立一個對象
其實你就理解成兩種方式的存放數據的方式就行
B. 用java編寫出來：用數組實現一個棧
public class Stack {
private Object[] stack;
//這個不需要;
//private int top = 0; //初始化棧頂
//這個也不需要;
//寫一個棧出來,最好是可以動態的,可以自己改變大小的,即數組的長度;
//private int size = 0; // 初始化大小
//元素個數;
private int size;
//默認長度為10;
public Stack(){
this(10);
}
//也可以自己設置長度,即容量;
public Stack(int len){
stack = new Object[len];
}
//返回元素個數;
public int size(){
return size;
}
//返回數組長度,即容量;
public int capacity(){
return stack.length;
}
//實現動態的數組;
public void ensureCapacity(){
if(size() == capacity()){
Object[] newStack = new Object[size() * 3 / 2 + 1];
System.array(stack, 0, newStack, 0, size());
stack = newStack;
}
}
//入棧;
public void push(Object o){
size++;
ensureCapacity();
stack[size - 1] = o;
}
/*
public void push(Object object) {
if (isFull()) {
System.out.println("棧滿! 入棧失敗");
}
stack[top++] = object;
}
*/
//判空;
public boolean isEmpty(){
return size == 0;
}
//出棧;
public Object pop(){
//首先要判空;
if(isEmpty()){
throw new ("不能為空");
}
Object o = stack[--size];
stack[size] = null;
return o;
}
/*
// 出棧
public Object pop() {
Object object = stack[--top];
stack[top] = null;
return object;
}
*/
/*
// 計算棧當前大小
public int size() {
return top;
}
// 判斷是否是空棧
public boolean isEmpey() {
return top == 0;
}
// 判斷是否棧滿
public boolean isFull() {
return top >= size;
}
public Stack(int size) {
this.size = size;
}
*/
public static void main(String[] args) {
Stack stack = new Stack(3);
String[] data = new String[] { "a", "b", "c" };
for (int i = 0; i < data.length; i++) {
stack.push(data[i]);
System.out.println(data[i] + "");
}
System.out.println("***********");
while (!stack.isEmpty()) {
System.out.println(stack.pop() + "");
}
//}
}
}
你自己對比一下,我是在你的裡面修改的
C. Java編程思想里的泛型實現一個堆棧類 分享
覺得作者寫得太好了，不得不收藏一下。
對這個例子的理解：
//類型參數不能用基本類型，T和U其實是同一類型。
//每次放新數據都成為新的top，把原來的top往下壓一級，通過指針建立鏈接。
//末端哨兵既是默認構造器創建出的符合end()返回true的節點。
復制代碼
代碼如下:
//:
generics/LinkedStack.java
//
A
stack
implemented
with
an
internal
linked
structure.
package
generics;
public
class
LinkedStack<T>
{
private
static
class
Node<U>
{
U
item;
Node<U>
next;
Node()
{
item
=
null;
next
=
null;
}
Node(U
item,
Node<U>
next)
{
this.item
=
item;
this.next
=
next;
}
boolean
end()
{
return
item
==
null
&&
next
==
null;
}
}
private
Node<T>
top
=
new
Node<T>();
//
End
sentinel
public
void
push(T
item)
{
top
=
new
Node<T>(item,
top);
}
public
T
pop()
{
T
result
=
top.item;
if(!top.end())
top
=
top.next;
return
result;
}
public
static
void
main(String[]
args)
{
LinkedStack<String>
lss
=
new
LinkedStack<String>();
for(String
s
:
"Phasers
on
stun!".split("
"))
lss.push(s);
String
ss;
while((ss
=
lss.pop())
!=
null)
System.out.println(ss);
//-----
if
put
integer
into
the
LinkedList
LinkedStack<Integer>
lii
=
new
LinkedStack<Integer>();
for(Integer
i
=
0;
i
<
10;
i++){
lii.push(i);
}
Integer
end;
while((end
=
lii.pop())
!=
null)
System.out.println(end);
//-----
integer
test
end!
}
}
/*
Output:
stun!
on
Phasers
*/
D. java語言中用LinkList實現堆棧
棧和隊列是兩種特殊的線性表，它們的邏輯結構和線性表相同，只是其運算規則較線性表有更多的限制，故又稱它們為運算受限的線性表。
LinkedList數據結構是一種雙向的鏈式結構，每一個對象除了數據本身外，還有兩個引用，分別指向前一個元素和後一個元素，和數組的順序存儲結構（如：ArrayList）相比，插入和刪除比較方便，但速度會慢一些。
棧的定義
棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。
(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。
(2)當表中沒有元素時稱為空棧。
(3)棧為後進先出（Last In First Out）的線性表，簡稱為LIFO表。
棧的修改是按後進先出的原則進行。每次刪除（退棧）的總是當前棧中"最新"的元素，即最後插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最後才能刪除。
實現代碼：
package com.weisou.dataStruct;
import java.util.LinkedList;
@SuppressWarnings("unchecked")
public class MyStack {
LinkedList linkList = new LinkedList<Object>();
public void push(Object object) {
linkList.addFirst(object);
}
public boolean isEmpty() {
return linkList.isEmpty();
}
public void clear() {
linkList.clear();
}
// 移除並返回此列表的第一個元素
public Object pop() {
if (!linkList.isEmpty())
return linkList.removeFirst();
return "棧內無元素";
}
public int getSize() {
return linkList.size();
}
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(2);
myStack.push(3);
myStack.push(4);
System.out.println(myStack.pop());
System.out.println(myStack.pop());
}
}
隊列定義
隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表
（1）允許刪除的一端稱為隊頭（Front）。
（2）允許插入的一端稱為隊尾（Rear）。
（3）當隊列中沒有元素時稱為空隊列。
（4）隊列亦稱作先進先出（First In First Out）的線性表，簡稱為FIFO表。
實現代碼：
package com.weisou.dataStruct;
import java.util.LinkedList;
/**
*
* @author gf
* @date 2009-11-13
*/
public class MyQueue {
LinkedList linkedList = new LinkedList();
//隊尾插
public void put(Object o){
linkedList.addLast(o);
//隊頭取 取完並刪除
public Object get(){
if(!linkedList.isEmpty())
return linkedList.removeFirst();
else
return "";
}
public boolean isEmpty(){
return linkedList.isEmpty();
}
public int size(){
return linkedList.size();
}
public void clear(){
linkedList.clear();
}
/**
* @param args
*/
public static void main(String[] args) {
MyQueue myQueue= new MyQueue();
myQueue.put(1);
myQueue.put(2);
myQueue.put(3);
System.out.println(myQueue.get());
}
}
E. Java隊列入隊和堆棧出棧演算法實現
class LinkedList //定義雙項鏈表{char data;LinkedList back;LinkedList forward;}interface Access //定義從隊列和棧存取操作的介面{void put(char c);char get();}class Queue implements Access //定義隊列類{private LinkedList QHead=new LinkedList();private LinkedList QRear=QHead; //初始化隊頭和隊尾public void put(char c) //實現向隊列存數的方法{QRear.forward=new LinkedList();QRear.forward.data=c;QRear.forward.back=QRear;QRear=QRear.forward;}public char get() //實現從隊列取數的方法{if(QHead!=QRear) //如果隊列不為空則取數{QHead.forward.back=null;QHead=QHead.forward;return QHead.data;}else{System.out.println("The queue is empty! ");return '\0';}}}class Stack implements Access //定義棧類{private LinkedList bottom=new LinkedList();private LinkedList top=bottom; //初始化棧頂與斬底public void put(char c) //實現從棧中存數的方法{top.forward=new LinkedList();top.forward.data=c;top.forward.back=top;top=top.forward;}public char get() //實現從棧中取數的方法{if(top!=bottom) //如果棧不為空則取數{char ch=top.data;top.back.forward=null;top=top.back;return ch;}else{System.out.println("The stack is empty! ");return '\0';}}}public class StackQueue{public static void main(String[] args){char ch;Queue q=new Queue(); //創建一個隊列qStack s=new Stack(); //創建一個棧sq.put('x');q.put('y');q.put('z'); //向隊列q存入3個字元s.put('x');s.put('y');s.put('z'); //向棧s存入3個字元System.out.println("Queue: ");if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);//從隊列q中取數並顯示System.out.println("Stack: ");if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);//從棧s中取數並顯示}}引自： http://wenwen.soso.com/z/q104863.htm?ch=w.xg.ll
F. 用一維整數數組實現數據結構中的堆棧(Stack)。（用java語言）
public class IntStack {
private int[] stack;
private int top;
/**
*初始化棧，傳入一個非負的整數，否則拋出一個錯誤
*/
public IntStack(int size) throws StackErrorException{
if(size<0){
throw new StackErrorException("錯誤的大小");
}
init(size);
}
private void init(int size) {
stack = new int[size];
top = 0;
}
/**
*判斷棧是否為空，true則為空，反之則反
*/
public boolean isEmpty(){
return top==0;
}
/**
*判斷棧是否已滿，true則已滿，反之則反
*/
public boolean isFull(){
return top==stack.length;
}
/**
*向棧頂添加元素，滿則拋出異常
*/
public void push(int value) throws StackErrorException{
if(isFull()){
throw new StackErrorException("棧已滿");
}
stack[top++] = value;
}
/**
*移除棧頂元素並返回，空則拋出異常
*/
public int pop() throws StackErrorException{
if(isEmpty()){
throw new StackErrorException("已到棧底!");
}
return stack[--top];
}
/**
*返回棧頂元素，空則拋出異常
*/
public int peek() throws StackErrorException{
if(isEmpty()){
throw new StackErrorException("已在棧底!");
}
return stack[top-1];
}
/**
*返回棧大小
*/
public int size(){
return stack.length;
}
class StackErrorException extends Exception{
public StackErrorException(String msg) {
super(msg);
}
}
}