栈是一种先进后出的数据结构，以下是其常见操作：
（1)清空（clear)
栈的清空操作将栈顶指针TOP置为-1，表示栈中没有元素。
void clear() { TOP = -1; }
（2)获取栈内元素个数(size)
由于栈项指针TOP始终指向栈顶元素，而数组下标从0开始、因此栈内元素的数为TOP+1
int size() { return TOP + 1; }
(3）判空(empty）
由栈顶指针TOP的定义可知，仅当TOP== -1时为栈空，返回true；否则，返回false。
bool empty() { if (TOP == -1) return true; else return false; }
(4)进栈(push)
push(x)操作将元素x置于栈顶。由于栈顶指针TOP指向栈顶元素，因此需要先把TOP
加1，然后再把x存入TOP指向的位置。
void push() { st[++TOP] = x; }
(5)出栈(pop)
pop()操作将栈顶元素出栈，而事实上可以直接将栈顶指针TOP减1来实现这个效果。
void pop(){ TOP--; }
(6)取栈顶元素(top）
由于栈顶指针 TOP始终指向栈顶元素，因此可以st[TOP]即为栈顶元素。
int top() { return st[TOP]; }
(7)栈的清空
使用一个while循环反复pop出元素直至栈空。
while (TOP != -1) { st.pop(); }
或者重新定义一个栈以变相的实现栈的清空。
队列是一种先进先出的数据结构，区别于栈。
应当注意到，队列总是从队尾加入元素，而从队首移除元素，并且满足先进先出的规则。
一般来说，需要一个队首指针front来指向队首元素的前一个位置，而使用一个队尾指针rear来指向队尾元素。
和栈类似，当使用数组来实现队列时，队首指针front 和队尾指针rear 为int型变量(数组下标从0开始）；而当使用链表来实现队列时，则为int* 型变量的指针。
这样当使用数组来实现上面的例子时，队首指针front和队尾指针rear的指向情况如图7 - 3所示。
接下来介绍队列的常用操作，包括清空（clear)、获取队列内元素的个数(size)、判空(empty)、入队（push)、出队(pop)、取队首元素（get_front）、取队尾元素（get_rear)等。
下面将使用数组q[]来实现队列，而int型变量front存放队首元素的前一个元素的下标、 rear存放队尾元素的下标（数组下标从0开始）。下面对常见操作进行示范实现：
(1）清空(clear)
使用数组来实现队列时，初始状态为front = -1、rear = -1，图中第一步rear指向0是因为此时队列中已经有一个元素了，如果没有元素，rear应当是指向 - 1位置的。
void clear() { front = rear = -1; }
(2)获取队列内元素的个数（size)
显然rear - front即为队列内元素的个数，这一点可以从图中很容易看出来。
int size() { return rear - front; }
(3)判空(empty）
判定队列为空的条件为front == rear。
bool empty() { if (front = rear) return true; else return false; }
(4)入队(push)
由于队尾指针rear指向队尾元素，因此把元素入队时，需要先把rear加1，然后再存放到rear指向的位置
bool empty() { if (front = rear) return true; else return false; }
(5)出队（pop）
可以直接把队首指针front加1来实现出队的效果
void pop(int x) { front++; }
(6)取队首元素(get_front）
由于队首指针front指向的是队首元素的前一个元素，因此font + 1才是队首元素的位置
int get_front() { return q[front + 1]; }
(7)取队尾元素(get_rear)
由于队尾指针 rear指向的是队尾元素，因此可以直接访问rear的位置。
int get_rear() { return q[rear]; }
(8)队列的清空
与栈类似，出队操作和取队首、队尾元素操作必须在队列非空的情形下才能使用，因此在使用pop()函数、get_front()函数、get_ rear()函数之前必须先使用empty()函数判断队列是否为空。
同样的，可以使用C++STL中的queue容器来非常容易地使用队列。STL中的queue实现好了队列的常用操作，当需要使用时，只需直接调用函数即可，和与栈一样，STL中也没有实现队列的清空，所以如果需要实现队列的清空，可以用一个while循环反复pop出元素直到队列为空，也就是下面这样的写法：
while (!q.empty()){ q.pop(); }
而更常用的方法是重新定义一个队列以实现队列的清空，因为这并不需要花很多时间。
STL的 queue进行定义的时间复杂度和定义slack一样都是O(1)
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
