前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >共享栈的实现&两个栈实现一个队列&两个队列实现一个栈

共享栈的实现&两个栈实现一个队列&两个队列实现一个栈

作者头像
lexingsen
发布2022-02-24 19:18:58
4770
发布2022-02-24 19:18:58
举报
文章被收录于专栏:乐行僧的博客乐行僧的博客

1.共享栈的实现 共享栈能够更加有效的节省内存空间,其实现比较简单,就是再同一个数组上存放两个栈,这就需要两个栈顶指针来标记。 判断栈满, 一般当两个栈顶指针相距为1时,就认为共享栈此时已经满了,其实就是牺牲了一个存储空间用来判断满。

代码语言:javascript
复制
#include <iostream>
#include <cassert>
using namespace stdl

#define N 100     //共享栈数组的大小
int s[N];
int top1 = -1;//左栈栈顶指针初始化为-1  是一个无效索引
int top2 = N;//右栈栈顶指针初始化为N,同样也是一个无效的索引
//无论是左边的栈顶指针还是右边在栈顶指针其范围都是在[0...N-1]这个闭区间中,因此他
俩的初始值选择-1和N是合适的

bool isFull() {return top2 - top1 == 1;}
//idx表示向哪个栈入栈    idx==1 表示左栈    idx==2表示右栈       
//在下边top()和pop()实现的中,idx的含义和此处相同


void push(int x, int idx) {
	if(isFull()) {
		cout << "full!" << endl; 
	}
	assert(idx == 1 || idx == 2);
	if(idx == 1) {
		s[++ top1] = x;
	}
	else if(idx == 2) {
		s[-- top2] = x;
	}
} 

void pop(int idx) {
    if(idx == 1) {
        if(top1==-1) {
            cout << "empty! can't pop!" << endl;
        }
        -- top1;
    }else if(idx == 2) {
        if(top2 == N) {
            cout << "empty! can't pop!" << endl;
        }
        ++ top2;
    }
}

int top(int idx) {
    if(idx == 1) {
        if(top1 == -1) {
            cout << "empty!" << endl;
            return -1;
        }
        return s[top1];
    }
    else if(idx == 2) {
        if(top2 == N) {
            cout << "empty!" << endl;
            return -1;
        }
        return s[top2];
    }
}

2.两个栈实现一个队列 一个栈用来存储数据,另外一个栈作为辅助。 front();//存放数据的栈先转换到辅助栈中,刚好就是给数据栈的顺序逆置了,这个时候获取辅助栈的栈顶元素,即为队头元素 pop();//方法同上,只需要将辅助栈进行pop(),即是完成对队列的pop() empty();//只需要判断数据栈是否为空,就能说明队列是否为空,因此只需要调用数据栈的empty()函数即可 这里需要一个重要的辅助函数,其功能就是将a栈的数据转化到b栈,元素的顺序关系刚好是逆置的,如下图所示:

在这里插入图片描述
在这里插入图片描述

具体实现:

代码语言:javascript
复制
#include  <stack>
#include <iostream>
using namespace std;

class Queue{
private:
	stack<int> data, aux;
public:
	void push(int x) {data.push(x);}
	int front() {
		inverse(data, aux);
		int res = aux.top();
		inverse(aux, data);
		return res;
	}
	void pop() {
		inverse(data, aux);
		aux.pop();
		inverse(aux, data);
	}
	bool empty() {return data.empty();}
	//最重要的一个方法
	//将a栈中数据转到b栈中   数据元素的顺序刚好发生了改变
	void inverse(stack<int> &a, stack<int> &b) {
		while(!a.empty()) {
			b.push(a.top());a.pop();
		}
	}
};

int main() {
    int a[] = {1,2,3,4,5};
    int n = sizeof a/sizeof(int);
    Queue q;
    for(int i=0; i<n; ++i) q.push(a[i]);

    while(!q.empty()) {
        cout << q.front() << " ";q.pop();
    }
    cout << endl;
    return 0;
}

执行结果:

在这里插入图片描述
在这里插入图片描述

3.两个队列实现一个栈 由于栈先进后出的特性,用队列来实现栈时,当我们需要对这个封装的栈进行pop()和top()操作时,一定是对最后一个进队列的元素进行操作,一种是出栈即为队列的pop(),另外一种是获取栈顶元素即为队列front(),基于这个特点我们很好写top()和pop()操作。

具体实现:

代码语言:javascript
复制
#include <queue>
#include <iostream>
using namespace std;

class Stack{
private:
    queue<int> data, aux;//aux队列用来保存在data队列中除了最后一个元素外的其他所有元素
public:
    void push(int x) {data.push(x);}

    void pop() {
        while(data.size() > 1) {
            aux.push(data.front()); data.pop();
        }
        data.pop();
        while(!aux.empty()) {
            data.push(aux.front()); aux.pop();
        }
    }
    int top() {
        while(data.size() > 1) {
            aux.push(data.front());data.pop();
        }
        int res = data.front();
        aux.push(data.front()); data.pop();
        while(!aux.empty()) {
            data.push(aux.front()); aux.pop();
        }
        return res;
    }

    bool empty() {return data.empty();}
};


int main() {
    int a[] = {1,2,3,4,5};
    int n = sizeof a/sizeof(int);

    Stack s;
    for(int i=0; i<n; ++i) s.push(a[i]);
    while(!s.empty()) {
         cout << s.top() << " "; s.pop();
    }
    cout << endl;
    return 0;
}

执行结果:

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档