本文概述
- C ++
- C
- Java
- Python3
- C#
is_empty(S): Tests whether stack is empty or not.
push(S): Adds new element to the stack.
pop(S): Removes top element from the stack.
top(S): Returns value of the top element. Note that this
function does not remove element from the stack.例子：
Input:-3<
--- Top
14
18
-5
30 Output: 30<
--- Top
18
14
-3
-5这个问题主要是使用递归的反向栈的一种变体。
解决方案的想法是将所有值保留在函数调用栈中, 直到栈变空。当栈变空时, 请按排序顺序一次插入所有保留的项目。在这里, 排序顺序很重要。
算法
我们可以使用以下算法对栈元素进行排序：
sortStack(stack S)
if stack is not empty:
temp = pop(S);
sortStack(S);
sortedInsert(S, temp);
下面的算法是对元素进行插入排序：
sortedInsert(Stack S, element)
if stack is empty OR element >
top element
push(S, elem)
else
temp = pop(S)
sortedInsert(S, element)
push(S, temp)插图：
Let given stack be
-3<
-- top of the stack
14
18
-5
30让我们使用上面的示例来说明栈的排序：
首先从栈中弹出所有元素, 然后将弹出的元素存储在变量" temp"中。弹出所有elements函数后, 其栈框架将如下所示：
temp = -3-->
stack frame #1
temp = 14-->
stack frame #2
temp = 18-->
stack frame #3
temp = -5-->
stack frame #4
temp = 30-->
stack frame #5现在栈为空, 并调用了" insert_in_sorted_order()"函数, 并在栈底部插入了30(从栈帧5开始)。现在栈如下所示：
30<
-- top of the stack现在选择下一个元素, 即-5(来自栈帧＃4)。由于-5 < 30, 因此-5会插入栈的底部。现在栈变为：
30<
-- top of the stack
-0接下来的18个(来自栈帧3)被选中。由于18 < 30, 因此将18插入30以下。现在栈变为：
30<
-- top of the stack
18
-5接下来的14个(来自栈帧2)被选中。由于14 < 30和14 < 18, 因此将其插入18以下。现在, 栈变为：
30<
-- top of the stack
18
14
-5现在, 选择-3(从栈帧1), 因为-3 < 30和-3 < 18和-3 < 14, 它将插入14以下。现在, 栈变为：
30<
-- top of the stack
18
14
-3
-5实现
下面是上述算法的实现。
C ++
// C++ program to sort a stack using recursion
#include <
iostream>
using namespace std;
// Stack is represented using linked list
struct stack {
int data;
struct stack* next;
};
// Utility function to initialize stack
void initStack( struct stack** s) { *s = NULL;
}// Utility function to chcek if stack is empty
int isEmpty( struct stack* s)
{
if (s == NULL)
return 1;
return 0;
}// Utility function to push an item to stack
void push( struct stack** s, int x)
{
struct stack* p = ( struct stack*) malloc ( sizeof (*p));
if (p == NULL) {
fprintf (stderr, "Memory allocation failed.\n" );
return ;
}p->
data = https://www.lsbin.com/x;
p->
next = *s;
*s = p;
}// Utility function to remove an item from stack
int pop( struct stack** s)
{
int x;
struct stack* temp;
x = (*s)->
data;
temp = *s;
(*s) = (*s)->
next;
free (temp);
return x;
}// Function to find top item
int top( struct stack* s) { return (s->
data);
}// Recursive function to insert an item x in sorted way
void sortedInsert( struct stack** s, int x)
{
// Base case: Either stack is empty or newly inserted
// item is greater than top (more than all existing)
if (isEmpty(*s) or x >
top(*s)) {
push(s, x);
return ;
}// If top is greater, remove the top item and recur
int temp = pop(s);
sortedInsert(s, x);
// Put back the top item removed earlier
push(s, temp);
}// Function to sort stack
void sortStack( struct stack** s)
{
// If stack is not empty
if (!isEmpty(*s)) {
// Remove the top item
int x = pop(s);
// Sort remaining stack
sortStack(s);
// Push the top item back in sorted stack
sortedInsert(s, x);
}
}// Utility function to print contents of stack
void printStack( struct stack* s)
{
while (s) {
cout <
<
s->
data <
<" " ;
s = s->
next;
}
cout <
<
"\n" ;
}// Driver code
int main( void )
{
struct stack* top;
initStack(&
top);
push(&
top, 30);
push(&
top, -5);
push(&
top, 18);
push(&
top, 14);
push(&
top, -3);
cout <
<
"Stack elements before sorting:\n" ;
printStack(top);
sortStack(&
top);
cout <
<
"\n" ;
cout <
<
"Stack elements after sorting:\n" ;
printStack(top);
return 0;
}// This code is contributed by SHUBHAMSINGH10C
// C program to sort a stack using recursion
#include <
stdio.h>
#include <
stdlib.h>
// Stack is represented using linked list
struct stack {
int data;
struct stack* next;
};
// Utility function to initialize stack
void initStack( struct stack** s) { *s = NULL;
}// Utility function to chcek if stack is empty
int isEmpty( struct stack* s)
{
if (s == NULL)
return 1;
return 0;
}// Utility function to push an item to stack
void push( struct stack** s, int x)
{
struct stack* p = ( struct stack*) malloc ( sizeof (*p));
if (p == NULL) {
fprintf (stderr, "Memory allocation failed.\n" );
return ;
}p->
data = https://www.lsbin.com/x;
p->
next = *s;
*s = p;
}// Utility function to remove an item from stack
int pop( struct stack** s)
{
int x;
struct stack* temp;
x = (*s)->
data;
temp = *s;
(*s) = (*s)->
next;
free (temp);
return x;
}// Function to find top item
int top( struct stack* s) { return (s->
data);
}// Recursive function to insert an item x in sorted way
void sortedInsert( struct stack** s, int x)
{
// Base case: Either stack is empty or newly inserted
// item is greater than top (more than all existing)
if (isEmpty(*s) || x >
top(*s)) {
push(s, x);
return ;
}// If top is greater, remove the top item and recur
int temp = pop(s);
sortedInsert(s, x);
// Put back the top item removed earlier
push(s, temp);
}// Function to sort stack
void sortStack( struct stack** s)
{
// If stack is not empty
if (!isEmpty(*s)) {
// Remove the top item
int x = pop(s);
// Sort remaining stack
sortStack(s);
// Push the top item back in sorted stack
sortedInsert(s, x);
}
}// Utility function to print contents of stack
void printStack( struct stack* s)
{
while (s) {
printf ("%d " , s->
data);
s = s->
next;
}
printf ( "\n" );
}// Driver code
int main( void )
{
struct stack* top;
initStack(&
top);
push(&
top, 30);
push(&
top, -5);
push(&
top, 18);
push(&
top, 14);
push(&
top, -3);
printf ( "Stack elements before sorting:\n" );
printStack(top);
sortStack(&
top);
printf ( "\n\n" );
printf ( "Stack elements after sorting:\n" );
printStack(top);
return 0;
}Java
// Java program to sort a Stack using recursion
// Note that here predefined Stack class is used
// for stack operationimport java.util.ListIterator;
import java.util.Stack;
class Test
{
// Recursive Method to insert an item x in sorted way
static void sortedInsert(Stack<
Integer>
s, int x)
{
// Base case: Either stack is empty or newly
// inserted item is greater than top (more than all
// existing)
if (s.isEmpty() || x >
s.peek())
{
s.push(x);
return ;
}// If top is greater, remove the top item and recur
int temp = s.pop();
sortedInsert(s, x);
// Put back the top item removed earlier
s.push(temp);
}// Method to sort stack
static void sortStack(Stack<
Integer>
s)
{
// If stack is not empty
if (!s.isEmpty())
{
// Remove the top item
int x = s.pop();
// Sort remaining stack
sortStack(s);
// Push the top item back in sorted stack
sortedInsert(s, x);
}
}// Utility Method to print contents of stack
static void printStack(Stack<
Integer>
s)
{
ListIterator<
Integer>
lt = s.listIterator();
// forwarding
while (lt.hasNext())
lt.next();
// printing from top to bottom
while (lt.hasPrevious())
System.out.print(lt.previous() + " " );
}// Driver code
public static void main(String[] args)
{
Stack<
Integer>
s = new Stack<
>
();
s.push( 30 );
s.push(- 5 );
s.push( 18 );
s.push( 14 );
s.push(- 3 );
System.out.println(
"Stack elements before sorting: " );
printStack(s);
sortStack(s);
System.out.println(
" \n\nStack elements after sorting:" );
printStack(s);
}
}Python3
# Python program to sort a stack using recursion# Recursive method to insert element in sorted waydef sortedInsert(s, element):# Base case: Either stack is empty or newly inserted
# item is greater than top (more than all existing)
if len (s) = = 0 or element >
s[ - 1 ]:
s.append(element)
return
else :# Remove the top item and recur
temp = s.pop()
sortedInsert(s, element)# Put back the top item removed earlier
s.append(temp)# Method to sort stackdef sortStack(s):# If stack is not empty
if len (s) ! = 0 :# Remove the top item
temp = s.pop()# Sort remaining stack
sortStack(s)# Push the top item back in sorted stack
sortedInsert(s, temp)# Printing contents of stackdef printStack(s):
for i in s[:: - 1 ]:
print (i, end = " " )
print ()# Driver Code
if __name__ = = '__main__' :
s = []
s.append( 30 )
s.append( - 5 )
s.append( 18 )
s.append( 14 )
s.append( - 3 )print ( "Stack elements before sorting: " )
printStack(s)sortStack(s)print ( "\nStack elements after sorting: " )
printStack(s)# This code is contributed by Muskan Kalra.C#
// C# program to sort a Stack using recursion
// Note that here predefined Stack class is used
// for stack operation
using System;
using System.Collections;
public class GFG
{
// Recursive Method to insert an item x in sorted way
static void sortedInsert(Stack s, int x)
{
// Base case: Either stack is empty or
// newly inserted item is greater than top
// (more than all existing)
if (s.Count == 0 || x >
( int )s.Peek()) {
s.Push(x);
return ;
}// If top is greater, remove
// the top item and recur
int temp = ( int )s.Peek();
s.Pop();
sortedInsert(s, x);
// Put back the top item removed earlier
s.Push(temp);
}// Method to sort stack
static void sortStack(Stack s)
{
// If stack is not empty
if (s.Count >
0) {
// Remove the top item
int x = ( int )s.Peek();
s.Pop();
// Sort remaining stack
sortStack(s);
// Push the top item back in sorted stack
sortedInsert(s, x);
}
}// Utility Method to print contents of stack
static void printStack(Stack s)
{
foreach ( int c in s) { Console.Write(c + " " );
}
}// Driver code
public static void Main(String[] args)
{
Stack s = new Stack();
s.Push(30);
s.Push(-5);
s.Push(18);
s.Push(14);
s.Push(-3);
Console.WriteLine(
"Stack elements before sorting: " );
printStack(s);
sortStack(s);
Console.WriteLine(
" \n\nStack elements after sorting:" );
printStack(s);
}
}// This code is Contibuted by Arnab Kundu输出如下：
Stack elements before sorting:
-3 14 18 -5 30 Stack elements after sorting:
30 18 14 -3 -5复杂度分析：
- 时间复杂度：O(n^2)。
在最坏的情况下sortstack(), sortedinsert()被递归调用" N"次, 以将元素放置在正确的位置 - 辅助空间：O(n^2)
使用栈数据结构存储值
推荐阅读
- JavaScript布尔构造函数属性
- 如何使用MoviePy合成视频（设置单个剪辑的开始时间）
- JavaScript如何使用Date parse()方法（用法示例）
- Python程序可计算列表中的正数和负数
- jQuery如何使用多个ID选择器（代码示例）
- 检查给定字符串的字符是否可以重新排列以形成回文
- 算法设计（如何高效地找到数字的奇偶性（））
- 了解基本的JavaScript代码，简要指南
- 进程表和进程控制块（PCB）详细指南