Cho một số nguyên Num làm đầu vào. Mục tiêu là tìm số đảo ngược của Num bằng ngăn xếp (stack).
Stack: Cấu trúc dữ liệu trong C++ lưu trữ theo LIFO (Last In First Out). Các phép toán chính:
Khai báo: stack<int> stck;
Lấy đỉnh: top() - trả về tham chiếu phần tử đỉnh.
Xóa đỉnh: pop() - xóa phần tử đỉnh.
Thêm vào đỉnh: push(value) - thêm giá trị vào stack.
Kiểm tra rỗng: empty() - true nếu stack rỗng.
Ví dụ
Đầu vào - Num = 33267
Đầu ra - Số đảo ngược: 76233
Giải thích -
Đẩy các chữ số vào stack: 7 - 6 - 2 - 3 - 3 ← đỉnh
7×10000 + 6×1000 + 2×100 + 3×10 + 3×1 = 76233
Đầu vào - Num = 111000
Đầu ra - Số đảo ngược: 111
Giải thích -
Đẩy các chữ số: 0 - 0 - 0 - 1 - 1 - 1 ← đỉnh
0×100000 + 0×10000 + 0×1000 + 1×100 + 1×10 + 1×1 = 111
Phương pháp sử dụng trong chương trình dưới đây
Lấy phần dư của số đầu vào đẩy vào stack, chia số cho 10 cho đến khi số = 0. Stack sẽ có chữ số đầu tiên ở đỉnh. Sau đó lấy từng phần tử từ stack xây dựng số đảo ngược.
Nhập số Num.
Tạo stack rỗng stack<int> stck.
Hàm pushDigts(int num1) đẩy các chữ số vào stack với chữ số đầu ở đỉnh.
Biến rem. While num1 > 0: rem = num1%10; push rem; num1 /= 10.
Hàm revrseNum() xây dựng số đảo ngược từ stack.
Biến revrs=0, i=1, temp, topp. While stack không rỗng: topp = top(); pop(); temp = topp*i; revrs += temp; i *= 10.
Trả về revrs.
In kết quả trong main.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; stack <int> stck; void pushDigts(int num1){ int rem; while (num1 > 0){ rem=num1 % 10; stck.push(rem); num1 = num1 / 10; } } int revrseNum(){ int revrs = 0; int i = 1; int temp; int topp; while (!stck.empty()){ topp=stck.top(); stck.pop(); temp=topp*i; revrs = revrs + temp; i *= 10; } return revrs; } int main(){ int Num = 43556; pushDigts(Num); cout<<"Số đảo ngược là: "<<revrseNum(); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Số đảo ngược là: 65534