算法导论第十章 栈队列和链表
本章讲述的是基本的数据结构，如栈、队列和链表。这些都是最最基本的数据结构，具体的就不再啰嗦。然后本章也没有什么需要特别注意的点，哦，有一个小节：指针和对象的实现，可以认真看一下，大概就是用其他的实现方式来代替指针和对象的实现，因为有些语言不支持指针和对象数据类型，那在实现这种链式的数据结构就无法表示，本节介绍的方法就是利用数组和数组下标来构造对象和指针，说白了，就是利用数组来表示链式对象。个人感觉意义不大，权当了解得了。
结合一些常见的笔试面试题，我就用3个习题来总结这一章吧。
1、习题10.1-6：说明如何用两个栈实现一个队列，并分析相关队列操作的运行时间。
两个栈实现一个队列和两个队列实现一个栈的思路都是一样的。
算法思路：
1）StackA和StackB，StackA作为存储栈，StackB作为辅助栈；
2）入队列操作：假如StackA中有元素，则首先将StackA中元素出栈放入StackB中，再把入队列元素放入StackA，然后再把StackB中的元素出栈放入StackA中
3）出队列操作：以上操作保证先入队列的元素先出，所以，直接从StackA中出栈即可。
如下直观的图示：
代码如下：
1 #include <iostream> 2 #include <stack> 3 #include <cstdlib> 4 5 using namespace std; 6 7 /************************************************************************/ 8 /* 两个栈实现队列 9 /* 采用C++模板是实现 10 /************************************************************************/ 11 template<class T> 12 class StackQueue 13 { 14 public: 15 StackQueue(){} 16 ~StackQueue(){} 17 18 void Enqueue(const T& elem); 19 T Dequeue(); 20 bool Empty() const; 21 22 private: 23 stack<T> m_stackA; 24 stack<T> m_stackB; 25 }; 26 27 template<class T> 28 void StackQueue<T>::Enqueue(const T& elem) 29 { 30 if (m_stackA.empty()) 31 m_stackA.push(elem); 32 else { 33 while (!m_stackA.empty()) { 34 m_stackB.push(m_stackA.top()); 35 m_stackA.pop(); 36 } 37 m_stackA.push(elem); 38 } 39 40 while(!m_stackB.empty()) { 41 m_stackA.push(m_stackB.top()); 42 m_stackB.pop(); 43 } 44 } 45 46 template<class T> 47 T StackQueue<T>::Dequeue() 48 { 49 T retElem; 50 if (!m_stackA.empty()) { 51 retElem = m_stackA.top(); 52 m_stackA.pop(); 53 } 54 return retElem; 55 } 56 57 template<class T> 58 bool StackQueue<T>::Empty() const 59 { 60 if (m_stackA.empty()) 61 return true; 62 else 63 return false; 64 } 65 66 // int main() 67 // { 68 // StackQueue<int> SQ; 69 // for (int i = 1; i <= 5; i ++) { 70 // SQ.Enqueue(i); 71 // } 72 // 73 // for (int i = 1; i <= 5; i ++) { 74 // cout << SQ.Dequeue(); 75 // } 76 // return 0; 77 // }
2、习题10.1-7：说明如何用两个队列实现一个栈，并分析相关栈操作的运行时间。
该算法思路与上题一样，本处就不再赘述。直接贴代码吧：
1 #include <iostream> 2 #include <queue> 3 4 using namespace std; 5 6 /************************************************************************/ 7 /* 两个队列实现一个栈 8 /* 使用C++模板的形式 9 /************************************************************************/ 10 template<class T> 11 class QueueStack { 12 public: 13 QueueStack(){} 14 ~QueueStack(){} 15 16 void Push(const T& elem); 17 void Pop(); 18 T Top() const; 19 20 private: 21 queue<T> m_queueA; 22 queue<T> m_queueB; 23 }; 24 25 template<class T> 26 void QueueStack<T>::Push(const T& elem) 27 { 28 if (m_queueA.empty()) 29 m_queueA.push(elem); 30 else { 31 while (!m_queueA.empty()) { 32 m_queueB.push(m_queueA.front()); 33 m_queueA.pop(); 34 } 35 m_queueA.push(elem); 36 } 37 while (!m_queueB.empty()) { 38 m_queueA.push(m_queueB.front()); 39 m_queueB.pop(); 40 } 41 } 42 43 template<class T> 44 void QueueStack<T>::Pop() 45 { 46 if (!m_queueA.empty()) 47 m_queueA.pop(); 48 } 49 50 template<class T> 51 T QueueStack<T>::Top() const 52 { 53 T nElem; 54 if (!m_queueA.empty()) 55 nElem = m_queueA.front(); 56 return nElem; 57 } 58 59 // int main() 60 // { 61 // QueueStack<int> QS; 62 // for (int i = 1; i <= 5; i ++) { 63 // QS.Push(i); 64 // } 65 // 66 // for (int i = 1; i <= 5; i ++) { 67 // cout << QS.Top(); 68 // QS.Pop(); 69 // } 70 // return 0; 71 // }
3、习题10.2-7：给出一个O(n)时间的非递归过程，实现对一个含n个元素的单链表的逆转，要求出存储链表本身所需空间外，该过程只能使用固定大小的存储空间。
由于限制了时间和空间，所以只能通过就地逆转来实现，结合单链表的特性，能想到的就是改变指针的指向，我们可以用三个指针来指向链表中的元素，使之满足这样的关系：p->q->r。也不太好描述，看下面一个图示吧：
代码如下：
1 #include <iostream> 2 3 using namespace std; 4 5 template<class T> 6 class Node 7 { 8 public: 9 template<class T> friend class SingleLink; 10 11 //Node(Node *pNext = NULL):m_pNext(pNext) {} 12 Node(T key = (T)0, Node *pNext = NULL):m_key(key), m_pNext(pNext) {} 13 ~Node(){} 14 15 private: 16 T m_key; 17 Node *m_pNext; 18 }; 19 20 template<class T> 21 class SingleLink 22 { 23 public: 24 SingleLink(Node<T> *pHead = NULL):m_pHead(pHead) {} 25 ~SingleLink(){} 26 27 void Insert(const T& ); 28 void Delete(const T& ); 29 30 void Reverse(); 31 32 void Print(); 33 34 private: 35 Node<T> *m_pHead; 36 }; 37 38 //有序地插入 39 template<class T> 40 void SingleLink<T>::Insert(const T& key) 41 { 42 Node<T> *pInsert = new Node<T>(key); 43 if (NULL == m_pHead) 44 m_pHead = pInsert; 45 else { 46 Node<T> *pTemp = m_pHead; 47 Node<T> *qTemp = NULL; 48 while (pTemp) { 49 if (pTemp->m_key <= key) { 50 qTemp = pTemp; 51 pTemp = pTemp->m_pNext; 52 } 53 else break; 54 } 55 pInsert->m_pNext = pTemp; 56 qTemp->m_pNext = pInsert; 57 } 58 } 59 60 template<class T> 61 void SingleLink<T>::Delete(const T& key) 62 { 63 if (NULL == m_pHead) 64 return; 65 66 if (m_pHead->m_key == key) 67 m_pHead = NULL; 68 else { 69 Node<T> *pTemp = m_pHead; 70 Node<T> *pDelete = m_pHead->m_pNext; 71 while (pDelete) { 72 if (pDelete->m_key != key) { 73 pTemp = pDelete; 74 pDelete = pDelete->m_pNext; 75 } 76 else { 77 pTemp->m_pNext = pDelete->m_pNext; 78 break; 79 } 80 } 81 } 82 } 83 84 template<class T> 85 void SingleLink<T>::Reverse() 86 { 87 //only one element 88 if (NULL == m_pHead || NULL == m_pHead->m_pNext) 89 return; 90 91 //p->q->r 92 Node<T> *p = NULL, *q = m_pHead, *r = NULL; 93 while (true) { 94 r = q->m_pNext; 95 q->m_pNext = p; 96 97 if (NULL == r) { 98 m_pHead = q; 99 break; 100 } 101 p = q; 102 q = r; 103 } 104 } 105 106 template<class T> 107 void SingleLink<T>::Print() 108 { 109 Node<T> *pTemp = m_pHead; 110 while (pTemp) { 111 cout << pTemp->m_key << " "; 112 pTemp = pTemp->m_pNext; 113 } 114 cout << endl; 115 } 116 117 int main() 118 { 119 SingleLink<int> SL; 120 for (int i = 1; i <= 5; i ++) 121 SL.Insert(i); 122 SL.Print(); 123 SL.Insert(9); 124 SL.Insert(7); 125 SL.Print(); 126 SL.Delete(7); 127 SL.Print(); 128 SL.Delete(6); 129 SL.Print(); 130 SL.Reverse(); 131 SL.Print(); 132 return 0; 133 }