栈与队列的应用

2024-03-22 21:45:16

栈是一种先进后出的数据结构，以下是其常见操作：

（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指向的位置。

void push(int x) {
	q[++rear] = x;
}

(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()

码农公寓