栈和队列
实现一个栈
Last-in First-Out。
用链表实现的做法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <iostream>
template <typename T>
class ListNode
{
public:
T val;
ListNode* next;
ListNode(T x) : val(x), next(NULL){}
};
template <typename T>
class Stack
{
public:
Stack() : top_node(NULL){}
void pop()
{
if (top_node)
{
ListNode<T>* t = top_node;
top_node = top_node->next;
delete(t);
}
}
void push(T item)
{
ListNode<T>* t = new ListNode<T>(item);
t->next = top_node;
top_node = t;
}
T top()
{
if (top_node)
{
return top_node->val;
}
return T();
}
bool empty() {return top_node == 0;}
size_t size()
{
size_t len(0);
ListNode<T>* node(top_node);
while (node)
{
++len;
node = node->next;
}
return len;
}
protected:
ListNode<T>* top_node;
};
int main()
{
Stack<int> st;
st.push(1);
st.push(2);
st.push(3);
std::cout << "Size: " << st.size() << std::endl;
std::cout << "Data: ";
while (!st.empty())
{
std::cout << st.top() << " ";
st.pop();
}
system("Pause");
}
|
实现一个队列
First-in First-Out。
用链表实现的做法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <iostream>
template <typename T>
class ListNode
{
public:
T val;
ListNode* next;
ListNode(T x) : val(x), next(NULL){}
};
template <typename T>
class Queue
{
public:
Queue() : front_node(NULL), back_node(NULL){}
void pop()
{
if (front_node)
{
ListNode<T>* t = front_node;
front_node = front_node->next;
delete t;
}
}
void push(T item)
{
ListNode<T>* t = new ListNode<T>(item);
if (!front_node)
{
front_node = back_node = t;
}
back_node->next = t;
back_node = t;
}
T front()
{
if (front_node)
{
return front_node->val;
}
return T();
}
bool empty() {return front_node == 0;}
size_t size()
{
size_t len(0);
ListNode<T>* node(front_node);
while (node)
{
++len;
node = node->next;
}
return len;
}
protected:
ListNode<T>* front_node;
ListNode<T>* back_node;
};
int main()
{
Queue<int> st;
st.push(1);
st.push(2);
st.push(3);
std::cout << "Size: " << st.size() << std::endl;
std::cout << "Data: ";
while (!st.empty())
{
std::cout << st.front() << " ";
st.pop();
}
system("Pause");
}
|
STL中Stack和Queue的实现
STL Stack
STL Queue
STL Priority Queue
leetcode相关题目(栈)
Valid Parentheses
Longest Valid Parentheses
Largest Rectangle in Histogram
Evaluate Reverse Polish Notation
更多题目
1. 用两个栈实现一个队列。队列的声明如下，请实现两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
1
2
3
4
5
6
7
8
9
10
11
| template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
|
分析：插入元素：到stack1。删除元素：如果stack2不为空，stack2的栈顶元素弹出。如果stack2为空，把stack1中的元素逐个弹出并压入stack2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| template <typename T>
void CQueue<T>::appendTail(const T& node)
{
stack1.push(node);
}
template <typename T>
T CQueue<T>::deleteHead()
{
if (stack2.empty())
{
while (!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
}
if (stack2.empty()) {throw new exception("queue is empty");}
T head = stack2.top();
stack2.pop();
return head;
}
|
测试用例
- 往空的队列里添加、删除元素。
- 往非空的队列里添加、删除元素。
- 连续删除元素直至队列为空。
2. 用两个队列实现一个栈
分析：要删除元素的时候，把有元素的queue里的元素移到另一个空queue，最后处理的那个元素就是队尾，也就是最新的元素，就删他。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <iostream>
#include <queue>
#include <exception>
template <typename T>
class CStack
{
public:
void appendtail(const T& node)
{
if (!queue2.empty()) {queue2.push(node);}
else {queue1.push(node);}
}
T deleteHead()
{
if (!queue1.empty()) {
while (queue1.size() > 1)
{
queue2.push(queue1.front());
queue1.pop();
}
T head = queue1.front();
queue1.pop();
return head;
}
if (!queue2.empty()) {
while (queue2.size() > 1)
{
queue1.push(queue2.front());
queue2.pop();
}
T head = queue2.front();
queue2.pop();
return head;
}
else {std::cout << "Empty Stack" << std::endl;}
}
private:
std::queue<T> queue1;
std::queue<T> queue2;
};
int main()
{
CStack<int> hah;
hah.appendtail(1);
hah.appendtail(2);
hah.appendtail(3);
std::cout << hah.deleteHead() << " ";
std::cout << hah.deleteHead() << " ";
std::cout << hah.deleteHead() << " ";
std::cout << hah.deleteHead() << " ";
system("Pause");
}
|
[1] Cracking the Coding Interview
[2] leetcode
[3] 剑指Offer