我想在c++中开发一个函数，它将取两个排序的堆栈a和B(最小在上)，并且创建一个合并和排序的新堆栈(最小在上)。
只允许使用最小的标准堆栈操作，如pop, push, size和top。
对于该任务，不允许使用其他数据结构，如数组。
栈应该通过一个单链表实现，因此，有一个stack类和一个Node类。
我想出了下面的尝试，这不起作用。
堆栈中的元素顺序错误。Current output: 10 9 8 7 6 5 4 3 2 1
Expected Output: 1 2 3 4 5 6 7 8 9 10
如何正确地做到这一点?
请参阅下面我的不工作代码:
#include <initializer_list>
#include <iostream>
// Node class for a minimum singly linked list
struct Node {
int data{}; // Data part
Node* next{}; // Link
};
// Stack, implemented as singly linked list with only minimum necessary functions
class Stack {
Node* head{}; // Head of singly linked list
int numberOfElements{}; // Housekeeping. Stack size
public:
Stack() {}; // Default constructor. Do nothing
// Convenience function. Build stack from initailizer list
Stack(const std::initializer_list<int>& il) { for (const int i : il) push(i); }
// And destructor, will release memory
~Stack() {
Node* temp = head; // Start with the head
while (temp) { // Iterate along the list
Node* toDelete = temp; // Remember Node that must be deleted
temp = temp->next; // Goto next element
delete toDelete; // Delete Remebered Element
}
}
void push(const int value) { // Push a new element onto the stack. Insert at beginning
Node* temp = new Node; // Allocate memory for a new node
temp->data = value; // Assign data part to new Node
temp->next = head; // This will be the new head, so, next will point to previous head
head = temp; // Set head pointer to new Node
++numberOfElements; // Bookkeeping, incremenent size
}
void pop() { // Simply dlete the first element in the linked list
if (head) { // If there is something in the list at all
Node* temp = head; // Remember current head Node
head = head->next; // New head will be the current heads next node
delete temp; // Delete old head
--numberOfElements; // Bookkeeping, decremenent size
}
};
int top() const { return head ? head->data : 0; } // Simply retun data from head node
int size() const { return numberOfElements; } // expose size to outside world
void print() { // Helper for printing debug output
Node* temp = head; // We will iterate over the list beginning at the head
while (temp) { // As long as we are not at the end of the list
std::cout << temp->data << ' '; // Show data
temp = temp->next; // And continue with next node
}
std::cout << 'n';
}
};
// This is the function that needs to be done
void mergeSortedStacks(Stack& s1, Stack& s2, Stack& merged) {
// As long as there are elements in s1 or in s1
while (s1.size() or s2.size()) {
// If there are elements in both s1 and s2
if (s1.size() and s2.size()) {
// Which top element is smaller?
if (s1.top() < s2.top()) {
// S1 top is smaller. push on resulting output stack
merged.push(s1.top());
s1.pop();
}
else {
// S2 top is smaller. push on resulting output stack
merged.push(s2.top());
s2.pop();
}
}
// Only s1 has still some elements
else if (s1.size()) {
// Copy them to other stack
merged.push(s1.top());
s1.pop();
}
// Only s2 has still some elements
else if (s2.size()) {
merged.push(s2.top());
s2.pop();
}
}
}
// Test
int main() {
Stack s1{ 10, 8, 6, 4 ,2 };
s1.print();
Stack s2{ 9, 7, 5, 3, 1};
s2.print();
Stack m{};
mergeSortedStacks(s1, s2, m);
m.print();
}
你的主意不错。
基本上我不会改变那么多。只需反转结果堆栈中的值。这可以通过一个临时堆栈来实现。
top/pop的元素从一个堆栈，然后把它到产生的堆栈。这一切。
请见:
#include <initializer_list>
#include <iostream>
// Node class for a minimum singly linked list
struct Node {
int data{}; // Data part
Node* next{}; // Link
};
// Stack, implemented as singly linked list with only minimum necessary functions
class Stack {
Node* head{}; // Head of singly linked list
int numberOfElements{}; // Housekeeping. Stack size
public:
Stack() {}; // Default constructor. Do nothing
// Convenience function. Build stack from initailizer list
Stack(const std::initializer_list<int>& il) { for (const int i : il) push(i); }
// And destructor, will release memory
~Stack() {
Node* temp = head; // Start with the head
while (temp) { // Iterate along the list
Node* toDelete = temp; // Remember Node that must be deleted
temp = temp->next; // Goto next element
delete toDelete; // Delete Remebered Element
}
}
void push(const int value) { // Push a new element onto the stack. Insert at beginning
Node* temp = new Node; // Allocate memory for a new node
temp->data = value; // Assign data part to new Node
temp->next = head; // This will be the new head, so, next will point to previous head
head = temp; // Set head pointer to new Node
++numberOfElements; // Bookkeeping, incremenent size
}
void pop() { // Simply dlete the first element in the linked list
if (head) { // If there is something in the list at all
Node* temp = head; // Remember current head Node
head = head->next; // New head will be the current heads next node
delete temp; // Delete old head
--numberOfElements; // Bookkeeping, decremenent size
}
};
int top() const { return head ? head->data : 0; } // Simply retun data from head node
int size() const { return numberOfElements; } // expose size to outside world
void print() { // Helper for printing debug output
Node* temp = head; // We will iterate over the list beginning at the head
while (temp) { // As long as we are not at the end of the list
std::cout << temp->data << ' '; // Show data
temp = temp->next; // And continue with next node
}
std::cout << 'n';
}
};
void mergeSortedStacks(Stack& s1, Stack& s2, Stack& merged) {
Stack tempStack{}; // ****** New
// As long as there are elements in s1 or in s1
while (s1.size() or s2.size()) {
// If there are elements in both s1 and s2
if (s1.size() and s2.size()) {
// Which top element is smaller?
if (s1.top() < s2.top()) {
// S1 top is smaller. push on resulting output stack
tempStack.push(s1.top());
s1.pop();
}
else {
// S2 top is smaller. push on resulting output stack
tempStack.push(s2.top());
s2.pop();
}
}
// Only s1 has still some elements
else if (s1.size()) {
// Copy them to other stack
tempStack.push(s1.top());
s1.pop();
}
// Only s2 has still some elements
else if (s2.size()) {
tempStack.push(s2.top());
s2.pop();
}
}
// Reverse stack *****
const int stacksize = tempStack.size();
for (int i = 0; i < stacksize; ++i) {
merged.push(tempStack.top());
tempStack.pop();
}
}
// Test
int main() {
Stack s1{ 10, 8, 6, 4 ,2 };
s1.print();
Stack s2{ 9, 7, 5, 3, 1};
s2.print();
Stack m{};
mergeSortedStacks(s1, s2, m);
m.print();
}