《数据结构与算法分析：C语言描述》复习——第三章“线性表、栈和队列”—

《数据结构与算法分析：C语言描述》复习——第三章“线性表、栈和队列”——栈

2014.06.14 22:26

简介：

　　栈，是先进先出的结构。我们只关心栈的大小和栈顶的元素。

图示：

实现：

 1 // My implementation of stack.
 2 class Stack {
 3 public:
 4     Stack() {
 5         m_capacity = 1;
 6         m_size = 0;
 7         m_data = new int[m_capacity];
 8     }
 9     
10     void push(int val) {
11         if (m_size + 1 >= m_capacity) {
12             resize(2 * m_capacity);
13         }
14         m_data[m_size++] = val;
15     }
16     
17     void pop() {
18         if (m_size > 0) {
19             --m_size;
20         }
21     }
22     
23     int top() {
24         return m_data[m_size - 1];
25     }
26     
27     int size() {
28         return m_size;
29     }
30     
31     bool empty() {
32         return m_size == 0;
33     }
34     
35     ~Stack() {
36         delete m_data;
37     }
38 private:
39     int *m_data;
40     int m_capacity;
41     int m_size;
42     
43     void resize(int new_capacity) {
44         if (new_capacity <= m_capacity) {
45             return;
46         }
47         int *new_data = new int[new_capacity];
48         
49         for (int i = 0; i < m_size; ++i) {
50             new_data[i] = m_data[i];
51         }
52         delete[] m_data;
53         m_data = new_data;
54         m_capacity = new_capacity;
55     }
56 };
57 
58 int main()
59 {
60     return 0;
61 }