链式栈和队列.doc

1、 定义： 链式结构：The idea of a linked list is to augment every element of a list structure with a pointer giving the location of the next element in the list.Linked stack: a stack implemented by linked structure.Linked Queue: a queue implemented by linked structure.2、 实现： Linked Stack: *Node.h: *Node.h:#ifndef NODE_H#define NODE_H#include typedef double Node_entry;typedef Node_entry Stack_entry;struct NodeNode_entry entry;Node *next;Node()next = NULL;Node(Node_entry item, Node* add = NULL)entry = item;next = add;#endif*LinkedStack.h:class Stack public:/ Standard Stack methods Stack(); bool empty() const; Error_code push(const Stack_entry &item); Error_code pop(); Error_code top(Stack_entry &item) const;/ Safety features for linked structures Stack(); Stack(const Stack &original); void operator =(const Stack &original);protected: Node *top_node;LinkedStack.cpp: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; Linked Queue: *Node.h:#ifndef NODE_H#define NODE_H#include typedef double Node_entry;typedef Node_entry Queue_entry;struct NodeNode_entry entry;Node *next;Node()next = NULL;Node(Node_entry item, Node* add = NULL)entry = item;next = add;#endif*LinkedQueue.h:#ifndef LINKED_QUEUE_H#define LINKED_QUEUE_Henum Error_codesuccess,overflow,underflow;#include Node.hclass LinkedQueuepublic:LinkedQueue();LinkedQueue(const LinkedQueue &original);LinkedQueue();bool empty() const;Error_code append(const Queue_entry &item);Error_code serve();Error_code retrieve(Queue_entry &item) const;void operator = (const LinkedQueue& original);protected:Node *front,*rear;#endif*LinkedQueue.cpp:#include LinkedQueue.hLinkedQueue:LinkedQueue()front = rear = NULL;LinkedQueue:LinkedQueue(const LinkedQueue &original)Node *new_front,*copy_front = original.front;if(copy_front != NULL)front = new_front = new Node(copy_front-entry);while (copy_front-next != NULL)copy_front = copy_front-next;new_front -next = new Node(copy_front-entry);new_front = new_front-next;rear = new_front;rear-next = NULL;elsefront = rear = NULL;LinkedQueue:LinkedQueue()while (!empty()serve();bool LinkedQueue:empty() constreturn(rear = NULL);Error_code LinkedQueue:append(const Queue_entry &item)Node *new_rear = new Node(item);if(new_rear = NULL)return overflow;else if(rear = NULL)front = rear = new_rear;elserear-next = new_rear;rear = new_rear;return success;Error_code LinkedQueue:retrieve(Queue_entry &item)constif(rear = NULL)return underflow;item = front-entry;return success;Error_code LinkedQueue:serve()if(front = NULL)return underflow;Node *old_front = front;front = old_