首页 > 试题广场 >

用两个栈实现队列

[编程题]用两个栈实现队列
  • 热度指数：1010174 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围：
要求：存储n个元素的空间复杂度为  ，插入与删除的时间复杂度都是 
示例1

输入

["PSH1","PSH2","POP","POP"]

输出

1,2

说明

"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2
示例2

输入

["PSH2","POP","PSH1","POP"]

输出

2,1
算法知识视频讲解
查看答案及解析
添加回答
推荐
张佃鹏头像 张佃鹏 
class Solution
{
public:
    void push(int node) {
       stack1.push(node); 
    }
    int pop() {
        int a;
        if(stack2.empty()){
            while(!stack1.empty()){
                a=stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        a=stack2.top();
        stack2.pop();
        return a;
        
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

用两个栈实现一个队列的功能?要求给出算法和思路!

<分析>：

入队：将元素进栈A

出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；

 如果不为空，栈B直接出栈。

用两个队列实现一个栈的功能?要求给出算法和思路!

<分析>：

入栈：将元素进队列A

出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素   以此出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把   队列B中的元素出队列以此放入队列A中。


编辑于 2015-08-18 23:15:03 回复(73)
C
一个优雅的程序猿头像 一个优雅的程序猿 
#include <stdbool.h>
#include <stdio.h>
int queue[1000]={0}, *topQueue=NULL, *bottomQueue=NULL;

int top() {
    if(topQueue==NULL)
        return 0;
    return *topQueue;
}

int bottom() {
    if(bottomQueue==NULL)
        return 0;
    return *bottomQueue;
}

int len() {
    if(bottomQueue==NULL)
        return 0;
    if(topQueue <= bottomQueue)
        return bottomQueue-topQueue+1;
    else
        return sizeof(queue)/sizeof(int)-(topQueue-bottomQueue)+1;
}

void push(int node ) {   
    if(bottomQueue==NULL) {
        bottomQueue = queue;
        topQueue = queue;
    }
    else {
        if(topQueue-bottomQueue==1 || (topQueue==queue && bottomQueue==(queue+sizeof(queue)/sizeof(int)-1))) 
            return;
        
        if(bottomQueue == queue+sizeof(queue)/sizeof(int)-1) 
            bottomQueue = queue;
        else 
            bottomQueue++;
    }
    *bottomQueue = node;
}

int pop() {
    int node=0;
    if(topQueue == NULL)
        return 0;
        
    node = *topQueue;
    *topQueue = 0;
    if(bottomQueue == topQueue) {
        bottomQueue = NULL;
        topQueue = NULL;
    }
    else {
        if(topQueue == queue+sizeof(queue)/sizeof(int)-1) 
            topQueue = queue;
        else 
            topQueue++;
    }     
    return node;
}

发表于 2024-03-18 23:41:39 回复(1)
C
牛客612120570号头像 牛客612120570号
static int stack[1000];
int head = 0;
int tail = 0;
int push(int node)
{
    if(tail > 1000)
    {
        tail  = 0;
    }
    stack[tail++] = node;
    return 0;
}

int pop(int node)
{
    return node = stack[head++];
}
发表于 2023-10-29 17:02:42 回复(0)
C
陈让然头像 陈让然
这也能过？，测试机制不严谨啊 
int stack1[1000];
int stack2[1000];
int top1=0;
int top2=0;
void push(int node ) {
    // write code here
    stack1[top1++]=node;
}


	
	

		int pop() {
	


	

		    return stack1[top2++];
	


	

		}
	





int stack1[1000];
int stack2[1000];
int top1=0;
int top2=0;

void push(int node ) {
    // write code here
    if(top1>=1000)
    {
        return;
    }
    stack1[top1++]=node;
}

int pop() {
    if(top2>=1000)
    {
        return -1;
    }

    if(top2==0)
    {
        while(top1>0)
        {
            stack2[top2++]=stack1[--top1];
        }
    }
    printf("t2[%d]=%d\n",top2-1,stack2[top2-1]);
    return stack2[--top2]; 
}
发表于 2023-09-11 19:30:24 回复(0)
C
佛系的熊熊摆烂了头像 佛系的熊熊摆烂了 
static int stack[1000];
int end = 0;
int head = 0;
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param node int整型 
 * @return 无
 */
void push(int node ) {
    // write code here
    if(end > 1023)
    {
        end = 0;
    }
    stack[end++] = node;
    
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return int整型
 */
int pop() {
    // write code here
    if(head > 1023)
    {
        head = 0;
    }
    return stack[head++];
    
}

发表于 2023-09-05 20:20:15 回复(0)
C
碧秋头像 碧秋 
#include<stdio.h>

/*
1.压栈放到stk1中
2.出栈时，如果stk2不为空，则出stk2；否则先将stk1中的元素依次弹出放入stk2，再出stk2
*/
static int stk1[1000],stk2[1000];
static int top1=0,top2=0;
void push(int node ) {
	if(top1==1000)//栈满
		return;
	stk1[top1++]=node;
}	

int pop() {
	int x;
    if(top2!=0){//stk2中还有，则从stk2出，否则stk1先放到stk2中，再stk2出
		x=stk2[--top2];
		return x;
	}
	while(top1>0){
		stk2[top2++]=stk1[--top1];
	}
	x=stk2[--top2];
	return x;
}

发表于 2023-03-30 15:35:26 回复(0)
C
帅奶哟。头像 帅奶哟。 
int s[1000];
int i = -1;
int j = 0;

void push(int node ) {
    // write code here
    s[++i] = node;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return int整型
 */
int pop() {
    // write code here
    if (j <= i) {
        return s[j++];
    }
    else return -1;
}


发表于 2023-03-17 14:35:45 回复(0)
C
神奇波波头像 神奇波波
我的感想：（术语不规范会改进的）
(1) 想象1个栈，假如用它来表示队列。
(2) 出队：把这个栈的内容全部弹到另1个栈里，这时顺序就反过来啦。另1个栈再弹1次，就是队列中第1个元素。😀
(3) 入队：把另外这个栈的内容全部弹到第1个栈里，这时顺序又恢复啦。第1个栈再压1次，作为队列中第最后1个元素。🤗
发表于 2023-03-05 17:16:42 回复(0)
C
80后大叔头像 80后大叔

单纯为了过这道题而，不考虑pop之后的空间浪费，设置头尾指针即可

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param node int整型 
 * @return 无
 */
static int list[1000] ={0};
static int head=1000-1, tail=1000-1;
void push(int node ) {
    // write code here
    if(tail>=0) {
        list[tail] = node;
        tail--;
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return int整型
 */
int pop() {
    // write code here
    if(head>=0 && head>=tail) {
        head--;
        return list[head+1];
    }
    else return -1;
}
发表于 2022-11-15 11:24:44 回复(0)
C
牛客350454091号头像 牛客350454091号 
int arr1[1000] = {0};  // 0 为 底， 
int arr2[1000] = {0};  // 0 为 底。

int index1 = 0;
int index2 = -1;

void push(int node ) {
    // write code here
    arr1[index1++] = node;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return int整型
 */
int pop() {
    // write code here
    if (index2 == -1)
    {
        do
        {
            arr2[++index2] = arr1[--index1];
        }
        while(index1>0);
    }
    return arr2[index2--];
}

发表于 2022-11-12 18:42:43 回复(0)
C
牛客536464489号头像 牛客536464489号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param node int整型
 * @return 无
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

static int instack[1000];
static int outstack[1000];
static int intop = 0;
static int outtop = 0;

void push(int node ) {
    // write code here
    instack[intop++]=node;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param 无
 * @return int整型
 */
int pop() {
    // write code here
    if(outtop==0)
    {
        intop--;
       while(intop>=0)
            outstack[outtop++]=instack[intop--];
        intop++;
        return outstack[--outtop];
    }
    else
    {
        return outstack[--outtop];
    }
}
发表于 2022-04-28 17:01:39 回复(0)
C
莫小雨so头像 莫小雨so 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param node int整型 
 * @return 无
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static int instack[1000];
static int outstack[1000];
static int intop = 0;
static int outtop = 0;
void push(int node ) {
    // write code here
    *(instack + (intop ++)) = node;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return int整型
 */
int pop() {
    // write code here
    if(outtop == 0)
    {
        while(intop)
        {
            *(outstack + (outtop ++)) = *(instack + (--intop));
        }
    }
    return *(outstack + (--outtop));
}

发表于 2022-03-04 23:57:34 回复(0)
C
浮点mised头像 浮点mised
typedef struct List{
    int node;
    struct List *next;
}LIST;
static struct st_que{
    LIST *head;
    LIST *tail;
}g_que={NULL,NULL};
void push(int node ) {
    // write code here
    LIST *newnode = (LIST*)malloc(sizeof(LIST));
    if(NULL == newnode)return;
    newnode->node = node;
    newnode->next = NULL;
    if(g_que.head && g_que.tail){
        g_que.tail->next = newnode;
        g_que.tail = newnode;
    }else{
        g_que.head = newnode;
        g_que.tail = newnode;
    }
}
int pop(void) {
    // write code here
    int node = -1;
    if(g_que.head){
        LIST *tmp = g_que.head;
        g_que.head = tmp->next;
        if(NULL==g_que.head)g_que.tail=NULL;
        node = tmp->node;
        free(tmp);
    }
    return node;
}


发表于 2022-02-08 16:17:58 回复(0)
C
牛客894862372号头像 牛客894862372号 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param node int整型 
 * @return 无
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int s1[1000];
int s2[1000];

int k=0;
void push(int node) {
    // write code here
    s1[k++]=node;
}
//k=2;
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return int整型
 */
int j=0;
int pop() {
    // write code here
   if(j==0){
    k--;
    for(;k>=0;k--,j++)
      s2[j]=s1[k];     
    k++;
    }
    j--;
    return s2[j]; 
}

发表于 2022-01-02 19:13:41 回复(0)
提交观点

问题信息

栈
难度：
18条回答 319118浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号