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

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏高性能服务器开发

(三)dict哈希结构3

/* This function performs just a step of rehashing, and only if there are * no...

2778
来自专栏葡萄城控件技术团队

深入浅出OOP(五): C#访问修饰符(Public/Private/Protected/Internal/Sealed/Constants)

访问修饰符(或者叫访问控制符)是面向对象语言的特性之一,用于对类、类成员函数、类成员变量进行访问控制。同时,访问控制符也是语法保留关键字,用于封装组件。 Pub...

3239
来自专栏西二旗一哥

Conclusion of objective-C structure

1193
来自专栏开发与安全

数据结构:两栈共享存储空间

数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另一个栈为栈的末端,即下标为数组长度 n-1处。这样,如果两个栈增加元素,就是两端点...

2675
来自专栏Jed的技术阶梯

图解 Java 位运算

需要说明的是,在计算机中,数字是以补码的形式存在的,计算也是用补码来进行计算,计算后的结果也是补码

5092
来自专栏扎心了老铁

java优雅的使用elasticsearch api

本文给出一种优雅的拼装elasticsearch查询的方式,可能会使得使用elasticsearch的方式变得优雅起来,使得代码结构很清晰易读。 建立elast...

1.1K7
来自专栏码匠的流水账

聊聊spring cloud gateway的GatewayFilter

本文主要研究一下spring cloud gateway的GatewayFilter

5261
来自专栏ml

位运算的方法,大结

Title:       位操作基础篇之位操作全面总结 Author:     MoreWindows E-mail:      morewindows@126...

6148
来自专栏用户画像

C++实现斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而...

571
来自专栏我是攻城师

Fastjson解析嵌套Map例子

3995

扫码关注云+社区

领取腾讯云代金券