算法导论第十章 栈队列和链表

简介:   本章讲述的是基本的数据结构,如栈、队列和链表。这些都是最最基本的数据结构,具体的就不再啰嗦。然后本章也没有什么需要特别注意的点,哦,有一个小节:指针和对象的实现,可以认真看一下,大概就是用其他的实现方式来代替指针和对象的实现,因为有些语言不支持指针和对象数据类型,那在实现这种链式的数据结构就无法表示,本节介绍的方法就是利用数组和数组下标来构造对象和指针,说白了,就是利用数组来表示链式对象。

  本章讲述的是基本的数据结构,如栈、队列和链表。这些都是最最基本的数据结构,具体的就不再啰嗦。然后本章也没有什么需要特别注意的点,哦,有一个小节:指针和对象的实现,可以认真看一下,大概就是用其他的实现方式来代替指针和对象的实现,因为有些语言不支持指针和对象数据类型,那在实现这种链式的数据结构就无法表示,本节介绍的方法就是利用数组和数组下标来构造对象和指针,说白了,就是利用数组来表示链式对象。个人感觉意义不大,权当了解得了。

  结合一些常见的笔试面试题,我就用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 // }
View Code

 

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 // }
View Code

 

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 }
View Code

 

目录
相关文章
|
4天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
77 64
|
16天前
|
存储 算法 前端开发
深入理解操作系统:进程调度与优先级队列算法
【9月更文挑战第25天】在操作系统的复杂世界中,进程调度是维持系统稳定运行的核心机制之一。本文将深入探讨进程调度的基本概念,分析不同的进程调度算法,并着重介绍优先级队列算法的原理和实现。通过简洁明了的语言,我们将一起探索如何优化进程调度,提高操作系统的效率和响应速度。无论你是计算机科学的初学者还是希望深化理解的专业人士,这篇文章都将为你提供有价值的见解。
|
3天前
|
算法 C++
【算法单调栈】 矩形牛棚(C/C++)
【算法单调栈】 矩形牛棚(C/C++)
|
2月前
|
缓存 算法 Java
刷算法,你应该知道的队列经典应用
文章介绍了队列的基本特性和经典应用,包括如何用队列实现栈、使用优先级队列解决Top K问题,并通过LeetCode题目示例展示了队列在算法实现中的应用。
刷算法,你应该知道的队列经典应用
|
2月前
|
算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
|
2月前
|
算法
【数据结构与算法】优先级队列
【数据结构与算法】优先级队列
14 0
|
2月前
|
存储 算法
【数据结构与算法】队列(顺序存储)
【数据结构与算法】队列(顺序存储)
17 0
|
2月前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
15 0
|
2月前
|
算法
【数据结构与算法】双向链表
【数据结构与算法】双向链表
16 0
|
2月前
|
算法
【数据结构与算法】循环链表
【数据结构与算法】循环链表
17 0

热门文章

最新文章