Как отсортировать стек, используя только операции со стеком?
Я нашел этот вопрос в Интернете.
Учитывая стек S, напишите программу на C для сортировки стека (в порядке возрастания). Нам не разрешается делать какие-либо предположения о том, как реализован стек. Используются только следующие функции:
Push
Pop
Top
IsEmpty
IsFull
Я думаю, что мы можем построить кучу и отсортировать ее. Какое оптимальное решение для этого?
16 ответов
Предполагая, что единственной структурой данных, разрешенной здесь, является стек, тогда вы можете использовать 2 стека.
Итерируйте, пока исходный стек не станет пустым, и в каждой итерации извлекайте элемент из исходного стека, в то время как верхний элемент во втором стеке больше, чем удаленный элемент, извлекайте второй стек и переносите его в исходный стек. Теперь вы можете перенести элемент, который вы изначально извлекли из исходного стека, во второй стек.
Временная сложность этого подхода составляет O(N^2).
Код C для реализации этого алгоритма будет (извините мои ржавые навыки C):
void SortStack(struct Stack * orig_stack)
{
struct Stack helper_stack;
while (!IsEmpty(orig_stack))
{
int element = Pop(orig_stack);
while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
{
Push(orig_stack, Pop(&helper_stack));
}
Push(&helper_stack, element);
}
while (!IsEmpty(&helper_stack))
{
Push(orig_stack, Pop(&helper_stack));
}
}
Учитывая эти операции стека, вы можете написать рекурсивную вставку сортировки.
void sort(stack s) {
if (!IsEmpty(s)) {
int x = Pop(s);
sort(s);
insert(s, x);
}
}
void insert(stack s, int x) {
if (!IsEmpty(s)) {
int y = Top(s);
if (x < y) {
Pop(s);
insert(s, x);
Push(s, y);
} else {
Push(s, x);
}
} else {
Push(s, x);
}
}
Это можно сделать рекурсивно, используя один и тот же стек. O(n^2) я кодировал это в C++, но преобразование в C тривиально. Мне просто нравятся шаблоны, а вы отметили свой вопрос как C++
template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
if(element > stack.Top())
{
T top = stack.Pop();
Insert(element, stack);
stack.Push(top);
}
else
{
stack.Push(element);
}
}
template<typename T>
void StackSort(Stack<T>& stack)
{
if(!stack.IsEmpty())
{
T top = stack.Pop();
StackSort(stack);
Insert(top, stack);
}
}
Отредактировано, чтобы вернуть мой голос! :))
Сортировка блинов - еще один интересный способ сделать это: http://en.wikipedia.org/wiki/Pancake_sorting.
Модифицированный код из ответа T33C
(дано до того, как Сванте исправил языковой тег с C++ до c):stack.top() можно проверить только если !stack.empty()
void insert(int element, stack<int> &stack) {
if (!stack.empty() && element > stack.top()) {
int top = stack.top();
stack.pop();
insert(element, stack);
stack.push(top);
}
else {
stack.push(element);
}
}
void sortStack(stack<int> & stack) {
if (!stack.empty()) {
int top = stack.top();
stack.pop();
sortStack(stack);
insert(top, stack);
}
}
3 стека сортировки с использованием многофазной сортировки слиянием
Это должен быть самый быстрый способ реализации сортировки из трех стеков. Цель состоит в том, чтобы получить последовательность по возрастанию, поскольку элементы извлекаются из отсортированного стека.
Статья Wiki для многофазной сортировки слиянием (с использованием массивов):
http://en.wikipedia.org/wiki/Polyphase_merge_sort
Пример кода C++ для трехфазной сортировки стека, с использованием указателей, указателя в качестве указателя стека для каждого стека и указателя на конец каждого прогона и конец каждого стека. Указатель размера серии используется для отслеживания того, когда размер серии увеличивается или уменьшается в середине стека. Флаг нисходящей последовательности используется для отслеживания, являются ли последовательности нисходящими или восходящими, когда данные передаются между стеками. Он инициализируется в начале, а затем чередуется после объединения каждой пары прогонов.
typedef unsigned int uint32_t;
static size_t fibtbl[48] =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903,2971215073};
// binary search: return index of largest fib() <= n
size_t flfib(size_t n)
{
size_t lo = 0;
size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]);
while((hi - lo) > 1){
size_t i = (lo + hi)/2;
if(n < fibtbl[i]){
hi = i;
continue;
}
if(n > fibtbl[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort array using 3 arrays as stacks, a is source
uint32_t * ppmrg3s(uint32_t a[], uint32_t b[], uint32_t c[], size_t n)
{
if(n < 2)
return a+n;
uint32_t *asp = a; // a stack ptr
uint32_t *aer; // a end run
uint32_t *aes = a + n; // a end
uint32_t *bsp = b + n; // b stack ptr
uint32_t *ber; // b end run
uint32_t *bes = b + n; // b end
uint32_t *csp = c + n; // c stack ptr
uint32_t *ces = c + n; // c end
uint32_t *rsp = 0; // run size change stack ptr
size_t ars = 1; // run sizes
size_t brs = 1;
size_t scv = 0-1; // size change increment / decrement
bool dsf; // == 1 if descending sequence
{ // block for local variable scope
size_t f = flfib(n); // fibtbl[f+1] > n >= fibtbl[f]
dsf = ((f%3) == 0); // init compare flag
if(fibtbl[f] == n){ // if exact fibonacci size, move to b
for(size_t i = 0; i < fibtbl[f-1]; i++)
*(--bsp) = *(asp++);
} else { // else move to b, c
// update compare flag
dsf ^= (n - fibtbl[f]) & 1;
// move excess elements to b
aer = a + n - fibtbl[f];
while (asp < aer)
*(--bsp) = *(asp++);
// move dummy count elements to c
aer = a + fibtbl[f - 1];
while (asp < aer)
*(--csp) = *(asp++);
rsp = csp; // set run size change ptr
}
} // end local variable block
while(1){ // setup to merge pair of runs
if(asp == rsp){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
rsp = csp;
}
if(bsp == rsp){
brs += scv;
scv = 0-scv;
rsp = csp;
}
aer = asp + ars; // init end run ptrs
ber = bsp + brs;
while(1){ // merging pair of runs
if(dsf ^ (*asp <= *bsp)){ // if a <= b
*(--csp) = *(asp++); // move a to c
if(asp != aer) // if not end a run
continue; // continue back to compare
do // else move rest of b run to c
*(--csp) = *(bsp++);
while (bsp < ber);
break; // and break
} else { // else a > b
*(--csp) = *(bsp++); // move b to c
if(bsp != ber) // if not end b run
continue; // continue back to compare
do // else move rest of a run to c
*(--csp) = *(asp++);
while (asp < aer);
break; // and break
}
} // end merging pair of runs
dsf ^= 1; // toggle compare flag
if(bsp == bes){ // if b empty
if(asp == aes) // if a empty, done
break;
std::swap(bsp, csp); // swap b, c
std::swap(bes, ces);
brs += ars; // update run size
} else { // else b not empty
if(asp != aes) // if a not empty
continue; // continue back to setup next merge
std::swap(asp, csp); // swap a, c
std::swap(aes, ces);
ars += brs; // update run size
}
}
return csp; // return ptr to sorted array
}
Пример кода Java для сортировки с использованием пользовательского стекового класса (xstack), который включает функцию подкачки.
static final int[] FIBTBL =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903};
// return index of largest fib() <= n
static int flfib(int n)
{
int lo = 0;
int hi = 47;
while((hi - lo) > 1){
int i = (lo + hi)/2;
if(n < FIBTBL[i]){
hi = i;
continue;
}
if(n > FIBTBL[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort using 3 stacks
static void ppmrg3s(xstack a, xstack b, xstack c)
{
if(a.size() < 2)
return;
int ars = 1; // init run sizes
int brs = 1;
int asc = 0; // no size change
int bsc = 0;
int csc = 0;
int scv = 0-1; // size change value
boolean dsf; // == 1 if descending sequence
{ // block for local variable scope
int f = flfib(a.size()); // FIBTBL[f+1] > size >= FIBTBL[f]
dsf = ((f%3) == 0); // init compare flag
if(FIBTBL[f] == a.size()){ // if exact fibonacci size,
for (int i = 0; i < FIBTBL[f - 1]; i++) { // move to b
b.push(a.pop());
}
} else { // else move to b, c
// update compare flag
dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1);
// i = excess run count
int i = a.size() - FIBTBL[f];
// j = dummy run count
int j = FIBTBL[f + 1] - a.size();
// move excess elements to b
do{
b.push(a.pop());
}while(0 != --i);
// move dummy count elements to c
do{
c.push(a.pop());
}while(0 != --j);
csc = c.size();
}
} // end block
while(true){ // setup to merge pair of runs
if(asc == a.size()){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
asc = 0;
csc = c.size();
}
if(bsc == b.size()){
brs += scv;
scv = 0-scv;
bsc = 0;
csc = c.size();
}
int arc = ars; // init run counters
int brc = brs;
while(true){ // merging pair of runs
if(dsf ^ (a.peek() <= b.peek())){
c.push(a.pop()); // move a to c
if(--arc != 0) // if not end a
continue; // continue back to compare
do{ // else move rest of b run to c
c.push(b.pop());
}while(0 != --brc);
break; // and break
} else {
c.push(b.pop()); // move b to c
if(0 != --brc) // if not end b
continue; // continue back to compare
do{ // else move rest of a run to c
c.push(a.pop());
}while(0 != --arc);
break; // and break
}
} // end merging pair of runs
dsf ^= true; // toggle compare flag
if(b.empty()){ // if end b
if(a.empty()) // if end a, done
break;
b.swap(c); // swap b, c
brs += ars;
if (0 == asc)
bsc = csc;
} else { // else not end b
if(!a.empty()) // if not end a
continue; // continue back to setup next merge
a.swap(c); // swap a, c
ars += brs;
if (0 == bsc)
asc = csc;
}
}
a.swap(c); // return sorted stack in a
}
/* the basic idea is we go on
* popping one element (o) from the original stack (s) and we
* compare it with the new stack (temp)
* if o (the popped element from original stack)
* is < the peek element from new stack temp
* then we push the new stack element to original stack
* and recursively keep calling till temp is not empty
* and then push the element at the right place.
* else we push the element to the new stack temp
* (o >= new temp stack.
*
* Entire logic is recursive.
*/
public void sortstk( Stack s )
{
Stack<Integer> temp = new Stack<Integer>();
while( !s.isEmpty() )
{
int s1 = (int) s.pop();
while( !temp.isEmpty() && (temp.peek() > s1) )
{
s.push( temp.pop() );
}
temp.push( s1 );
}
// Print the entire sorted stack from temp stack
for( int i = 0; i < temp.size(); i++ )
{
System.out.println( temp.elementAt( i ) );
}
}
Если нет ограничений на использование других структур данных, я бы сказал, минимальная куча. всякий раз, когда извлекается элемент из стека, помещается в кучу. По окончании выталкивания берется элемент из верхней части кучи (минимум остальных) и помещается в стек. Повторять такой процесс, пока куча не опустеет.
Для создания кучи среднее время составляет O(nlogn); для удаления элементов из кучи и возврата элементов в порядке возрастания среднее время также составляет O (nlogn).
Как это выглядит?
Обратите внимание, что ответ Майкла Дж. Барбера (см. Выше) не верен, и он забывает перенести элемент обратно в стек, когда он пуст. Правильная версия выглядит следующим образом:
void sort(stack s) {
if (!IsEmpty(s)) {
int x = Pop(s);
sort(s);
insert(s, x);
}
}
void insert(stack s, int x) {
if (!IsEmpty(s)) {
int y = Top(s);
if (x < y) {
Pop(s);
insert(s, x);
Push(s, y);
} else {
Push(s, x);
}
} else {
Push(s, x); // !!! must step, otherwise, the stack will eventually be empty after sorting !!!
}
}
class Program
{
static void Main(string[] args)
{
Stack<int> stack = new Stack<int>();
stack.Push(8);
stack.Push(5);
stack.Push(3);
stack.Push(4);
stack.Push(7);
stack.Push(9);
stack.Push(5);
stack.Push(6);
Stack<int> tempStack = new Stack<int>();
while (stack.Count > 0)
{
int temp = stack.Pop();
while(tempStack.Count>0 && tempStack.Peek() > temp)
{
stack.Push(tempStack.Pop());
}
tempStack.Push(temp);
}
while (tempStack.Count > 0)
{
Console.Write(tempStack.Pop() + " ");
}
Console.ReadLine();
}
}
Поскольку ничего не сказано о том, сколько дополнительных стеков можно использовать, поэтому я предполагаю, что любое количество стеков можно использовать для максимально эффективного решения проблемы сортировки.
Если вы забудете об ограничении стека и предположите, что это была обычная проблема сортировки. Тогда как вы можете решить это? (Подсказка: сортировка слиянием)
Выполните обычную сортировку слиянием в стеке, используя вспомогательные стеки. Временная сложность - N*log(n).
Вот решение в Javascript, основанное на ответе @OrenD
var org = [4,67,2,9,5,11,3];
var helper = [];
while(org.length > 0){
var temp = org.pop();
while((helper.length > 0) && (helper[helper.length-1] < temp)){
org.push(helper.pop());
}
helper.push(temp);
}
while(helper.length > 0){
org.push(helper.pop());
}
Игра из трех стеков
С тремя стеками S (исходный стек, стек с несортированными элементами), A, B вы можете начать играть в игру, подобную сортировке слиянием.
Я думаю, что ясно, что если вы упорядочили элементы на A и B (в одном и том же направлении, оба восходящие или оба нисходящие), вы можете использовать S для объединения сортировки A и B, а затем переместить результат, например, в B,
Тот факт, что у вас есть некоторые элементы на A, B или S, не мешает вам использовать A, B или S для слияния (если у вас есть маркер текущего размера A, B и S, чтобы вы могли не промахнулся бы). Если ваша процедура переносит упорядоченные элементы на S, то нет смысла использовать A и B для удаления отсортированной части в A или B в любом понравившемся вам направлении: вы можете поместить ее в обратном порядке непосредственно в A или B или, например,, поместите все элементы в A и затем снова поверните в B.
Предположим, что у вас есть 4 отсортированных элемента на A, 16 на B и несколько несортированных элементов на S.
A.push (S.pop) и теперь создайте отсортированное по 2 элементам слияние. Снова B.push(S.pop) и создайте еще одно 2-элементное сортированное слияние. Если слияния не разделены и / или не находятся в одном и том же направлении, вы можете манипулировать элементами любым способом, пока не достигнете 4-элементного сортированного слияния на B (или даже S). Теперь объединяйте начальное 4-элементное сортированное слияние от A и эту часть на B, пока не достигнете 8-элементного сортированного слияния.
Вы повторяете все до тех пор, пока не создадите другое 8-элементное сортированное слияние. Вы размещаете его в правильном порядке на B (или S) и объединяетесь, чтобы получить сортировку с 16 элементами. Теперь вы помещаете его в A (или S) и объединяетесь с 16-элементным слиянием, которое мы имели на B все время.
Оптимизированная реализация сложна, так как вам нужно уменьшить перемещение (возврат) отсортированного слияния из одного стека в другой. Однако, если вы исправите и решите, для чего собираетесь использовать A, B и S, и, например, заставите: A содержать меньшую и B большую объединенную часть в порядке убывания, тогда алгоритм будет проще.
Тот факт, что вам нужно переместить некоторые верхние элементы из одного стека в другой, добавляет постоянный фактор сложности, но он никогда не превышает 2. Кроме того, сложность равна n*log(n) (вы достигаете 2n-элемента сортировка слиянием путем объединения 2-х сортированных слиянием элементов, и слияние требует не более 2n шагов.)
Реализация в C# (другие похожие языки очевидны)
void Stacking(Stack<int> sourceStack, Stack<int> mainStack, Stack<int> childStack, int n)
{
if (n == 0) return;
if (n == 1)
{
mainStack.Push(sourceStack.Pop());
return;
}
int mainSize = n/2;
int childSize = n - n/2;
Stacking(sourceStack, mainStack, childStack, mainSize);
Stacking(sourceStack, childStack, mainStack, childSize);
while (true)
{
while (mainSize > 0 && mainStack.Peek() >= childStack.Peek())
{
sourceStack.Push(mainStack.Pop());
mainSize--;
}
if (mainSize == 0) break;
while (childSize > 0 && childStack.Peek() >= mainStack.Peek())
{
sourceStack.Push(childStack.Pop());
childSize--;
}
if (childSize == 0) break;
}
while (mainSize > 0)
{
sourceStack.Push(mainStack.Pop());
mainSize--;
}
while (childSize > 0)
{
sourceStack.Push(childStack.Pop());
childSize--;
}
for (int i = 0; i < n; i++)
mainStack.Push(sourceStack.Pop());
}
void SortStack(Stack<int> sourceStack)
{
int n = sourceStack.Count();
// possible optimization: if (n < 2) return;
Stack<int> mainStack = new Stack<int>();
Stack<int> childStack = new Stack<int>();
Stacking(sourceStack, mainStack, childStack, n);
for (int i = 0; i < n; i++)
sourceStack.Push(mainStack.Pop());
}
Игра бревен (n) стеков
Вышеуказанная процедура может быть упрощена, если вам разрешено использовать не более log (n) стеков. Это количество стеков не означает, что вы когда-либо будете использовать дополнительное пространство, превышающее порядок n. Вы просто отмечаете стеки, которые будут использоваться для объединения 1, 2, 4... элементов. В этом случае вы не заботитесь о порядке, так как объединяющиеся части 2^n всегда будут отсортированы в одном направлении. Однако это решение только обходит тот факт, что вы ограничены в использовании операций push и pop; кроме этого это эквивалентно сортировке слиянием во всех аспектах. По сути, если количество стеков не ограничено, то вы также можете легко эмулировать быструю сортировку.
Я думаю, что сортировка пузырьков может работать в стеке с рекурсией.
void sortStack(stack<int>& st){
bool flag = true;
int n = st.size();
for(int i = 1; i <= n - 1 && flag; i++){
flag = false;
bubbleSortStack(st, flag, i);
}
}
void bubbleSortStack(stack<int>& st, bool& flag, int endSize){
if(st.size() == endSize)
return;
int val = st.top();
st.pop();
if(val > st.top()){
flag = true;
int tmp = st.top();
st.push(val);
val = tmp;
}
bubbleSortStack(st, flag);
st.push(val);
}
Если у вас нет никакой дополнительной информации о содержимом стека, то вы в значительной степени застряли, просто извлекая все данные, сортируя их и возвращая их обратно. Heapsort был бы здесь полезен, как бы быстрая сортировка или интросортировка.
Поместите элементы в стек S в порядке возрастания, используя один дополнительный стек и некоторые дополнительные переменные, не являющиеся массивом.