23

思路：

1.先看下圖

初始棧initStack中存放的數(shù)組中待排序的數(shù)；臨時(shí)棧tempStack中存放的是已經(jīng)排好序的數(shù)。

現(xiàn)在繼續(xù)對(duì)初始棧中的數(shù)進(jìn)行排序，5應(yīng)當(dāng)插入到臨時(shí)棧哪個(gè)位置？

2. 5應(yīng)該插入到8下，3上。

具體如何操作呢？

首先初始棧initStack彈出待排序的數(shù)5，存入變量tmp；而臨時(shí)棧tempStack彈出比5大的數(shù)，并存入初始化棧initStack中。如下圖：

3. 將變量tmp保存的數(shù)插入到臨時(shí)棧tempStack中去，由于初始化棧initStack中8，12是排好序的，可以再直接彈入臨時(shí)棧中，再對(duì)下一個(gè)數(shù)10進(jìn)行如上操作。

代碼如下：

import java.util.*;

public class TwoStacks {

public ArrayList twoStacksSort(int[] numbers) {

ArrayList list = new ArrayList();

//構(gòu)建棧，并初始化棧

Stack initStack = new Stack<>();

for (int i = 0 ; i < numbers.length; i++){

initStack.push(numbers[i]);

}

//構(gòu)建輔助棧,用來存放排好序的數(shù)

Stack tempStack = new Stack<>();

while(!initStack.isEmpty()){

if (tempStack.isEmpty()){

tempStack.push(initStack.pop());

}else {

//新建變量，存儲(chǔ)原始棧中待排序的棧

int tmp = initStack.pop();

//將輔助棧中的排好序中的大于tmp的數(shù)放入原始棧中

while (!tempStack.isEmpty() && tempStack.peek() > tmp){

initStack.push(tempStack.pop());

}

//輔助棧存儲(chǔ)之前保存的變量

tempStack.push(tmp);

}

}

while(!tempStack.isEmpty()){

list.add(tempStack.pop());

}

return list;

}

}

發(fā)表于 2017-06-22 15:53:11

回復(fù)(3)

9

如果嚴(yán)格按照題目中“給定一個(gè)int[]

numbers

(C++中為vector&ltint>)，其中第一個(gè)元素為棧頂”的意思來，這里的第一個(gè)元素應(yīng)該是指數(shù)組的第0項(xiàng)，即第0項(xiàng)為棧頂元素，那么就應(yīng)該倒序來push，討論中很多回答都是正序來push，但這個(gè)影響不大。

雖然Java中Stack繼承Vector，但既然這里題目主要是考察雙棧排序，那就不要用get()，remove()，以及peek()等方法，就只用push()與pop()來完成對(duì)棧中元素的操作。

public class TwoStacks {

public ArrayList twoStacksSort(int[] numbers) {

// write code here

ArrayList result = new ArrayList<>(numbers.length);

//初始化原始棧

Stack stack = new Stack<>();

int index = numbers.length - 1;

for (int i = index; i >= 0; i--) {

stack.push(numbers[i]);

}

Stack resultStack = new Stack<>();//額外的棧

while (!stack.empty()) {

if (resultStack.empty()) {

resultStack.push(stack.pop());

} else {

int a = stack.pop();

int b = resultStack.pop();

if (a < b) {

stack.push(b);

while (!resultStack.empty() && a < (b = resultStack.pop())) {

stack.push(b);

}

}

if (a >= b) {

resultStack.push(b);

}

resultStack.push(a);

}

}

//返回ArrayList結(jié)果

while (!resultStack.empty()) {

result.add(resultStack.pop());

}

return result;

}

發(fā)表于 2016-07-12 15:01:41

回復(fù)(0)

11

public ArrayList twoStacksSort(int[] numbers) {

/*

* 思路：

* 只用兩個(gè)棧排序，一個(gè)是有序的asc，另一個(gè)是無序的buffer就可以實(shí)現(xiàn)對(duì)一個(gè)棧的排序。如何有序，當(dāng)原始棧只有一個(gè)時(shí)就有序了

* numbers中第一個(gè)為棧頂

* 主要是解決buffer棧頂元素放在asc的位置

* 1. buffer棧頂大于等于asc棧頂或asc空

* 直接放

* 2. buffer棧頂小于asc棧頂

* buffer棧頂值出棧，臨時(shí)變量存放buffer棧頂值

* 循環(huán)從asc中拿出值放到buffer直至asc空或滿足1條件

*/

if(numbers == null || numbers.length == 0){

return null;

}

int length = numbers.length;

ArrayList res = new ArrayList(length);

Stack buffer = new Stack();

Stack ascStack = new Stack();

//初始狀態(tài)，buffer中放了length-1個(gè)與numbers逆序的數(shù)串，asc只剩棧底元素

for(int i = 0; i < length-1; i++){

buffer.push(numbers[i]);

}

ascStack.push(numbers[length-1]);

//排序

int bufTop = 0;

while(buffer.size() > 0){

if(ascStack.isEmpty() || buffer.peek() >= ascStack.peek()){

ascStack.push(buffer.pop());

}else{

bufTop = buffer.pop();

int count_curBuffer = buffer.size();

while(!ascStack.isEmpty() && bufTop < ascStack.peek()){

buffer.push(ascStack.pop());

}

ascStack.push(bufTop);

int count_numsFromAsc = buffer.size()-count_curBuffer;

for(int i = 0; i < count_numsFromAsc; i++){

ascStack.push(buffer.pop());

}

}

}

for(int i = 0; i < length; i++){

res.add(ascStack.pop());

}

return res;

}

編輯于 2016-04-18 16:46:24

回復(fù)(0)

9

class TwoStacks {

public:

vector twoStacksSort(vector numbers) {

// write code here

vector forSort;

if(numbers.size() <= 1) return numbers;

forSort.push_back(numbers.back());

numbers.pop_back();

while(numbers.size() > 0)

{

int temp = numbers.back();

numbers.pop_back();

int popNum = 0; // 出棧元素的數(shù)量

while(!forSort.empty() && temp < forSort.back()){

numbers.push_back(forSort.back());

forSort.pop_back();

popNum++;

}

forSort.push_back(temp);

while(popNum > 0){

forSort.push_back(numbers.back());

numbers.pop_back();

popNum--;

}

}

reverse(forSort.begin(),forSort.end());

return forSort;

}

};

插入排，一個(gè)作為備用存儲(chǔ)臨時(shí)元素。

發(fā)表于 2016-01-09 22:36:28

回復(fù)(3)

5

vector twoStacksSort(vector numbers) {

vector stack;

while(!numbers.empty()){

int num = numbers.back();

numbers.pop_back();

while(!stack.empty() && num > stack.back()){

numbers.push_back(stack.back());

stack.pop_back();

}

stack.push_back(num);

}

return stack;

}

發(fā)表于 2017-08-18 16:25:17

回復(fù)(0)

4

import java.util.*;

/*

是左程云《程序員代碼指南》里的

要排序的棧為stack,輔助的棧為help，在stack上執(zhí)行pop操作，彈出的元素記為cur

1.如果cur小于或者等于help的棧頂元素，則將cur直接壓入help(目的是要小的放在下面)

2.如果cur大于help的棧頂元素，則將help的元素逐一彈出，逐一壓入stack，直到1

就是為了將小的數(shù)都放在help的底下

*/

public class TwoStacks {

public ArrayList twoStacksSort(int[] numbers) {

// write code here

Stack stack=new Stack();

Stack help=new Stack();

ArrayList list=new ArrayList();

for(int i=0;i

stack.push(numbers[i]);

while(!stack.isEmpty()){

int cur =stack.pop();

while(!help.isEmpty()&& help.peek()>cur ){ //比cur大 出棧

stack.push(help.pop());

}

help.push(cur);

}

while(!help.isEmpty()){

list.add(stack.push(help.pop()));

}

return list;

}

}

發(fā)表于 2017-07-27 23:13:54

回復(fù)(1)

3

class TwoStacks {

public:

vector twoStacksSort(vector numbers) {

// write code here

stack a;

stack b;

int siz = numbers.size();

for(int i = 0; i < siz; i++){

a.push(numbers[i]);

}

for(int i = 0; i < siz; i++){

int min = a.top();

int count = 0;

for(int j = i; j < siz; j++){

if(a.top() < min){

min = a.top();

}

b.push(a.top());

a.pop();

}

a.push(min);

for(int j = i; j < siz; j++){

if(count == 0 && b.top() == min){

b.pop();

count++;

continue;

}

a.push(b.top());

b.pop();

}

}

for(int i = 0; i < siz; i++){

numbers[i] = a.top();

a.pop();

}

return numbers;

}

};

發(fā)表于 2016-05-09 17:11:31

回復(fù)(1)

5

class TwoStacks {

public:

vector twoStacksSort(vector numbers) {

vector help;

while (!numbers.empty()) {

int cur = numbers.back();

numbers.pop_back();

while (!help.empty() && cur < help.back()) {

numbers.push_back(help.back());

help.pop_back();

}

help.push_back(cur);

}

numbers.clear();

while (!help.empty()) {

numbers.push_back(help.back());

help.pop_back();

}

return numbers;

}

};

好想知道為什么不用stack而要用vector?

vector的第一個(gè)元素是棧頂?shù)脑?#xff0c;操作起來好麻煩啊。

這里我投機(jī)取巧了，把vector的最后的一個(gè)元素當(dāng)做棧頂，每次移動(dòng)棧頂?shù)牟僮骶褪?/p>

pop_back()，每次獲取棧頂元素就直接用back()。

思路很簡單啊，就兩點(diǎn)：

1. 如果棧頂元素cur<=輔助棧help棧頂元素，那么就直接push入輔助棧。

2. 否則，就將輔助棧的棧頂元素push到原棧，直至cur>輔助棧的棧頂元素，此時(shí)再將cur

push入輔助棧。保證輔助棧的數(shù)據(jù)是從棧頂?shù)綏５咨?#xff0c;最后將輔助棧的數(shù)據(jù)逆序push到原棧

就可以使得原棧是降序啦～

編輯于 2017-02-25 10:46:29

回復(fù)(2)

4

public ArrayList twoStacksSort(int[] numbers) {

if(numbers==null || numbers.length<1)

return null;

Stack myStack1 = new Stack();

Stack myStack2 = new Stack();

ArrayList myResult = new ArrayList();

for(int i=0;i

myStack1.push(numbers[i]);

}

while(!myStack1.empty()){

int myTemp=myStack1.pop();

while(!myStack2.empty() && myStack2.peek()>myTemp){

myStack1.push(myStack2.pop());

}

myStack2.push(myTemp);

}

while(!myStack2.empty()){

myResult.add(myStack2.pop());

}

return myResult;

}

發(fā)表于 2015-12-24 21:49:27

回復(fù)(9)

2

//看到題目蛋碎一地，說好的是棧，你給我一個(gè)數(shù)組是什么意思，人與人之間最基本的信任呢

//還只讓我用一個(gè)額外棧，結(jié)果輸出是個(gè)ArrayList，如果照題目意思把ArrayList也當(dāng)成一個(gè)棧。。。那還要啥自行車

//我的內(nèi)心是崩潰的，然后就有了這樣的寫法

//思路，取出棧1中元素放在棧2中，然后棧1再彈出一個(gè)元素，比較這個(gè)元素與棧2頂元素大小，如果大于等于棧二頂元素，就把它壓入棧2中，如果小于，就把棧2中元素彈出一個(gè)壓入棧1中，重復(fù)比較，直到元素大于棧2頂元素或棧2為空，就把它壓入棧2中，實(shí)現(xiàn)排序。

//方法一：

public ArrayList twoStacksSort(int[] numbers) {

ArrayList result=new ArrayList();

if(numbers==null) return result;

int count=0,temp=0,index=0;

while(index

temp=count==0?numbers[index++]:temp;

if(result.size()==0||temp>=result.get(0)){

result.add(0,temp);

// while(count-->0) result.add(0,numbers[index++]);//這句話可以不要

count=0;

}

else {

numbers[--index]=result.remove(0);

count++;

}

}

return result;

}

//方法二，原理同方法一，不讓我用棧我偏用，我是菜鳥我怕誰QAQ

public ArrayList twoStacksSort(int[] numbers) {

ArrayList result=new ArrayList();

if(numbers==null) return result;

Stack stack= new Stack();

Stack resultStack= new Stack();

for(int i=0;i

int count=0,temp=0;

while(!stack.isEmpty()){

temp=count==0?stack.pop():temp;

if(resultStack.isEmpty()||temp>=resultStack.peek()){

resultStack.push(temp);

// while(count-->0) resultStack.push(stack.pop());//這句話可以不要，不過不知道為什么加上這句話，運(yùn)行占用內(nèi)存是1000多K,不加是3000多K

count=0;

}

else {

stack.push(resultStack.pop());

count++;

}

}

while(!resultStack.isEmpty()) result.add(resultStack.pop());

return result;

}

編輯于 2017-05-12 20:24:46

回復(fù)(0)

2

//解題思路：一個(gè)原棧，一個(gè)輔助棧，我們可以將原棧中的元素依次出棧和輔助棧中的棧頂元素進(jìn)行比較，如果原大于輔，將原出棧到輔助中，

發(fā)表于 2016-08-16 15:46:44

回復(fù)(0)

2

class TwoStacks {

public:

vector twoStacksSort(vector numbers) {

// write code here

vector temp;

temp.push_back(numbers.back());

numbers.pop_back();

while(!numbers.empty()){

int n=numbers.back();

numbers.pop_back();

while(!temp.empty()&&n>temp.back()){//下沉操作，彈出到temp中不小于n的位置

numbers.push_back(temp.back());//temp彈出的數(shù)放到numbers中

temp.pop_back();

}

temp.push_back(n);

}

return temp;

}

};

發(fā)表于 2016-06-01 11:17:36

回復(fù)(3)

6

python one line solution: return sorted(numbers,reverse=True)

發(fā)表于 2017-10-01 20:28:53

回復(fù)(1)

3

public ArrayList twoStacksSort(int[] numbers) {

// write code here

ArrayList stack=new ArrayList();

int temp,i;

for(i=0;i

temp=numbers[i];

while(!stack.isEmpty()&&stack.get(stack.size()-1)

numbers[i--]=stack.get(stack.size()-1);

stack.remove(stack.size()-1);

}

stack.add(temp);

}

return stack;

}

發(fā)表于 2016-03-15 13:51:09

回復(fù)(2)

1

設(shè)置一個(gè)臨時(shí)棧存放已經(jīng)排序好的序列。如果臨時(shí)棧為空，則從初始棧pop一個(gè)壓入臨時(shí)棧，如果不為空，則初始棧pop出一個(gè)元素與臨時(shí)棧最后一個(gè)元素(棧底)比較 class?TwoStacks:

def?twoStacksSort(self,?numbers):

#return?sorted(numbers,reverse=True)

if?not?numbers&nbs***bsp;len(numbers)==1:

return?numbers

res?=?[]

while?numbers:

if?not?res:

res.append(numbers.pop())

else:

pre?=?numbers.pop()

if?pre<=res[-1]:

res.append(pre)

else:

while?res?and?res[-1]

numbers.append(res.pop())

res.append(pre)

return?res

發(fā)表于 2020-06-16 10:22:39

回復(fù)(0)

1

class?TwoStacks?{

public:

vector?twoStacksSort(vector?numbers)?{

vector?temp_stack;

int?temp;

while(!numbers.empty()){

temp?=?numbers.back();

numbers.pop_back();

while(!temp_stack.empty()?&&?temp_stack.back()?

numbers.push_back(temp_stack.back());

temp_stack.pop_back();

}

temp_stack.push_back(temp);

}

return?temp_stack;

}

};

編輯于 2019-10-30 17:54:14

回復(fù)(0)

1

class TwoStacks {

public:

vector twoStacksSort(vector numbers) {

vector res;

while (!numbers.empty()) {

int num = numbers.back();

numbers.pop_back();

while (!res.empty() && res.back() < num) {

numbers.push_back(res.back());

res.pop_back();

}

res.push_back(num);

}

return res;

}

};

運(yùn)行時(shí)間：6ms

占用內(nèi)存：504k

發(fā)表于 2018-12-24 17:03:09

回復(fù)(1)

1

純用 vector 時(shí)間復(fù)雜度O(N^2)，空間復(fù)雜度O(N)

發(fā)表于 2018-03-29 12:13:58

回復(fù)(0)

1

//構(gòu)建一個(gè)輔助棧存放排好序的 和 一個(gè)變量存放臨時(shí)值

public ArrayList twoStacksSort(int[] numbers) {

ArrayList res = new ArrayList<>();

if (numbers == null || numbers.length == 0) return res;

Stack stack1 = new Stack<>();//原始棧

for (int i = numbers.length - 1; i >= 0; i--)

stack1.push(numbers[i]);

int temp;//存放臨時(shí)值

Stack stack2 = new Stack<>();

while (stack1.size() != 0) {

temp = stack1.pop();

while (stack2.size() != 0 && stack2.peek() > temp) {//輔助棧不為空，且棧頭元素比臨時(shí)值大

stack1.push(stack2.pop());

}

stack2.push(temp);

}

while (stack2.size() != 0) {

res.add(stack2.pop());

}

return res;

}

發(fā)表于 2018-03-14 10:07:38

回復(fù)(0)

1

class TwoStacks {

public:

vector twoStacksSort(vector num) {

vector res;

stack tempsta;

while(num.size()){

while(!res.size() || (num.size() && num[0]>res[0])){

res.insert(res.begin(),num[0]);

num.erase(num.begin());

}

if(num.size()){

while(res.size() && num[0]

tempsta.push(res[0]);

res.erase(res.begin());

}

res.insert(res.begin(),num[0]);

num.erase(num.begin());

while(!tempsta.empty()){ res.insert(res.begin(),tempsta.top()); tempsta.pop(); }

}

}

return res;

}

};

發(fā)表于 2017-08-23 21:36:55

回復(fù)(0)

總結(jié)

以上是生活随笔為你收集整理的双栈排序java_双栈排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。