河口建设局网站,像优酷这样的网站需要怎么做,有关做橡胶品的网站,高端文化网站模板文章目录一、用栈实现队列入队#xff1a;出队#xff1a;Java代码实现#xff1a;二、用队列实现栈入栈#xff1a;出栈#xff1a;Java代码实现#xff1a;附#xff1a;C版代码1、用栈实现队列2、用队列实现栈栈#xff08;stack#xff09;#xff1a;先进后出出队Java代码实现二、用队列实现栈入栈出栈Java代码实现附C版代码1、用栈实现队列2、用队列实现栈栈stack先进后出后进先出。限定在表尾进行插入删除的线性表。 队列queue先进先出后进后出。限定在表头删除在表尾插入的线性表。 那么如何用栈来实现队列和如何用队列来实现栈的数据结构呢
一、用栈实现队列
单个栈肯定无法实现队列所以至少应该用两个栈来实现队列。
入队
数据栈每次有新元素来时先把存放的元素弹入辅助栈再把新元素压入数据栈底辅助栈等待新元素进入数据栈以后依次弹出元素压入数据栈中
根据这两个栈的功能不管是数据栈中是否有元素存在新元素都会被沉到栈底中实现入队的功能。
出队
由于在入队时通过数据栈与辅助栈的交换实现了后加入的元素沉在栈底先进入的元素保留在栈顶直接通过出栈弹出即可
Java代码实现
public class StackImplQueue {// 数据栈private StackInteger stack;// 辅助栈private StackInteger aux;StackImplQueue() {stack new Stack();aux new Stack();}// 入队--通过数据栈与辅助栈相互交换保证新加入的元素沉在数据栈底public void enqueue(Integer e) {while (!stack.isEmpty()) {aux.push(stack.pop());}stack.push(e);while(!aux.isEmpty()){stack.push(aux.pop());}}// 出队--弹出数据栈元素public Integer dequeue(){return stack.pop();}// 查看队头元素public Integer peek(){return stack.peek();}// 是否为空public boolean isEmpty(){return stack.isEmpty();}public static void main(String[] args) {StackImplQueue queue new StackImplQueue();queue.enqueue(1);System.out.println(queue.peek());queue.enqueue(2);System.out.println(queue.peek());queue.enqueue(3);System.out.println(queue.peek());System.out.println();System.out.println(queue.dequeue());System.out.println(queue.dequeue());System.out.println(queue.dequeue());}
}二、用队列实现栈
入栈
入栈的元素要在队头而队列入队的元素在队尾只需让队头至队尾前的其它所有元素依次出队再入队直至在队尾新加入的元素被移到队头也即实现了让新压入的元素保留在栈顶。
出栈
由于在入栈时保证队列中新加入队尾的元素被移到了队头出栈只需弹出队头元素即可
Java代码实现
public class QueueImplStack {// 定义队列private QueueInteger queue;public QueueImplStack() {queue new LinkedList();}// 入栈--在队尾加入元素后,让其他元素按顺序出队再入队保持新加入的元素永远在队头public void push(Integer e) {queue.offer(e);int size queue.size();int i 0;while (i size - 1) {queue.offer(queue.poll());i;}}// 出栈--将队尾前的其它所有元素出队再入队直至队尾元素移到队头public Integer pop() {return queue.poll();}// 查看栈顶元素--即队头元素public Integer peek() {return queue.peek();}// 是否为空public boolean isEmpty() {return queue.isEmpty();}public static void main(String[] args) {QueueImplStack stack new QueueImplStack();stack.push(1);System.out.println(stack.peek());stack.push(2);System.out.println(stack.peek());stack.push(3);System.out.println(stack.peek());System.out.println();System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.isEmpty());}
}附C版代码
1、用栈实现队列
#includestack
#includeiostreamusing namespace std;class queue{
public:stackint dataStack;//数据栈 stackint auxStack;//辅助栈//入队通过辅助栈让新元素沉于栈底
void push(int x) {while(!dataStack.empty()){auxStack.push(dataStack.top());dataStack.pop();}dataStack.push(x);while(!auxStack.empty()){dataStack.push(auxStack.top());auxStack.pop();}
}// 出队--弹出数据栈元素int outqueue(){int temp dataStack.top();dataStack.pop();return temp;}// 查看队头元素int top(){return dataStack.top();}// 是否为空bool empty(){return dataStack.empty();}};int main(){queue iq;iq.push(1);coutiq.top()endl;iq.push(2);coutiq.top()endl;iq.push(3);coutiq.top()endl;cout-------------endl;coutiq.outqueue()endl;coutiq.outqueue()endl;coutiq.outqueue()endl; return 0;
}2、用队列实现栈 #includedeque
#includeiostreamusing namespace std;class stack{
public:dequeint de;// 入栈--在队尾加入元素后,让其他元素按顺序出队再入队保持新加入的元素永远在队头void push(int x) {de.push_front(x);int size de.size();int i 0;while (i size - 1) {de.push_front(de.back());de.pop_back();i;}}// 出栈--将队尾前的其它所有元素出队再入队直至队尾元素移到队头int pop() {int temp de.front();de.pop_front();return temp;}// 查看栈顶元素--即队头元素int top() {return de.front();}// 是否为空bool isEmpty() {return de.empty();}
};int main(){stack iq;iq.push(1);coutiq.top()endl;iq.push(2);coutiq.top()endl;iq.push(3);coutiq.top()endl;cout-------------endl;coutiq.pop()endl;coutiq.pop()endl;coutiq.pop()endl; return 0;
}本文参考来源
用队列实现栈用栈实现队列听起来有点绕都搞懂了就掌握了精髓 - 云社区 - 腾讯云 (tencent.com)《小灰的算法之旅》
