网站推广神器,有没有个人做网站的,网站被别人备案,品牌建设的预期成果文章目录 队列和栈的区别一.用队列模拟实现栈1.1入栈1.2出栈1.3返回栈顶元素1.4判断栈是否为空 二.用栈模拟实现队列2.1 入队2.2出队2.3peek2.4判断队列是否为空 三.完整代码3.1 队列模拟实现栈3.2栈模拟实现队列 队列和栈的区别 栈和队列都是常用的数据结构#xff0c;它们的… 文章目录 队列和栈的区别一.用队列模拟实现栈1.1入栈1.2出栈1.3返回栈顶元素1.4判断栈是否为空 二.用栈模拟实现队列2.1 入队2.2出队2.3peek2.4判断队列是否为空 三.完整代码3.1 队列模拟实现栈3.2栈模拟实现队列 队列和栈的区别 栈和队列都是常用的数据结构它们的主要区别在于数据的插入和删除顺序。 栈 (Stack) 是一种后进先出 (Last-In-First-Out, LIFO) 的数据结构只允许在一端进行插入和删除操作这一端称为栈顶。新元素插入后成为新的栈顶而删除时也只能删除栈顶元素。 队列 (Queue) 是一种先进先出 (First-In-First-Out, FIFO) 的数据结构允许在两端进行插入和删除操作插入在队尾删除在队头。新元素插入时成为新的队尾而删除时也只能删除队头元素。 一.用队列模拟实现栈 1.void push(int x) 将元素 x 压入栈顶。 2.int pop() 移除并返回栈顶元素。 3.int top() 返回栈顶元素。 4.boolean empty() 如果栈是空的返回 true 否则返回 false 。 如上便是需要用队列来实现栈的四个基本操作。 我们试想实现这些栈的操作一个队列可以完成吗 显然不可以我们使用两个队列来实现栈的模拟 大体流程 1.入栈时 如果两个都为空那么想 1.1入栈
当我们要放入18 25 35 48 这一串数字入栈时先放入18 25 35放入时选择的队列是不为空的队列模拟入队以及入栈时的状况如下图 public void push(int x) {if(empty()){queue1.offer(x);return;}if(!queue1.isEmpty()){queue1.offer(x);}else {queue2.offer(x);}}1.2出栈
此时如果我们要将35出栈时又该如何操作呢此时我们就需要用到第二个队列将队列一的前size1个元素也就是18 25)从队列一中出队放入队列二中。此时队列一中的元素为35队列二的元素为18 25 如下图。
当初栈完成时我们此时要将48入栈时又该放入哪个栈中呢我们考虑栈的特点先入后出我们将再入栈的元素放到不为空的队列中。 public int pop() {if(empty()){return -1;}if(!queue1.isEmpty()){int size queue1.size();for (int i 0; i size-1; i) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size queue2.size();for (int i 0; i size-1; i) {queue1.offer(queue2.poll());}return queue2.poll();}}
1.3返回栈顶元素
在实现pop的基础上我们将声明一个变量temp来储存每次要移除的元素。 public int top() {if(empty()){return -1;}if (!queue1.isEmpty()){int temp -1;int size queue1.size();for (int i 0; i size; i) {temp queue1.poll();queue2.offer(temp);}return temp;}else {int size queue2.size();int temp -1;for (int i 0; i size; i) {temp queue2.poll();queue1.offer(temp);}return temp;}}1.4判断栈是否为空
当队列一和队列二都为空时此时栈就为空。
public boolean empty() {return queue1.isEmpty()queue2.isEmpty();}二.用栈模拟实现队列 我们也是用两个栈来模拟实现队列 2.1 入队
我们将所有入队的元素都放入栈一中如下图
public void push(int x) {stack1.push(x);}2.2出队
要出栈时如果栈二不为空就出栈二中的元素如果栈二为空将栈一中的所有元素一次性的全部push到栈二中此时就将入栈的元素全部倒转过来了,(例如入栈时在栈中的入栈顺序依次排序为18 25 35栈二中此时的元素入栈顺序是35 25 18出栈时就先出18,就完成了转换如下图 public int pop() {if(empty()){return -1;}if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}2.3peek
peek只是将出队时的pop换成peek就可以完成要求。
public int peek() {if(empty()){return -1;}if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}2.4判断队列是否为空
如果栈一和栈二都为空时那么队列就为空。 public boolean empty() {return stack1.isEmpty() stack2.isEmpty();}三.完整代码
3.1 队列模拟实现栈
class MyStack {QueueInteger queue1 ;QueueInteger queue2 ;public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}public void push(int x) {if(empty()){queue1.offer(x);return;}if(!queue1.isEmpty()){queue1.offer(x);}else {queue2.offer(x);}}public int pop() {if(empty()){return -1;}if(!queue1.isEmpty()){int size queue1.size();for (int i 0; i size-1; i) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size queue2.size();for (int i 0; i size-1; i) {queue1.offer(queue2.poll());}return queue2.poll();}}public int top() {if(empty()){return -1;}if (!queue1.isEmpty()){int temp -1;int size queue1.size();for (int i 0; i size; i) {temp queue1.poll();queue2.offer(temp);}return temp;}else {int size queue2.size();int temp -1;for (int i 0; i size; i) {temp queue2.poll();queue1.offer(temp);}return temp;}}public boolean empty() {return queue1.isEmpty()queue2.isEmpty();}
}3.2栈模拟实现队列
class MyQueue {public StackInteger stack1 ;public StackInteger stack2;public MyQueue() {stack1 new Stack();stack2 new Stack();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()){return -1;}if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()){return -1;}if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() stack2.isEmpty();}
}
