栈、队

本文为个人学习笔记。

昨天学习了表，写了个简单的单链表。今天看了下栈和队。

　　说白了：栈就是一个只能在头部插入和删除的表，遵循后进先出的原则；而队与栈的区别就是先进先出，从头部插入，底部删除。

附代码

 1 #include <iostream>
 2 using namespace std;
 3 
 4 typedef struct StackNode
 5 {
 6     int data;
 7     StackNode* next;
 8 }Node;
 9 
10 class Stack
11 {    
12 public:
13     Stack(){bottom = top = NULL; }
14     ~Stack(){};
15 
16     void Init();
17     void push();
18     void del();
19 
20     bool IsEmpty();
21     void Print();
22     void EmptyStack();
23 
24 private:
25     Node* bottom;
26     Node* top;
27 };

  1 #include "stack.h"
  2 
  3 int main()
  4 {
  5     Stack stack;
  6 
  7     cout<<"初始化，以0结束
";
  8     stack.Init();
  9     int i = 1;
 10     while (i)
 11     {
 12         cout<<"1:进栈；2:出栈；3:输出；4:清空栈；0:退出"<<endl;
 13         cin>>i;
 14         switch (i)
 15         {
 16         case 1:stack.push();break;
 17         case 2:stack.del();break;
 18         case 3:stack.Print();break;
 19         case 4:stack.EmptyStack();break;
 20         case 0:return 0;
 21         default:break;
 22         }
 23     }
 24 
 25 }
 26 
 27 //*********************
 28 //初始化链表
 29 //*********************
 30 void Stack::Init()
 31 {
 32     top = bottom;//此处要new一个新的空间
 33     cout<<"输入初始化元素,并以0结束 "<<endl;
 34     int init_data = 0;
 35     
 36     while(cin>>init_data)
 37     {
 38         if (init_data == 0)
 39         {
 40             break;
 41         }
 42         else if( !IsEmpty() )
 43         {
 44             Node* temp = new Node;//要不要每次都new一次呢?
 45             temp->data = init_data;
 46             temp->next = NULL;
 47             top->next = temp;
 48             top = temp;
 49             temp = NULL;
 50             delete temp;
 51         }
 52         else
 53         {
 54             Node* temp = new Node;
 55             temp->data = init_data;
 56             temp->next = NULL;
 57             top = bottom = temp;
 58             temp = NULL;
 59             delete temp;
 60         }
 61     }
 62         
 63 }
 64 
 65 //*********************
 66 //*********************
 67 bool Stack::IsEmpty()
 68 {
 69     return bottom == NULL;
 70 }
 71 //*********************
 72 //进栈
 73 //*********************
 74 void Stack::push()
 75 {
 76     int push_data;
 77     cout<<"请输入：";
 78     cin>>push_data;
 79     Node* temp = new Node;
 80     
 81     temp->data = push_data;
 82     temp->next = NULL;
 83     if (IsEmpty())
 84     {
 85         top = bottom = temp;
 86     }
 87     else
 88     {
 89         top->next = temp;
 90         top = top->next;
 91     }
 92     
 93     temp = NULL;
 94     delete temp;
 95 }
 96 
 97 //*********************
 98 //出栈
 99 //*********************
100 void Stack::del()
101 {
102     if(IsEmpty())
103     {
104         cout<<"栈为空栈，不能删除"<<endl;
105         return;
106     }
107     else if (top == bottom)
108     {
109         Node* temp = bottom;
110         top = bottom = NULL;
111         delete temp;
112     }
113     else
114     {
115         Node* temp = bottom;
116         while (temp->next != top)
117         {
118             temp = temp->next;
119         }
120         Node* end = top;
121         top = temp;
122         top->next = NULL;
123         temp = NULL;
124         delete temp;
125         delete end;
126     }
127 }
128 //*********************
129 //输出链表
130 //*********************
131 void Stack::Print()
132 {
133     Node* m_temp = bottom;
134     while(m_temp != NULL)
135     {
136         cout<<m_temp->data<<"	";
137         m_temp = m_temp->next;
138     }
139     cout<<endl;
140     m_temp = NULL;
141 }
142 //*********************
143 //清空链表
144 //*********************
145 void Stack::EmptyStack()
146 {
147     Node* m_temp = bottom;
148     while(m_temp)
149     {
150         bottom = m_temp->next;
151         delete m_temp;
152         m_temp = bottom;
153     }
154     bottom = top = NULL;
155     cout<<endl;
156 }

队与栈的区别仅在于出栈方式不同

 1 //*********************
 2 //出栈
 3 //*********************
 4 void Stack::del()
 5 {
 6     if(IsEmpty())
 7     {
 8         cout<<"栈为空栈，不能删除"<<endl;
 9         return;
10     }
11     else if (top == bottom)
12     {
13         Node* temp = bottom;
14         top = bottom = NULL;
15         delete temp;
16     }
17     else
18     {
19         Node* temp = bottom;
20         bottom = bottom->next;
21 
22         delete temp;
23     }
24 }