隊列的兩個主要操作：入隊列、出隊列
棧的兩個主要操作：入棧、出棧
入隊列對應入棧
出隊列是出最早的，出棧是出最晚的
使用 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 閱讀(139)
評論(0) 編輯 收藏 引用