队列的两个主要操作：入队列、出队列
栈的两个主要操作：入栈、出栈
入队列对应入栈
出队列是出最早的，出栈是出最晚的
使用 360 浏览器，有个不错的功能是可以恢复标签，你关闭一个标签，这个标签就会进入待恢复表，如果待恢复表慢了，新加标签，最早的标签会消失，这是 FIFO 队列。
但是如果点击恢复标签队列，会恢复最近关闭的标签，也就是最晚进入待恢复表中的标签，所以这又是一种 LIFO 栈。
待恢复表既具有添加标签的 FIFO 队列性质，又具有恢复标签并移除标签的 LIFO 栈性质。
实现一个数据结构，使其既具有 FIFO 队列的性质，又具有 LIFO 栈的性质。
由于标签有很多，这里使用循环表来实现这个数据结构，早期的标签会随着新加入的标签被覆盖。
注意连续关闭两个相同的标签，第二次关闭时，不会将这个标签存入待恢复表中。
这个表主要有三个操作
·入队列
·出队列
·出栈
没有入栈，其实入栈也就是入队列。
实现：
1 #include <iostream>
2 using namespace std;
3
4 class Table360
5 {
6 private:
7 int capacity_;
8 int* data_;
9 int size_;
10 int head_;
11 int tail_;
12 public:
13 Table360(int c = 10) : capacity_(c)
14 {
15 data_ = new int[capacity_];
16 if (data_ == 0)
17 {
18 exit(1);
19 }
20 memset(data_, 0, sizeof (int) * capacity_);
21 size_ = 0;
22 head_ = 0;
23 tail_ = -1;
24 }
25 Table360(const Table360& t) : capacity_(t.capacity_)
26 {
27 data_ = new int[capacity_];
28 if (data_ == 0)
29 {
30 exit(1);
31 }
32 memset(data_, 0, sizeof (int) * capacity_);
33 size_ = t.size_;
34 head_ = t.head_;
35 tail_ = t.tail_;
36 for (int i = 0; i < size_; ++i)
37 {
38 data_[(head_+i) % capacity_] = t.data_[(t.head_ + i) % t.capacity_];
39 }
40 }
41 void swap_(Table360& t)
42 {
43 swap(capacity_, t.capacity_);
44 swap(data_, t.data_);
45 swap(size_, t.size_);
46 swap(head_, t.head_);
47 swap(tail_, t.tail_);
48 }
49 Table360& operator = (const Table360& t)
50 {
51 Table360 temp(t);
52 swap_(temp);
53 return *this;
54 }
55 ~Table360()
56 {
57 delete [] data_;
58 capacity_ = 0;
59 size_ = 0;
60 head_ = 0;
61 tail_ = 0;
62 }
63 int size()
64 {
65 return size_;
66 }
67 bool empty()
68 {
69 return size_ == 0;
70 }
71 int top()
72 {
73 return data_[head_];
74 }
75 void enQueue(int item)
76 {
77 if (size_ >= capacity_)
78 {
79 deQueue();
80 }
81 tail_ = (tail_ + 1) % capacity_;
82 data_[tail_] = item;
83 ++size_;
84 //if (size_ >= capacity_)
85 //{
86 // head_ = (head_ + 1) % capacity_;
87 // --size_;
88 // tail_ = (tail_ + 1) % capacity_;
89 // data_[tail_] = item;
90 // ++size_;
91 //}
92 //else
93 //{
94 // tail_ = (tail_ + 1) % capacity_;
95 // data_[tail_] = item;
96 // ++size_;
97 //}
98 }
99 void deQueue()
100 {
101 head_ = ++head_ % capacity_;
102 --size_;
103 }
104 // 其实没有入栈操作，入栈即是入队列
105 void push(int item)
106 {
107 enQueue(item);
108 }
109 int pop()
110 {
111 int tmp = tail_;
112 tail_ = (tail_ + capacity_ - 1) % capacity_;
113 --size_;
114 return data_[tmp];
115 }
116 int stacktop()
117 {
118 return data_[tail_];
119 }
120 };
121
122 int main()
123 {
124 Table360 t(20);
125 cout << t.size() << endl;
126 for (int i = 0; i < 100; ++i)
127 {
128 t.enQueue(i);
129 }
130 cout << t.size() << endl;
131 // cout << t.top() << endl;
132 while (!t.empty())
133 {
134 // cout << t.pop() << ' ';
135 cout << t.stacktop() << ' ';
136 t.pop();
137 }
138 cout << endl;
139 return 0;
140 }
其他链接：
http://zh.wikipedia.org/wiki/%E9%98%9F%E5%88%97
http://zh.wikipedia.org/wiki/%E5%A0%86%E6%A0%88
http://zh.wikipedia.org/wiki/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84
http://student.zjzk.cn/course_ware/data_structure/web/zhanhuoduilie/zhanhuoduilie3.2.1.htm
http://student.zjzk.cn/course_ware/data_structure/web/zhanhuoduilie/zhanhuoduilie3.1.1.htm
http://student.zjzk.cn/course_ware/data_structure/web/main.htm
posted on 2011-05-26 00:48
unixfy 阅读(125)
评论(0) 编辑 收藏 引用