【数据结构笔记】栈的实现（C++）
栈的概念 栈是限定仅在表尾进行插入和删除操作的线性表。“栈”者，存储货物或供旅客住宿的地方，可引申为仓库、中转站，引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。 这里我们基于数组与链表实现栈。栈的数组实现 栈的顺序存储结构简称为顺序栈（就是用一组地址连续的存储单元一次存放栈底到栈顶的数据元素）。 #pragma once const int maxstack = 10; // small value for testing typedef float Stack_entry; // The program will use stacks with float entries. enum Error_code {//枚举状态 success, fail, range_error, underflow, overflow, fatal, not_present, duplicate_error, entry_inserted, entry_found, internal_error }; class Stack { public: Stack(); bool empty() const;//判空 Error_code pop();//入栈 Error_code top(Stack_entry& item) const;//读取栈顶元素 Error_code push(const Stack_entry& item);//出栈 private: int count; Stack_entry entry[maxstack]; }; Stack::Stack() { count = 0; } Error_code Stack::push(const Stack_entry& item) { Error_code outcome = success; if (count >= maxstack) outcome = overflow; else entry[count++] = item; return outcome; } Error_code Stack::top(Stack_entry& item) const { Error_code outcome = success; if (count == 0) outcome = underflow; else item = entry[count - 1]; return outcome; } bool Stack::empty() const { bool outcome = true; if (count > 0) outcome = false; return outcome; //return count==0; } Error_code Stack::pop() { Error_code outcome = success; if (count == 0) outcome = underflow; else --count; return outcome; } 栈的链表实现 栈的链式存储结构称为链栈，链栈通常可以使用不带头节点的单链表表示，而头指针top就是栈顶指针head。 struct Node { Node_entry entry; Node *next; Node(); Node(Node_entry item, Node *add_on = NULL); }; Node::Node() { next = NULL; } Node::Node(Node_entry item, Node *add_on) { entry = item; next = add_on; } class Stack { public: Stack(); bool empty() const; Error_code push(const Stack_entry &item); Error_code pop(); Error_code top(Stack_entry &item) const; ~Stack(); Stack(const Stack &original); void operator =(const Stack &original); protected: Node *top_node; }; bool Stack::empty() const { return count==0; } Error_code Stack::push(const Stack_entry &item) { Node *new_top = new Node(item, top_node); if (new_top == NULL) return overflow; top_node = new_top; return success; } Error_code Stack::pop() { Node *old_top = top_node; if (top_node == NULL) return underflow; top_node = old_top->next; delete old_top; return success; } Error_code Stack::push(Stack_entry item) { Node new_top(item, top_node); top_node = new_top; return success; } Stack::~Stack() // Destructor { while (!empty()) pop(); } void Stack::operator = (const Stack &original) // Overload assignment { Node *new_top, *new_copy, *original_node = original.top_node; if (original_node == NULL) new_top = NULL; else { // Duplicate the linked nodes new_copy = new_top = new Node(original_node->entry); while (original_node->next != NULL) { original_node = original_node->next; new_copy->next = new Node(original_node->entry); new_copy = new_copy->next; } } while (!empty()) // Clean out old Stack entries pop(); top_node = new_top; // and replace them with new entries. } Stack::Stack(const Stack &original) // copy constructor { Node *new_copy, *original_node = original.top_node; if (original_node == NULL) top_node = NULL; else { // Duplicate the linked nodes. top_node = new_copy = new Node(original_node->entry); while (original_node->next != NULL) { original_node = original_node->next; new_copy->next = new Node(original_node->entry); new_copy = new_copy->next; } } } void Stack::operator = (const Stack &original) { Stack new_copy(original); top_node = new_copy.top_node; }