CTDL và giải thuật - Đảo ngược của string

Cho một string, nhiệm vụ của bạn là in chuỗi đảo ngược của string đó ra màn hình bằng cách dùng stack.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    codelearn

    nraeledoc


    Với s = "codelearn" thì reverseString(s) = "nraeledoc".
     
  • Test mẫu 2:
     
    Input Output

    abcd

    dcba


    Với s = "abcd" thì reverseString(s) = "dcba".

Giới thiệu về cấu trúc stack.

Stack là một loại container adaptor, được thiết kế để hoạt động theo kiểu LIFO (Last - in first - out) (vào sau ra trước), tức là một kiểu danh sách mà việc bổ sung và loại bỏ một phần tử được thực hiển ở cuối danh sách. Vị trí cuối cùng của stack gọi là đỉnh (top) của ngăn xếp.

 

Stack giống như việc giáo viên kiểm tra vở bài tập của học sinh vậy, ai nộp sau cùng thì vở bài tập của người đó sẽ được giáo viên kiểm tra đầu tiên, đương nhiên người nộp vợ đầu tiên sẽ được kiểm tra cuối cùng.

Stack có các hàm sau (ví dụ cho C++):

  • size : trả về kích thước hiện tại của stack. ĐPT O(1).
  • empty : true stack nếu rỗng, và ngược lại. ĐPT O(1).
  • push : đẩy phần tử vào stack. ĐPT O(1).
  • pop : loại bỏ phẩn tử ở đỉnh của stack. ĐPT O(1).
  • top : truy cập tới phần tử ở đỉnh stack. ĐPT O(1).

 

Hướng dẫn bài tập.

Bài này có khá nhiều cách làm, chúng ta có thể dùng stack để hiểu hơn về stack.

Dùng một stack có kiểu char để lưu các ký tự trong chuỗi, sau đó in stack ra màn hình.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>
#include<stack>

using namespace std;

int main(){
	string s;
	stack<char> st;
	getline(cin,s);
	for (int i = 0; i < s.length(); i++){
		st.push(s[i]);
	}
	while(!st.empty()){
		cout << st.top();
		st.pop();
	}
	
	return 0;
}