隊(duì)列的兩個(gè)主要操作：入隊(duì)列、出隊(duì)列
棧的兩個(gè)主要操作：入棧、出棧
入隊(duì)列對應(yīng)入棧
出隊(duì)列是出最早的，出棧是出最晚的
使用 360 瀏覽器，有個(gè)不錯(cuò)的功能是可以恢復(fù)標(biāo)簽，你關(guān)閉一個(gè)標(biāo)簽，這個(gè)標(biāo)簽就會(huì)進(jìn)入待恢復(fù)表，如果待恢復(fù)表慢了，新加標(biāo)簽，最早的標(biāo)簽會(huì)消失，這是 FIFO 隊(duì)列。
但是如果點(diǎn)擊恢復(fù)標(biāo)簽隊(duì)列，會(huì)恢復(fù)最近關(guān)閉的標(biāo)簽，也就是最晚進(jìn)入待恢復(fù)表中的標(biāo)簽，所以這又是一種 LIFO 棧。
待恢復(fù)表既具有添加標(biāo)簽的 FIFO 隊(duì)列性質(zhì)，又具有恢復(fù)標(biāo)簽并移除標(biāo)簽的 LIFO 棧性質(zhì)。
實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)，使其既具有 FIFO 隊(duì)列的性質(zhì)，又具有 LIFO 棧的性質(zhì)。
由于標(biāo)簽有很多，這里使用循環(huán)表來實(shí)現(xiàn)這個(gè)數(shù)據(jù)結(jié)構(gòu)，早期的標(biāo)簽會(huì)隨著新加入的標(biāo)簽被覆蓋。
注意連續(xù)關(guān)閉兩個(gè)相同的標(biāo)簽，第二次關(guān)閉時(shí)，不會(huì)將這個(gè)標(biāo)簽存入待恢復(fù)表中。
這個(gè)表主要有三個(gè)操作
·入隊(duì)列
·出隊(duì)列
·出棧
沒有入棧，其實(shí)入棧也就是入隊(duì)列。
實(shí)現(xiàn)：
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 // 其實(shí)沒有入棧操作，入棧即是入隊(duì)列
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) 編輯 收藏 引用