Hôm nay cafedev chia sẻ cho ace một số ví dụ về việc sử dụng stack trong lập trình thực tế với các bài ví dụ hay và kinh điển. Trong phần ví dụ sẽ được code trên các ngôn ngữ khác nhau như C/C++, Java, Python….Nhằm giúp ace đang sử dụng các ngôn ngữ khác nhau hiểu nhanh và nắm vững cách dùng stack trong thực tế và khi đi làm.
Nếu ace nào chưa rõ về stack là gì?, có thể tham khảo series cấu trúc dữ liệu và giải thuật tham khảo đây..
Trong bài chúng ta sẽ áp dụng cấu trúc dữ liệu stack vào bài toán đảo ngược một chuỗi.
Cho một chuỗi, hãy đảo ngược nó bằng cách sử dụng ngăn xếp. Ví dụ: “Cafedev.vn” nên được chuyển đổi thành “vn.vedefaC”
Sau đây là thuật toán đơn giản để đảo ngược một chuỗi sử dụng ngăn xếp.
1) Tạo một ngăn xếp(stack) trống.
2) Từng bước một đẩy tất cả các ký tự của chuỗi vào ngăn xếp.
3) Từng bước một pop tất cả các ký tự từ ngăn xếp và đặt chúng trở lại chuỗi.
Các chương trình sau thực hiện thuật toán trên.
Code C++
// CPP program to reverse a string using stack
#include <bits/stdc++.h>
using namespace std;
// A structure to represent a stack
class Stack
{
public:
int top;
unsigned capacity;
char* array;
};
// function to create a stack of given
// capacity. It initializes size of stack as 0
Stack* createStack(unsigned capacity)
{
Stack* stack = new Stack();
stack->capacity = capacity;
stack->top = -1;
stack->array = new char[(stack->capacity * sizeof(char))];
return stack;
}
// Stack is full when top is equal to the last index
int isFull(Stack* stack)
{ return stack->top == stack->capacity - 1; }
// Stack is empty when top is equal to -1
int isEmpty(Stack* stack)
{ return stack->top == -1; }
// Function to add an item to stack.
// It increases top by 1
void push(Stack* stack, char item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}
// Function to remove an item from stack.
// It decreases top by 1
char pop(Stack* stack)
{
if (isEmpty(stack))
return -1;
return stack->array[stack->top--];
}
// A stack based function to reverse a string
void reverse(char str[])
{
// Create a stack of capacity
//equal to length of string
int n = strlen(str);
Stack* stack = createStack(n);
// Push all characters of string to stack
int i;
for (i = 0; i < n; i++)
push(stack, str[i]);
// Pop all characters of string and
// put them back to str
for (i = 0; i < n; i++)
str[i] = pop(stack);
}
// Driver code
int main()
{
char str[] = "Cafedev.vn";
reverse(str);
cout << "Reversed string is " << str;
return 0;
} Code C
// C program to reverse a string using stack
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
// A structure to represent a stack
struct Stack
{
int top;
unsigned capacity;
char* array;
};
// function to create a stack of given
// capacity. It initializes size of stack as 0
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (char*) malloc(stack->capacity * sizeof(char));
return stack;
}
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{ return stack->top == stack->capacity - 1; }
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{ return stack->top == -1; }
// Function to add an item to stack.
// It increases top by 1
void push(struct Stack* stack, char item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}
// Function to remove an item from stack.
// It decreases top by 1
char pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
// A stack based function to reverse a string
void reverse(char str[])
{
// Create a stack of capacity
//equal to length of string
int n = strlen(str);
struct Stack* stack = createStack(n);
// Push all characters of string to stack
int i;
for (i = 0; i < n; i++)
push(stack, str[i]);
// Pop all characters of string and
// put them back to str
for (i = 0; i < n; i++)
str[i] = pop(stack);
}
// Driver program to test above functions
int main()
{
char str[] = "Cafedev.vn";
reverse(str);
printf("Reversed string is %s", str);
return 0;
}
Code Java
/* Java program to reverse
String using Stack */
import java.util.*;
//stack
class Stack
{
int size;
int top;
char[] a;
//function to check if stack is empty
boolean isEmpty()
{
return (top < 0);
}
Stack(int n)
{
top = -1;
size = n;
a = new char[size];
}
//function to push element in Stack
boolean push(char x)
{
if (top >= size)
{
System.out.println("Stack Overflow");
return false;
}
else
{
a[++top] = x;
return true;
}
}
//function to pop element from stack
char pop()
{
if (top < 0)
{
System.out.println("Stack Underflow");
return 0;
}
else
{
char x = a[top--];
return x;
}
}
}
// Driver code
class Main
{
//function to reverse the string
public static void reverse(StringBuffer str)
{
// Create a stack of capacity
// equal to length of string
int n = str.length();
Stack obj = new Stack(n);
// Push all characters of string
// to stack
int i;
for (i = 0; i < n; i++)
obj.push(str.charAt(i));
// Pop all characters of string
// and put them back to str
for (i = 0; i < n; i++)
{
char ch = obj.pop();
str.setCharAt(i,ch);
}
}
//driver function
public static void main(String args[])
{
//create a new string
StringBuffer s= new StringBuffer("Cafedev.vn");
//call reverse method
reverse(s);
//print the reversed string
System.out.println("Reversed string is " + s);
}
}
Code Python
# Python program to reverse a string using stack
# Function to create an empty stack.
# It initializes size of stack as 0
def createStack():
stack=[]
return stack
# Function to determine the size of the stack
def size(stack):
return len(stack)
# Stack is empty if the size is 0
def isEmpty(stack):
if size(stack) == 0:
return true
# Function to add an item to stack .
# It increases size by 1
def push(stack,item):
stack.append(item)
#Function to remove an item from stack.
# It decreases size by 1
def pop(stack):
if isEmpty(stack): return
return stack.pop()
# A stack based function to reverse a string
def reverse(string):
n = len(string)
# Create a empty stack
stack = createStack()
# Push all characters of string to stack
for i in range(0,n,1):
push(stack,string[i])
# Making the string empty since all
#characters are saved in stack
string=""
# Pop all characters of string and
# put them back to string
for i in range(0,n,1):
string+=pop(stack)
return string
# Driver program to test above functions
string="Cafedev.vn"
string = reverse(string)
print("Reversed string is " + string)
Code C#
/* C# program to reverse
String using Stack */
using System;
using System.Text;
//stack
class Stack
{
public int size;
public int top;
public char[] a;
// function to check if stack is empty
public Boolean isEmpty()
{
return (top < 0);
}
public Stack(int n)
{
top = -1;
size = n;
a = new char[size];
}
// function to push element in Stack
public Boolean push(char x)
{
if (top >= size)
{
Console.WriteLine("Stack Overflow");
return false;
}
else
{
a[++top] = x;
return true;
}
}
// function to pop element from stack
public char pop()
{
if (top < 0)
{
Console.WriteLine("Stack Underflow");
return ' ';
}
else
{
char x = a[top--];
return x;
}
}
}
class GFG
{
// function to reverse the string
public static void reverse(StringBuilder str)
{
// Create a stack of capacity
// equal to length of string
int n = str.Length;
Stack obj = new Stack(n);
// Push all characters of string
// to stack
int i;
for (i = 0; i < n; i++)
obj.push(str[i]);
// Pop all characters of string
// and put them back to str
for (i = 0; i < n; i++)
{
char ch = obj.pop();
str[i] = ch;
}
}
// Driver code
public static void Main(String []args)
{
// create a new string
StringBuilder s = new StringBuilder("Cafedev.vn");
// call reverse method
reverse(s);
// print the reversed string
Console.WriteLine("Reversed string is " + s);
}
} Kết quả
Reversed string is vn.vedefaCĐộ phức tạp thời gian: O (n) với n là số ký tự trong ngăn xếp.
Không gian phụ: O(n) cho ngăn xếp.
Một chuỗi cũng có thể được đảo ngược mà không cần sử dụng bất kỳ không gian phụ trợ nào. Tiếp theo các chương trình C, Java, C # và Python để thực hiện đảo ngược mà không cần sử dụng ngăn xếp.
Code trên nhiều ngôn ngữ:
C++
// C++ program to reverse a string without using stack
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap two characters
void swap(char *a, char *b)
{
char temp = *a;
*a = *b;
*b = temp;
}
// A stack based function to reverse a string
void reverse(char str[])
{
// get size of string
int n = strlen(str), i;
for (i = 0; i < n/2; i++)
swap(&str[i], &str[n-i-1]);
}
// Driver program to test above functions
int main()
{
char str[] = "abc";
reverse(str);
cout<<"Reversed string is "<< str;
return 0;
}
C
// C program to reverse a string without using stack
#include <stdio.h>
#include <string.h>
// A utility function to swap two characters
void swap(char *a, char *b)
{
char temp = *a;
*a = *b;
*b = temp;
}
// A stack based function to reverse a string
void reverse(char str[])
{
// get size of string
int n = strlen(str), i;
for (i = 0; i < n/2; i++)
swap(&str[i], &str[n-i-1]);
}
// Driver program to test above functions
int main()
{
char str[] = "abc";
reverse(str);
printf("Reversed string is %s", str);
return 0;
}
Java
// Java program to reverse a string without using stack
public class GFG {
// A utility function to swap two characters
static void swap(char a[], int index1, int index2) {
char temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
// A stack based function to reverse a string
static void reverse(char str[]) {
// get size of string
int n = str.length, i;
for (i = 0; i < n / 2; i++) {
swap(str, i, n - i - 1);
}
}
// Driver program to test above functions
public static void main(String[] args) {
char str[] = "abc".toCharArray();
reverse(str);
System.out.printf("Reversed string is " + String.valueOf(str));
}
} Python
# Python program to reverse a string without stack
# Function to reverse a string
def reverse(string):
string = string[::-1]
return string
# Driver program to test above functions
string = "abc"
string = reverse(string)
print("Reversed string is " + string) C#
// C# program to reverse a string without using stack
using System;
public class GFG {
// A utility function to swap two characters
static void swap(char []a, int index1, int index2) {
char temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
// A stack based function to reverse a string
static void reverse(char []str) {
// get size of string
int n = str.Length, i;
for (i = 0; i < n / 2; i++) {
swap(str, i, n - i - 1);
}
}
// Driver program to test above functions
public static void Main() {
char []str = "abc".ToCharArray();
reverse(str);
Console.WriteLine("Reversed string is " + String.Join("",str));
}
} Kết quả
Reversed string is cbaNguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
