精华内容
下载资源
问答
  • 栈实现队列
    千次阅读
    2022-01-24 16:51:49

    仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

    实现 MyQueue 类:

    • void push(int x) 将元素 x 推到队列的末尾
    • int pop() 从队列的开头移除并返回元素
    • int peek() 返回队列开头的元素
    • boolean empty() 如果队列为空,返回 true ;否则,返回 false

    使用栈实现队列需要两个栈,一个输入栈,一个输出栈。

    1.在输入元素时只需要把元素放入输入栈。

    2.在输出时需要判断输出栈是否为空,如果为空,就要把输入栈中的元素全部导入,再从输出栈弹出数据;如果不为空,可以直接弹出元素。

    3.若进栈和出栈均为空,说明模拟的队列空了。

    实现代码如下:

    stack<int> stIn; //入栈 
    stack<int> stOut; //出栈 
    MyQueue() {}
    
    //将元素x入队  
    void push(int x) {
        stIn.push(x); 
    }
    
    //从队列首部移除元素 
    int pop() {
        if(stOut.empty()) {
            while(! stIn.empty()) {
                int i = stIn.top();
                stOut.push(i);
                stIn.pop();
            }
        }   
        int r = stOut.top();
        stOut.pop();
        return r;
    }
    
    //返回队首元素 
    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    //判断队列是否为空 
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
    更多相关内容
  • 两个栈实现队列:栈实现先进先出 栈1负责队尾,栈2负责队头 每次入队,栈2无元素且栈1无元素,入栈2;否则入栈1 每次出队,栈2有元素,出栈2顶;否则把全部栈1入栈2,再出栈2顶 bool Pop(ref int value) { if (m...

    两个栈实现队列:栈实现先进先出

    1. 栈1负责队尾,栈2负责队头
    2. 每次入队,栈2无元素且栈1无元素,入栈2;否则入栈1
    3. 每次出队,栈2有元素,出栈2顶;否则把全部栈1入栈2,再出栈2顶
    bool Pop(ref int value)
        {
            if (m_stack2.Count > 0)
            {
                value =  m_stack2.Pop();
                return true;
            }
    
            while (m_stack1.Count > 0)
            {
                m_stack2.Push(m_stack1.Pop());
            }
    
            if (m_stack2.Count > 0)
            {
                value = m_stack2.Pop();
                return true;
            }
    
            return false;
        }
    
        void Push(int value)
        {
            if (m_stack2.Count == 0 && m_stack1.Count == 0)
            {
                m_stack2.Push(value);
            }
            else
            {
                m_stack1.Push(value);
            }
        }
    

    两个队列实现栈:队列实现先进后出

    1. 队1负责插入,队2负责出栈时暂时保存空间。两者存在一个作为出队缓冲,然后1保留1个最为栈顶出去,即身份可以互调
    2. 两个队列只存在3种情况:都是空,插入队1;队1空,队2有值,即队2作为操作队列;反之队1有,队2空
    3. 出栈:有值的队列依次出队到另一个队列,留一个出栈
    4. 入栈:谁不空入谁;都空入队1
    bool Pop(ref int value)
       {
           if (m_queue1.Count == 1 && m_queue2.Count == 0)
           {
               value = m_queue1.Dequeue();
               return true;
           }
           else if (m_queue1.Count == 0 && m_queue2.Count == 1)
           {
               value = m_queue2.Dequeue();
               return true;
           }
           else if (m_queue1.Count > 1 && m_queue2.Count == 0)
           {
               while (m_queue1.Count > 1)
               {
                   m_queue2.Enqueue(m_queue1.Dequeue());
               }
    
               value = m_queue1.Dequeue();
               return true;
           }
           else if (m_queue1.Count == 0 && m_queue2.Count  > 1)
           {
               while (m_queue2.Count > 1)
               {
                   m_queue1.Enqueue(m_queue2.Dequeue());
               }
    
               value = m_queue2.Dequeue();
               return true;
           }
    
           return false;
       }
    
       void Push(int value)
       {
           if (m_queue1.Count >= 0  && m_queue2.Count == 0)
           {
               m_queue1.Enqueue(value);
           }
           else if (m_queue1.Count == 0 && m_queue2.Count > 0)
           {
               m_queue2.Enqueue(value);
           }
       }
    

    源码

    https://github.com/luoyikun/UnityForTest
    Stack2Queue场景

    展开全文
  • 用两个实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 2. 解题思路 2.1 分析 :先进后出 队列:先进先出 要求用两个{stack1,stack2}实现一个队列,也就是说我们需要使用的push和pop...
  • python用栈实现队列

    2018-05-30 23:23:45
    python用栈实现队列,简单明了易于进一步思考和总结发散思维。
  • C语言-用栈实现队列

    千次阅读 2021-11-13 16:48:42
    栈实现队列 栈是先进后出的数据结构,队列是先进先出的数据结构,所以当往队列中插入数据时,可以直接入栈。只是队列中先插入的在队首,队列中先插入的在栈底。 弹出队首的数据,实际就是删掉栈底的数据,直接...

    用栈实现队列

    1. 栈是先进后出的数据结构,队列是先进先出的数据结构,所以当往队列中插入数据时,可以直接入栈。只是队列中先插入的在队首,队列中先插入的在栈底。
    2. 弹出队首的数据,实际就是删掉栈底的数据,直接删除不了,可以利用另一个辅助栈,将当前栈中数据全部依次弹出,并push到辅助栈中,这时当前栈的栈底元素就变成了辅助栈的栈顶元素,直接pop掉辅助栈的栈顶元素就行。
    3. 队列从队首到队尾的元素始终是辅助栈栈顶到栈底+当前栈栈底到栈顶。辅助栈栈顶对应着队列队首,当前栈栈底对应队列队尾。这就说明当辅助栈不为空时,队列的pop,可以直接对辅助栈pop。当辅助栈为空时,就要将当前栈搬运到辅助栈再弹出。而入栈可以直接push当当前栈。
      4请添加图片描述
    
    typedef struct{
    	int* data;
    	int top;
    }MyStack;
    
    typedef struct{
    	MyStack* stackPush;
    	MyStack* stackPop;
    }MyQueue;
    
    #define maxQueueNum  100		//队列空间
    MyQueue* myQueueCreate(){
    	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    	
    	queue->stackPush = (MyStack*)malloc(sizeof(MyStack));
    	queue->stackPop = (MyStack*)malloc(sizeof(MyStack));
    	
    	queue->stackPush->data = (int*)malloc(sizeof(int) * maxQueueNum);
    	queue->stackPush->top = -1;
    	
    	queue->stackPop->data = (int*)malloc(sizeof(int) * maxQueueNum);
    	queue->stackPop->top = -1;
    	
    	return queue;
    }
    
    //入队
    void myQueuePush(MyQueue* obj){
    	if((obj->stackPush->top + obj->stackPop->top) == maxStackNum - 2)	//队列空间满
    		return ;
    	obj->stackPush->data[++obj->stackPush->top] = x;
    }
    
    //出队
    int myQueuePop(MyQueue* obj){
    	if(obj->stackPop->top != -1){		//辅助栈不为空,直接弹出
    		return obj->stackPop->data[obj->stackPop->top--];
    	}
    	while(obj->stackPush->top != -1){	//辅助栈为空,将当前栈依次弹出并压到辅助栈中
    		obj->stackPop->data[++obj->stackPop->top] = obj->stackPush->data[obj->stackPush->top--];
    	}
    	if(obj->stackPop->top == -1){		//辅助栈仍为空,说明对应队列为空,无值返回
    		return -1;
    	}
    	else
    	{
    		return obj->stackPop->data[obj->stckPop->top--];
    	}
    }
    
    //取队首值
    int myQueuePeek(MyQueue* obj){
    	if((obj->stackPush->top == -1) && (obj->stackPop->top == -1))//队列为空
    		return -1;
    
    	if(obj->stackPop->top != -1){
    		return obj->stackPop->data[obj->stackPop->top];
    	}
    	else
    	{
    		while(obj->stackPush->top != -1){
    			obj->stackPop->data[++obj->stackPop->top] = obj->stackPush->data[obj->stackPush->top--];
    		}
    		return obj->stackPop->data[obj->stackPop->top];
    	}
    }
    
    //判断队列是否为空
    bool myQueueEmpty(MyQueue* obj){
    	if((obj->stackPush->top == -1) && (obj->stackPop->top == -1))
    		return true;
    	else
    		return false;
    }
    
    void myQueueFree(MyQueue* obj) {
        free(obj->stackPush->data);
        free(obj->stackPop->data);
        free(obj->stackPush);
        free(obj->stackPop);
        free(obj);
    }
    
    
    展开全文
  • 如何用栈实现队列

    多人点赞 2022-05-12 23:37:53
    如果用实现队列则需要用俩个来模拟队列进而实现队列的先进先出(FIFO)原则。步骤如下: (1)创建俩个一个进行入栈操作Stack<E> in,一个进行出栈操作Stack<E> out (2)队列的特点为先进先出...

    队列遵循先进先出(FIFO)原则,栈遵循后进先出(LIFO)原则。如果用栈来实现队列则需要用俩个栈来模拟队列进而实现队列的先进先出(FIFO)原则。步骤如下:

    (1)创建俩个栈一个进行入栈操作Stack<E> in,一个进行出栈操作Stack<E> out

    (2)队列的特点为先进先出所以要求栈in进,栈out出

    (3)入队时要保证栈out为空,所以先判断栈out是否为空,若不为空则将栈out中的元素全部存入栈in中 in.push(out.pop())

    (4)出队时要保证栈in为空,所以先判断栈in是否为空,若不为空则将栈in中的元素全部存入栈out中 out.push(in.pop())

    代码实现:

    import java.util.Stack;
    public class Test01 {
    	public static void main(String[] args) {
    		MyQueue<String> queue=new MyQueue();
    		queue.offer("A1");
    		queue.offer("A2");
    		queue.offer("A3");
    		queue.offer("A4");
    		System.out.println(queue.poll()+"出队");
        }
    }
    //栈模拟队列
    class MyQueue<E>{
    	private Stack<E> in =new Stack<E>();
    	private Stack<E> out =new Stack<E>();
    	//入队
    	public void offer(E e) {
    		while(!out.isEmpty()) {
    			in.push(out.pop());
    		}
    		in.push(e);
    	}
       
        public boolean isEmpty() {
    		return in.size()==0&&out.size()==0;
    	}
    	//出队
    	public E poll() {
    		while(!in.isEmpty()) {
    			out.push(in.pop());
    		}
    		return out.pop();		
    	}
    }
    

    展开全文
  • JAVA——用栈实现队列

    2022-02-11 18:44:28
    问题:请你仅使用两个栈实现先入先出队列队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 ...
  • 本文实例讲述了PHP使用两个栈实现队列功能的方法。分享给大家供大家参考,具体如下: 问题 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解决思路 两个栈。出栈的时候,如果栈2不为...
  • 用两个栈实现一个队列。 请实现它的两个函数: appendTail:在队列尾部插入整数 deleteHead :在队列头部删除整数。(若队列中没有元素,deleteHead ...按以上方法即实现了两个栈实现队列。 class CQueue{ stack
  • 此问题的实现可以加深对队列的理解,让我们先来认识一下队列 1.Stack (Stack)是一种后进先出(LIFO)的数据结构 Stack只有入栈和出栈的操作,常用方法有: (1)把元素压栈:push() (2)把栈顶...
  • 主要介绍了如何使用两个栈实现队列Java,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 用两个栈实现队列

    2021-07-27 11:45:25
    用两个栈实现一个队列队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 示例 1: 输入: ...
  • 栈实现队列

    2017-01-09 17:16:03
    栈实现队列
  • 栈实现队列(Java实现)

    万次阅读 2020-07-08 08:27:10
    栈实现队列(力扣:232)
  • C语言用栈实现队列(数据结构)

    千次阅读 2021-12-01 17:57:33
    1.首先需要两个来模拟队列的出队和入队 2.假设入队1 2 3 4 ,如果要出队则不能直接出栈.需要进行数据的搬移: 先把s1的数据全部放入s2中,然后再在s2出栈->整个队列出队: 3.如果再要入队则将入队元素放入s1...
  • 请你仅使用两个栈实现先入先出队列队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int ...
  • 力扣:用两个栈实现队列(golang实现)

    千次阅读 2022-02-13 17:50:18
    力扣:使用两个栈实现队列
  • 栈实现队列和用队列实现栈

    千次阅读 2019-02-23 15:10:44
    第一 队列的了解 -- 先进后出(FILO—First-In/Last-Out) 队列 -- 先进先出(FIFO—first in first out) 对应的方法 入栈:s.push(x) 出栈:s.pop() 访问栈顶:s.top() 判断空:s.empty() 访问...
  • 之前的几章我讲解了和队列的基本特性和一些基本的操作方法,那么如何能利用实现队列呢? 下面我来讲解下具体思路,的特性先进后出,队列是先进先出,如果要模拟队列的这个特性,我们就必须用到两个。 一个...
  • 用两个栈实现队列(C语言版)

    千次阅读 2021-10-10 22:03:46
    用两个栈实现一个队列队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) ...
  • 栈实现队列1

    2022-08-03 14:51:38
    // 栈顶// 容量//检查容量void checkCapcity(Stack* ps)ps->_data = (STDataType*)realloc(ps-
  • 力扣刷题——两个栈实现队列,用JavaScript实现
  • 题目要求 要求使用两个来实现一个... * 使用两个实现队列 */ class MyQueue<T> { private Stack<T> stack1; private Stack<T> stack2; public MyQueue() { stack1 = new Stack<&g
  • 推前使用栈实现队列 使用堆栈实现队列的以下操作。 push(x) -- 将元素 x 推到队列的后面。 pop()——从队列前面移除元素。 peek() -- 获取最前面的元素。 empty() -- 返回队列是否为空。 Example: MyQueue queue = ...
  • 用两个栈实现一个队列队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 思路 根据栈的特性...
  • 请你仅使用两个栈实现先入先出队列队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int ...
  • 用两个栈实现一个队列 方法有add、delete、length 队列 特点:先进先出 API:add delete length 英文 queue 队列其实用链表实现最好,但是这个题目的目的是考察对于栈和队列的理解 先将一个栈中所有元素压到另一个...
  • 用两个栈实现队列 题目 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解题思路 栈stack1用来实现push操作,stack2空的前提下才能进行入栈,否则影响后续进出队列的顺序。 栈stack2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 268,538
精华内容 107,415
关键字:

栈实现队列