当前位置：首页 > news >正文

数据结构之栈的实现与排序详解与示例（C, C#, C++）

news 来源：原创 2024/9/20 19:34:44

文章目录

- 栈的基本操作
- 栈的排序
- 总结

栈是一种后进先出（Last In First Out, LIFO）的数据结构。在栈中，元素的插入和删除操作都发生在同一端，即栈顶。本文将详细介绍如何实现栈的排序，并提供C, C#, C++三种语言的示例。

栈的基本操作

在介绍栈的排序之前，我们先回顾一下栈的基本操作：

初始化栈
入栈（push）
出栈（pop）
获取栈顶元素
判断栈是否为空

以下是C, C#, C++三种语言实现栈的基本操作的示例：

C语言

#include <stdio.h>
#include <stdlib.h>typedef struct Stack {int *data;int top;int maxSize;
} Stack;// 初始化栈
void initStack(Stack *s, int size) {s->data = (int *)malloc(size * sizeof(int));s->top = -1;s->maxSize = size;
}// 入栈
void push(Stack *s, int value) {if (s->top < s->maxSize - 1) {s->top++;s->data[s->top] = value;} else {printf("栈满，无法入栈！\n");}
}// 出栈
int pop(Stack *s) {if (s->top >= 0) {int value = s->data[s->top];s->top--;return value;} else {printf("栈空，无法出栈！\n");return -1;}
}// 获取栈顶元素
int getTop(Stack *s) {if (s->top >= 0) {return s->data[s->top];} else {printf("栈空！\n");return -1;}
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == -1;
}

C#语言

using System;public class Stack {private int[] data;private int top;private int maxSize;public Stack(int size) {data = new int[size];top = -1;maxSize = size;}// 入栈public void Push(int value) {if (top < maxSize - 1) {top++;data[top] = value;} else {Console.WriteLine("栈满，无法入栈！");}}// 出栈public int Pop() {if (top >= 0) {int value = data[top];top--;return value;} else {Console.WriteLine("栈空，无法出栈！");return -1;}}// 获取栈顶元素public int GetTop() {if (top >= 0) {return data[top];} else {Console.WriteLine("栈空！");return -1;}}// 判断栈是否为空public bool IsEmpty() {return top == -1;}
}

C++语言

#include <iostream>
#include <vector>using namespace std;class Stack {
private:vector<int> data;int top;int maxSize;public:Stack(int size) : top(-1), maxSize(size) {}// 入栈void push(int value) {if (top < maxSize - 1) {top++;data.push_back(value);} else {cout << "栈满，无法入栈！" << endl;}}// 出栈int pop() {if (top >= 0) {int value = data[top];data.pop_back();top--;return value;} else {cout << "栈空，无法出栈！" << endl;return -1;}}// 获取栈顶元素int getTop() {if (top >= 0) {return data[top];} else {cout << "栈空！" << endl;return -1;}}// 判断栈是否为空bool isEmpty() {return top == -1;}
};

栈的排序

栈的排序是指将一个无序栈调整为有序栈。这里我们以升序排序为例，介绍两种常见的栈排序方法：递归法和辅助栈法。

递归法
递归法的基本思想是：每次递归地将栈顶元素出栈，然后对剩余的栈进行排序，最后将栈顶元素重新入栈。

以下是C, C#, C++三种语言实现递归法栈排序的代码示例：

C语言

void sortStack(Stack* stack) {if (!isEmpty(stack)) {int value = pop(stack);sortStack(stack);sortedInsert(stack, value);}
}void sortedInsert(Stack* stack, int value) {if (isEmpty(stack) || value > getTop(stack)) {push(stack, value);} else {int temp = pop(stack);sortedInsert(stack, value);push(stack, temp);}
}

C#语言

public void SortStack() {if (!IsEmpty()) {int value = Pop();SortStack();SortedInsert(value);}
}private void SortedInsert(int value) {if (IsEmpty() || value > GetTop()) {Push(value);} else {int temp = Pop();SortedInsert(value);Push(temp);}
}

C++语言

void sortStack() {if (!isEmpty()) {int value = pop();sortStack();sortedInsert(value);}
}void sortedInsert(int value) {if (isEmpty() || value > getTop()) {push(value);} else {int temp = pop();sortedInsert(value);push(temp);}
}

辅助栈法
辅助栈法的基本思想是：使用一个额外的栈来辅助排序。将原栈的元素逐个出栈，然后按照顺序插入到辅助栈中，最后将辅助栈的元素逐个出栈放回原栈。

以下是C, C#, C++三种语言实现辅助栈法栈排序的代码示例：

C语言

void sortStackUsingTempStack(Stack* stack) {Stack* tempStack = initStack();while (!isEmpty(stack)) {int temp = pop(stack);while (!isEmpty(tempStack) && getTop(tempStack) > temp) {push(stack, pop(tempStack));}push(tempStack, temp);}while (!isEmpty(tempStack)) {push(stack, pop(tempStack));}
}

C#语言

public void SortStackUsingTempStack() {Stack tempStack = new Stack();while (!IsEmpty()) {int temp = Pop();while (!tempStack.IsEmpty() && tempStack.GetTop() > temp) {Push(tempStack.Pop());}tempStack.Push(temp);}while (!tempStack.IsEmpty()) {Push(tempStack.Pop());}
}

C++语言

void sortStackUsingTempStack() {Stack tempStack;while (!isEmpty()) {int temp = pop();while (!tempStack.isEmpty() && tempStack.getTop() > temp) {push(tempStack.pop());}tempStack.push(temp);}while (!tempStack.isEmpty()) {push(tempStack.pop());}
}