用兩個棧實作隊列/用兩個隊列實作棧

用兩個棧實作隊列

1、棧的特點就是先進後出，而隊列要做到先進先出，是以兩個棧一個用來做入隊操作（stack1）一個用來做出隊操作（stack2）然後再把沒有删完的元素再放到stack1中。具體代碼實作過程如下：

private T[] stack;// 存儲棧的元素的數組

// top表示棧頂的位置

private int top;

public SeqStack(){

this(10);

}

public SeqStack(int size){

this.stack = (T[])new Object[size];

this.top = 0;

}

public void push(T val){

if(full()){

// 棧如果滿了，要進行記憶體2倍擴容

this.stack = Arrays.copyOf(this.stack,

this.stack.length*2);

}

this.stack[this.top] = val;

this.top++;

}

public void pop(T val){

if(empty())

return;

this.top–;

if(this.top < this.stack.length/2){

this.stack = Arrays.copyOf(this.stack, this.stack.length/2);

}

}

public T top(){

return this.stack[this.top - 1];

}

public boolean full(){

return this.top == this.stack.length;

}

public boolean empty(){

return this.top == 0;

-------------------------然後再實作兩個棧實作一個隊列-------------------------------

class Quene {

private SeqStack stack1;//入隊操作

private SeqStack stack2;//出隊操作

public void offer(E val){

stack1.push(val);

}

public E poll(E val){

E data=null;

while (!stack1.empty()){

data= stack1.pop();

stack2.push(data);

if(stack1.empty()){

break;

}

}

while (!stack2.empty()){

stack2.pop(val);

stack1.push(stack2.pop());

}

return data;

}

用兩個隊列實作棧

首先棧的特點是先進後出，隊列的特點是先進先出，是以這裡用兩個隊列，一個實作入棧操作，一個進行出棧操作。

public void offer(E val){

if(full()){

// 擴容

E[] newQue = Arrays.copyOf(this.que,

this.que.length*2);

int index = 0;

for(int i=this.front;

i != this.rear;

i=(i+1)%this.que.length){

newQue[index++] = this.que[i];

}

this.front = 0;

this.rear = index;

this.que = newQue;

}

this.que[this.rear] = val;

this.rear = (this.rear+1)%this.que.length;

}

/**
 * 出隊操作，并把出隊的元素的值傳回
 */
public E poll(){
    if(empty()){
        return null;
    }
    E front = this.que[this.front];
    this.front = (this.front+1)%this.que.length;
    return front;
}

/**
 * 檢視隊頭元素
 * @return
 */
public E peek(){
    if(empty()){
        return null;
    }
    return this.que[this.front];
}

/**
 * 判斷隊滿
 * @return
 */
public boolean full(){
    return (this.rear+1)%this.que.length == this.front;
}

/**
 * 判斷隊空
 * @return
 */
public boolean empty(){
    return this.rear == this.front;
}
           

}

----------------------------------兩個隊列實作一個棧  -----------------------------------
class SedStack <E> {
Queue<E> que1 = new Queue();
Queue<E> que2 = new Queue();

public void SedStack() {
    this.que1 = que1;
    this.que2 = que2;
}

public void push(E val) {
    que1.offer(val);
}

public E pop() {
    E data = null;
    while (!que1.empty()) {
        data = que1.poll();
        que2.offer(data);
        if (que1.empty()) {
            break;
        }
        while (!que2.empty()) {
            data = que2.poll();
            que1.offer(data);
        }
    }


    return data;
}

public E top() {
    E data = null;
    while (!que1.empty()) {
        data = que1.poll();
        que2.offer(data);
    }
    while (!que2.empty()) {
        data = que2.poll();
        que1.offer(data);
    }
    return data;
}
public boolean full(){
   return que1.full();
}
public boolean empty(){
    return que1.empty();
}
           

}