常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn 数据结构（三） 常宝宝 北京大学计算机科学与技术系 chbb@pku.edu.cn

内容提要 栈 队列 栈和队列是两种特殊的线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表。 栈和队列广泛地应用在各种软件系统中，是程序设计中必须掌握的两种基本数据结构。

什么是栈？ 若限定仅在线性表的一端进行插入和删除操作，这样的线性表称为栈。 能够进行插入和删除操作的一端称为栈顶。另一端则相应称为栈底。 位于栈顶的元素称为栈顶元素，位于栈底的元素称为栈底元素。 不含任何元素的栈称为空栈。 栈的特点是后进先出。 (Last In First Out: LIFO) 上溢和下溢

和栈有关的操作 和栈有关的操作： 构造一个不含任何元素的空栈 判断栈是否为空栈 判断栈是否满 返回栈中的元素个数 清空栈 向栈顶压入(添加)一个元素 从栈顶弹出(删除)一个元素 读取栈顶元素

栈作为抽象数据类型 template <typename stack_entry> class Stack { public: enum error_code { success, overflow, underflow}; protected: ... public: //操作 Stack(); Stack(const Stack& copy); ~Stack(); bool empty() const; bool full() const; int size(); void clear(); error_code push(const stack_entry& item); error_code pop(); error_code top(stack_entry& item) const; };

栈操作 Stack<stack_entry>::Stack(); // PRECONDITION: // POSTCONDITION: 建立了一个空栈 error_code① Stack<stack_entry>::pop(); // PRECONDITION: 栈非空 // POSTCONDITION: 栈顶部的元素被删除 // REMARKS: 若栈非空,栈顶元素被删除,若栈是空栈,返回错误代码underflow error_code Stack<sack_entry>::push(const stack_entry& item); // PRECONDITION: 栈未满 // POSTCONDITION: 元素item被加入到栈的顶部 // REMARKS: 若栈未满,元素item被加入到栈的顶部,若栈已满,返回overflow ① 在实际实现时，error_code 应写作 Stack<stack_entry>::error_code

栈操作 error_code Stack<stack_entry>::top(stack_entry& item) const; // PRECONDITION: 栈非空 // POSTCONDITION: 栈的状态未发生变化 // REMARKS: 若栈非空,栈顶元素被读入item中,若栈是空栈,返回错误 // 代码underflow bool Stack<stack_entry>::empty() const; // PRECONDITION: // POSTCONDITION: 栈的状态未发生变化 // REMARKS: 若栈是空栈,返回true,若栈不是空栈,返回false

栈结构的使用 int main() { Stack<int> intStack; //创建一个元素类型是整数的空栈 int n,item; cout << “Type in an integer n followed by n numbers” << endl; cin >> n; for (int i=0; i<n; i++ ) { cin >> item; intStack.push(item); //将整数item压入栈中 } cout << endl; while ( !intStack.empty() ) { //判断栈是否空栈 intStack.top(item); //读取位于栈顶的整数 cout << item << “ “; intStack.pop(); //将栈顶的整数弹出 } cout << endl; }

栈的实现 —顺序存储 和线性表类似，栈也有两种存储结构： (1) 顺序存储 (2) 链式存储。 和线性表类似，栈也有两种存储结构： (1) 顺序存储 (2) 链式存储。 顺序存储： 用一组连续的存储单元依次存放自栈底到栈顶的数据元素。

栈的实现 —顺序存储 template <typename stack_entry, int max_entry=100> class Stack { public: enum error_code { success, overflow, underflow}; protected: int count; stack_entry entry[max_entry]; public: //操作 Stack(); Stack(const Stack& copy); ~Stack(); bool empty() const; ... error_code push(const stack_entry& item); error_code pop(); error_code top(stack_entry& item) const; };

栈的实现 —顺序存储 template <typename stack_entry, int max_entry> Stack<stack_entry, max_entry>::Stack() { count = 0; } template <typename stack_entry, int max_entry> Stack<stack_entry, max_entry>::error_code Stack<stack_entry, max_entry>::pop() { if ( count == 0 ) return underflow; count--; return success; } template <typename stack_entry, int max_entry> Stack<stack_entry, max_entry>::error_code Stack<stack_entry, max_entry>::push(const stack_entry& item){ if ( count == max_entry ) return overflow; entry[count++]=item; return success; }

栈的实现 —顺序存储 template <typename stack_entry, int max_entry> Stack<stack_entry, max_entry>::error_code Stack<stack_entry, max_entry>::top(stack_entry& item) const { if ( count == 0 ) return underflow; item=entry[count-1]; return success; } x template <typename stack_entry, int max_entry> bool Stack<stack_entry, max_entry>::empty() const { if ( count == 0 ) return true; return false; }

栈的实现 —链式存储 在栈的链式实现中，栈被组织成一个链表。 栈顶指针 在链式存储的栈中： (1) 压入元素 (2) 弹出元素

栈的实现 —链式存储 template <typename stack_entry> class Stack { public: enum error_code { success, overflow, underflow}; protected: struct node { stack_entry entry; node *next; node():next(0) {} node(const stack_entry &se, node* link= NULL):entry(se), next(link) {} }; node* top_node; public: //操作 Stack(); ... error_code pop(); error_code top(stack_entry& item) const; };

栈的实现 —链式存储 template <typename stack_entry> Stack<stack_entry>::Stack() { top_node = NULL; } template <typename stack_entry> Stack<stack_entry>::error_code Stack<stack_entry>::pop() { if (top_node == NULL) return underflow; node* oldtop = top_node; top_node = top_node->next; delete oldtop; return success; } template <typename stack_entry> Stack<stack_entry>::error_code Stack<stack_entry>::push(const stack_entry& item){ node* newtop = new node(item, top_node); if ( newtop == NULL ) return overflow; top_node = newtop; return success; }

栈的实现 —链式存储 template <typename stack_entry> Stack<stack_entry>::error_code Stack<stack_entry>::top(stack_entry& item) const { if ( top_node == 0 ) return underflow; item=top_node->entry; return success; } x template <typename stack_entry> bool Stack<stack_entry>::empty() const { if ( top_node == NULL ) return true; return false; }

什么是队列？ 若限定线性表仅能在一端进行插入，另一端进行删除，这样的线性表称为队列。 能够进行插入的一端称为队尾。能够进行删除的一端称为队头。 位于队尾的元素称为队尾元素，位于队头的元素称为队头元素。 不含任何元素的队列称为空队列。 队列的特点是先进先出。(First In First Out: FIFO)

和队列有关的操作 和队列有关的操作： 构造一个不含任何元素的空队列 判断队列是否空队列 判断队列是否满 返回队列中的元素个数 清空队列 在队尾加入一个元素 删除位于队头的元素 读取队头元素

队列作为抽象数据类型 template <typename queue_entry> class Queue { public: enum error_code { success, overflow, underflow}; protected: ... public: //操作 Queue(); Queue(const Queue& copy); ~Queue(); bool empty() const; bool full() const; int size() const; void clear(); error_code append(const queue_entry& x); error_code serve(); error_code retrieve(queue_entry& x) const; };

队列的使用 int main() { Queue<int> intQueue; //创建一个整型空队列 int x; for (int i = 0; i<10; i++ ) intQueue.append(i); //在队列尾部插入整数 while (!intQueue.empty()) { //判断队列是否空队列 intQueue.retrieve(x); //读取队列头部的元素 cout << x << “ ”; intQueue.serve(); //删除队列头部的元素 } cout << endl; }

队列的实现 —顺序存储 在队列的顺序实现中，用一组连续的存储单元存储队列中的元素。 (1) 队头固定 (2) 队头、队尾均不固定 (3) 循环数组 防止“假溢出” 已分配空间 未分配空间

队列的实现 —顺序存储 template <typename queue_entry, int max_entry=100> class Queue { public: enum error_code { success, overflow, underflow}; protected: int count; int front, rear; queue_entry entry[max_entry]; public: //操作 Queue(); Queue(const Queue& copy); ~Queue(); bool empty() const; bool full() const; int size() const; void clear(); error_code append(const queue_entry& x); error_code serve(); error_code retrieve(queue_entry& x) const; }; template <typename stack_entry, int max_entry=100> class Stack { public: enum error_code { success, overflow, underflow}; protected: int count; stack_entry entry[max_entry]; public: //操作 Stack(); Stack(const Stack& copy); ~Stack(); bool empty() const; error_code push(const stack_entry& item); error_code pop(); error_code top(stack_entry& item) const; };

队列的实现 —顺序存储 template <typename queue_entry, int max_entry> Queue<queue_entry, max_entry>::Queue() { count=0; rear=max_entry-1; front=0; } template <typename queue_entry, int max_entry> bool Queue<queue_entry, max_entry>::empty() const { if ( count==0 ) return true; return false; } template <typename queue_entry, int max_entry> Queue<queue_entry, max_entry>::error_code Queue<queue_entry, max_entry>::append(const queue_entry& x) { if ( count==max_entry ) return overflow; count++; rear = (rear+1)%max_entry; entry[rear]=x; return success; }

队列的实现 —顺序存储 template <typename queue_entry, int max_entry> Queue<queue_entry, max_entry>::error_code Queue<queue_entry, max_entry>::serve() { if ( count == 0 ) return underflow; count--; front = (front+1)%max_entry; return success; } template <typename queue_entry, int max_entry> Queue<queue_entry, max_entry>::error_code Queue<queue_entry, max_entry>::retrieve(queue_entry& x) const { if ( count == 0 ) return underflow; x = entry[front]; return success; }

队列的实现 —链式存储 在队列的链式实现中，队列被组织成一个链表。 队头指针和队尾指针 在链式存储的队列中：(1) 插入元素 (2) 删除出元素

队列的实现 —链式存储 template <typename queue_entry> class Queue { public: enum error_code { success, overflow, underflow}; protected: struct node { queue_entry entry; node *next; node():next(0) {} node(const queue_entry &qe, node* link= NULL):entry(qe), next(link) {} }; node *front, *rear; public: //操作 Queue(); ... error_code append(const queue_entry& x); error_code serve(); error_code retrieve(queue_entry& x) const; };

队列的实现 —链式存储 template <typename queue_entry> Queue<queue_entry>::Queue():front(NULL),rear(NULL) {} template <typename queue_entry> bool Queue<queue_entry>::empty() const { if ( front==NULL ) return true; return false; } template <typename queue_entry> Queue<queue_entry>::error_code Queue<queue_entry>::append(const queue_entry& x) { node* newrear = new node(x); if ( newrear==NULL ) return overflow; if ( rear==NULL ) front=rear=newrear; else { rear->next = newrear; rear = newrear; } return success; }

队列的实现 —链式存储 template <typename queue_entry> Queue<queue_entry>::error_code Queue<queue_entry>::serve() { if ( front == NULL ) return underflow; node* oldfront = front; front = front->next; if ( front==NULL ) rear = NULL; delete oldfront; return success; } template <typename queue_entry> Queue<queue_entry>::error_code Queue<queue_entry>::retrieve(queue_entry& x) const { if ( front == 0 ) return underflow; x = front->entry; return success; }

上机作业 在机器上用C++分别实现顺序存储和链式存储的栈结构。 在机器上用C++分别实现顺序存储和链式存储的队列结构。 在实现链式存储的栈结构和队列结构时，必须提供析构函数、拷贝构造函数和赋值运算符重载函数，为什么？