使用递归对栈进行排序

2024 年 8 月 28 日 | 阅读 17 分钟

栈是一种线性数据结构，遵循后进先出 (LIFO) 原则。这意味着最后添加到栈中的元素会首先被删除。栈的另一个词是 LIFO，它指的是元素从栈中移除的顺序（后进先出）。这种结构被称为“栈”，因为它类似于一堆相互堆叠的真实物品。这种结构使得从栈顶移除一个元素很简单，但从栈底移除一个元素可能需要先移除许多其他元素。窥视操作也可以在不改变栈的情况下访问栈顶元素。

对栈进行排序对于各种任务都很有用，包括内存管理、在发生中断时维护进程的上下文以及其他高优先级任务。尽管我们在此将看到递归方法，但排序也可以迭代地完成。

栈中的操作

在栈中，我们可以执行以下操作，例如：

Push()：将元素压入栈中
Pop()：弹出栈顶元素
Top()：返回栈顶元素
Size()：返回栈的大小

栈是一种非常有用且关键的数据结构，它用于内存管理和进程流调度。程序计数器是栈最重要的应用之一，因为它保存了处理器代码的上下文，以防在需要转换到新进程时将其堆叠起来，以便在新进程完成时可以返回旧进程并完成它。

递归是最重要的算法之一，因为如果我们能解决一个较小的任务，我们几乎肯定可以利用较小的任务来解决整个项目。递归是一个术语，指的是自我调用的行为。它有一个基本情况，这是主要情况，它处理较小的问题场景，然后为较小的部分调用自身。它利用了这样一个事实：当我们处于某种状态时，我们假设我们的递归函数已经处理了较小的响应，现在我们可以将这些响应组合起来解决我们当前的状态。

Java 代码

让我们编写一个 Java 代码，使用递归对栈进行排序。

import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.Scanner;
 
class Main
{
    // Insert the given key into the sorted stack while maintaining its
    // sorted order. This is similar to the recursive insertion sort routine.
    public static void sortedInsert(Stack<Integer> stack, int key)
    {
        // base case: if the stack is empty or
        // the key is greater than all elements in the stack
        if (stack.isEmpty() || key > stack.peek())
        {
            stack.push(key);
            return;
        }
 
        /* We reach here when the key is smaller than the top element */
 
        // remove the top element
        int top = stack.pop();
 
        // recur for the remaining elements in the stack
        sortedInsert(stack, key);
 
        // insert the popped element back into the stack
        stack.push(top);
    }
 
    // Recursive method to sort a stack
    public static void sortStack(Stack<Integer> stack)
    {
        // base case: stack is empty
        if (stack.isEmpty()) {
            return;
        }
 
        // remove the top element
        int top = stack.pop();
 
        // recur for the remaining elements in the stack
        sortStack(stack);
 
        // insert the popped element back into the sorted stack
        sortedInsert(stack, top);
    }
 
    public static void main(String[] args)
    {
        
         // creating a object of the inbuilt class Stack named stack
        Stack<Integer> stack = new Stack<>();
        Scanner scan = new Scanner(System.in);
        char ch;
        /**  Print all the options to select from**/
        do    
        {
            System.out.println("\nSelect one of the operations::\n");
            System.out.println("1. To insert a new value in the Stack Data Structure.");
            System.out.println("2. To display the data inside of the Stack Data Structure.");
            System.out.println("3. To perform Sorting(via Recursion) on the Stack Data Structure.");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                stack.push(scan.nextInt());                     
                break;                          
            case 2 : 
                System.out.println("Stack:: "+stack);
                
                break;                                          
            case 3 : 
                System.out.println("Sort done.");
                sortStack(stack);
                break;     
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');
    }
}

输出

上面的 Java 代码给出以下输出。

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
45

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
32

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
98

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
22

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
49

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
13

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1 
Enter integer element to insert
36

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
54

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
102

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
1
Enter integer element to insert
506

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
2
Stack:: [45, 32, 98, 22, 49, 13, 36, 54, 102, 506]

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
3
Sort done.

Do you want to continue (Type y or n) 

y

Select one of the operations::
1. To insert a new value in the Stack Data Structure.
2. To display the data inside of the Stack Data Structure.
3. To perform sorting (via Recursion) on the Stack Data Structure.
2
Stack:: [13, 22, 32, 36, 45, 49, 54, 98, 102, 506]

Do you want to continue (Type y or n) 

n

通过这种方式，我们编写了 Java 代码来对栈数据结构执行排序操作。为栈数据结构编写了三个函数，一个是向栈数据结构中添加新节点，第二个是显示栈数据结构中存在的所有内容，第三个也是最后一个函数是对栈数据结构执行排序操作。

用户首先在栈数据结构中添加足够的数据。一旦节点成功添加，通过从每次操作后显示菜单中选择第三个选项，对栈数据结构执行排序操作，这将调用代码中编写的 sort() 函数，并将栈数据结构的对象作为参数传递。

排序操作成功完成后，用户可以通过从用户处选择第二个选项来显示栈数据结构中节点的值，以确认排序操作的结果。一旦所有操作完成，用户可以通过输入“n”或“N”字符退出代码。

C++ 代码

现在让我们编写一个 C++ 代码，使用递归对栈进行排序。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
 
// Insert the given key into the sorted stack while maintaining its sorted order.
// This is similar to the recursive insertion sort routine
void sortedInsert(stack<int> &stack, int key)
{
    // base case: if the stack is empty or
    // the key is greater than all elements in the stack
    if (stack.empty() || key > stack.top())
    {
        stack.push(key);
        return;
    }
 
    /* We reach here when the key is smaller than the top element */
 
    // remove the top element
    int top = stack.top();
    stack.pop();
 
    // recur for the remaining elements in the stack
    sortedInsert(stack, key);
 
    // insert the popped element back into the stack
    stack.push(top);
}
 
// Recursive method to sort a stack
void sortstack(stack<int> &stack)
{
    // base case: stack is empty
    if (stack.empty()) {
        return;
    }
 
    // remove the top element
    int top = stack.top();
    stack.pop();
 
    // recur for the remaining elements in the stack
    sortstack(stack);
 
    // insert the popped element back into the sorted stack
    sortedInsert(stack, top);
}
 
void printStack(stack<int> stack)
{
    while (!stack.empty())
    {
        cout << stack.top() << " ";
        stack.pop();
    }
    cout << endl;
}
 
int main()
{
    stack<int> stack;

    int data;
    char ch;
        /*  Perform tree operations  */
        do    
        {
            cout<<"\nSelect one of the operations::"<<endl;
            cout<<"1. To insert a new node in the Stack Data Structure."<<endl;
            cout<<"2. To display the nodes of the Stack Data Structure."<<endl;
            cout<<"3. To perform sorting on the Stack Data Structure."<<endl;
             
            int choice;
            cin>>choice;            
            switch (choice)
            {
            case 1 : 
                cout<<"Enter the value to be inserted"<<endl;
                cin>>data;
                stack.push(data);                
                break;                          
            case 2 : 
                cout<<"Contents of the stack are::"<<endl;
                printStack(stack);
                break; 
            case 3 : 
                cout<<"Sort done sucessfully."<<endl;
                sortstack(stack);
                break;
            default : 
                cout<<"Wrong Entry \n ";
                break;   
            }
 
            cout<<"\nDo you want to continue (Type y or n) \n";
            cin>>ch;                        
        } while (ch == 'Y'|| ch == 'y');
    return 0;       
}  // end of main function

输出

上面的 C++ 代码产生以下输出。

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
45

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
32

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
97 

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
40

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
21

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
67

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
30

Do you want to continue (Type y or n) 
y
Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
505

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
672

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
341

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
1
Enter the value to be inserted
231

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
2
Contents of the stack are::
231 341 672 505 30 67 21 40 97 32 45 

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
3
Sort did successfully.

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform sorting on the Stack Data Structure.
2
Contents of the stack are::
672 505 341 231 97 67 45 40 32 30 21 

Do you want to continue (Type y or n) 
n

通过这种方式，我们编写了 C++ 代码来对栈数据结构执行排序操作。为栈数据结构编写了三个函数，一个是向栈数据结构中添加新节点，第二个是显示栈数据结构中存在的所有内容，第三个也是最后一个函数是对栈数据结构执行排序操作。

C 代码

现在让我们编写一个简单的 C 代码，使用递归对栈进行排序。

// 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 check 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 = 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);
	int data;
    char ch;
        /*  Perform  operations  */
        do    
        {
            printf("\nSelect one of the operations::");
            printf("\n1. To insert a new node in the Stack Data Structure.");
            printf("\n2. To display the nodes of the Stack Data Structure.");
printf("\n3. To perform sort on the Stack Data Structure.\n");

            int choice;
            scanf("%d",&choice);            
            switch (choice)
            {
            case 1 : 
                printf("\nEnter the value to be inserted\n");
                scanf("%d",&data);
                push(&top,data);                  
                break;                          
            case 2 : 
				printf("Stack elements:\n");
				printStack(top);
                break; 
            case 3 : 
                printf("\nSort applied sucessfully.\n");
                sortStack(&top);
                break;
            default : 
                printf("Wrong Entry\n");
                break;   
            }

            printf("\nDo you want to continue (Type y or n)\n");
            scanf(" %c",&ch);                        
        } while (ch == 'Y'|| ch == 'y'); 
	return 0;
}

输出

上面的 C 代码给出此输出。

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
1

Enter the value to be inserted
12

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
1

Enter the value to be inserted
45

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
1

Enter the value to be inserted
9

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
1

Enter the value to be inserted
32

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
1

Enter the value to be inserted
87

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
1

Enter the value to be inserted
20

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
1

Enter the value to be inserted
18

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
1

Enter the value to be inserted
56

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
2
Stack elements:
56 18 20 87 32 9 45 12 

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
3

Sort applied successfully.

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Stack Data Structure.
2. To display the nodes of the Stack Data Structure.
3. To perform a sort on the Stack Data Structure.
2
Stack elements:
87 56 45 32 20 18 12 9 

Do you want to continue (Type y or n)
N

通过这种方式，我们编写了 C 代码来对栈数据结构执行排序操作。为栈数据结构编写了三个函数，一个是向栈数据结构中添加新节点，第二个是显示栈数据结构中存在的所有内容，第三个也是最后一个函数是对栈数据结构执行排序操作。

下一主题数据结构中的 LIFO 方法

使用递归对栈进行排序

栈中的操作

Java 代码

C++ 代码

C 代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

使用递归对栈进行排序

栈中的操作

Java 代码

C++ 代码

C 代码

相关帖子

查找每个经理下的员工数量

检测链表中的循环

使用 O(1) 额外空间合并两个已排序数组

后缀数组导论

鸡尾酒排序

将表示数字的链表相加

线段树中的懒惰传播

二叉树的性质

以最小成本连接 n 根绳子

后缀数组 nLogN 算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器