以前にも同様の質問がありましたが、ここでの質問はその逆で、2 つのキューをスタックとして使用しています。質問...
標準操作 ( 、 、、 )を持つ 2 つのキューが与えられた場合、その標準操作 ( enqueue、dequeue、isempty、 )をsize持つスタックを実装します。poppushisemptysize
ソリューションには2 つのバージョンが必要です。
特定の言語の実装よりもアルゴリズムに興味があります。ただし、私がよく知っている言語 ( java、c#、python、vb、javascript、php ) で表現されたソリューションを歓迎します。
バージョン A (効率的なプッシュ):
バージョン B (効率的なポップ):
これを行う最も簡単な (そしておそらく唯一の) 方法は、新しい要素を空のキューにプッシュしてから、他の要素をデキューし、以前の空のキューにエンキューすることです。このようにして、最新のものは常にキューの先頭にあります。これはバージョン B になります。バージョン A の場合、最後のキューを除いて要素を 2 番目のキューにデキューすることでプロセスを逆にします。
ステップ 0:
"Stack"
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
ステップ1：
"Stack"
+---+---+---+---+---+
| 1 | | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 1 | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
ステップ2：
"Stack"
+---+---+---+---+---+
| 2 | 1 | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | 2 | 1 | | | |
+---+---+---+---+---+ +---+---+---+---+---+
ステップ 3:
"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 3 | 2 | 1 | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
1 つのキューでこれを行うことができます。
押す：
n、要素のn-1時間を削除および挿入します。ポップ：
.
push 1
front
+----+----+----+----+----+----+
| 1 | | | | | | insert 1
+----+----+----+----+----+----+
push2
front
+----+----+----+----+----+----+
| 1 | 2 | | | | | insert 2
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | 2 | 1 | | | | remove and insert 1
+----+----+----+----+----+----+
insert 3
front
+----+----+----+----+----+----+
| | 2 | 1 | 3 | | | insert 3
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | | 1 | 3 | 2 | | remove and insert 2
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | | | 3 | 2 | 1 | remove and insert 1
+----+----+----+----+----+----+
実装例:
int stack_pop (queue_data *q)
{
return queue_remove (q);
}
void stack_push (queue_data *q, int val)
{
int old_count = queue_get_element_count (q), i;
queue_insert (q, val);
for (i=0; i<old_count; i++)
{
queue_insert (q, queue_remove (q));
}
}
import java.util.*;
/**
*
* @author Mahmood
*/
public class StackImplUsingQueues {
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
public int pop() {
if (q1.peek() == null) {
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
} else {
int pop = q1.remove();
return pop;
}
}
public void push(int data) {
if (q1.peek() == null) {
q1.add(data);
} else {
for (int i = q1.size(); i > 0; i--) {
q2.add(q1.remove());
}
q1.add(data);
for (int j = q2.size(); j > 0; j--) {
q1.add(q2.remove());
}
}
}
public static void main(String[] args) {
StackImplUsingQueues s1 = new StackImplUsingQueues();
// Stack s1 = new Stack();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);
s1.push(8);
s1.push(9);
s1.push(10);
// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());
System.out.println("8th = " + s1.pop());
System.out.println("9th = " + s1.pop());
System.out.println("10th= " + s1.pop());
}
}
1 つのキューだけを使用してスタックを実装できますか? 2 つのキューを使用できますが、単一のキューを考慮するとより効率的です。コードは次のとおりです。
public void Push(T val)
{
queLower.Enqueue(val);
}
public T Pop()
{
if (queLower.Count == 0 )
{
Console.Write("Stack is empty!");
return default(T);
}
if (queLower.Count > 0)
{
for (int i = 0; i < queLower.Count - 1;i++ )
{
queLower.Enqueue(queLower.Dequeue ());
}
}
return queLower.Dequeue();
}
queue<int> q1, q2;
int i = 0;
void push(int v) {
if( q1.empty() && q2.empty() ) {
q1.push(v);
i = 0;
}
else {
if( i == 0 ) {
while( !q1.empty() ) q2.push(q1.pop());
q1.push(v);
i = 1-i;
}
else {
while( !q2.empty() ) q1.push(q2.pop());
q2.push(v);
i = 1-i;
}
}
}
int pop() {
if( q1.empty() && q2.empty() ) return -1;
if( i == 1 ) {
if( !q1.empty() )
return q1.pop();
else if( !q2.empty() )
return q2.pop();
}
else {
if( !q2.empty() )
return q2.pop();
else if( !q1.empty() )
return q1.pop();
}
}
これは、平均的なケースで O(1) に対して機能する私のソリューションです。と の 2 つのキューがありinますout。以下の疑似コードを参照してください。
PUSH(X) = in.enqueue(X)
POP: X =
if (out.isEmpty and !in.isEmpty)
DUMP(in, out)
return out.dequeue
DUMP(A, B) =
if (!A.isEmpty)
x = A.dequeue()
DUMP(A, B)
B.enqueue(x)
これが私の答えです - 「ポップ」が非効率的です。すぐに頭に浮かぶすべてのアルゴリズムは N の複雑さを持っているようです。ここで、N はリストのサイズです。「ポップ」で作業するか、「プッシュ」で作業するかを選択します。
サイズの計算が不要なため、リストを交換して 4 番目にするアルゴリズムの方が優れている可能性がありますが、ループして空と比較する必要があります。
キューの最後の要素に関する情報は、キューのサイズを知ることによってのみ利用可能であり、その要素に到達するにはデータを破棄する必要があることに注意することで、このアルゴリズムが N よりも高速に記述できないことを証明できます。 .
これを高速化する唯一の方法は、そもそもキューを使用しないことです。
from data_structures import queue
class stack(object):
def __init__(self):
q1= queue
q2= queue #only contains one item at most. a temp var. (bad?)
def push(self, item):
q1.enque(item) #just stick it in the first queue.
#Pop is inefficient
def pop(self):
#'spin' the queues until q1 is ready to pop the right value.
for N 0 to self.size-1
q2.enqueue(q1.dequeue)
q1.enqueue(q2.dequeue)
return q1.dequeue()
@property
def size(self):
return q1.size + q2.size
@property
def isempty(self):
if self.size > 0:
return True
else
return False
すでに述べたように、単一のキューでうまくいくのではないでしょうか。おそらくあまり実用的ではありませんが、少し滑らかです。
push(x):
enqueue(x)
for(queueSize - 1)
enqueue(dequeue())
pop(x):
dequeue()
Q1 = [10, 15, 20, 25, 30]
Q2 = []
exp:
{
dequeue n-1 element from Q1 and enqueue into Q2: Q2 == [10, 15, 20, 25]
now Q1 dequeue gives "30" that inserted last and working as stack
}
swap Q1 and Q2 then GOTO exp
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
Queue<Integer> queue1 = new LinkedList<Integer>();
Queue<Integer> queue2 = new LinkedList<Integer>();
// Push element x onto stack.
public void push(int x) {
if(isEmpty()){
queue1.offer(x);
}else{
if(queue1.size()>0){
queue2.offer(x);
int size = queue1.size();
while(size>0){
queue2.offer(queue1.poll());
size--;
}
}else if(queue2.size()>0){
queue1.offer(x);
int size = queue2.size();
while(size>0){
queue1.offer(queue2.poll());
size--;
}
}
}
}
// Removes the element on top of the stack.
public void pop() {
if(queue1.size()>0){
queue1.poll();
}else if(queue2.size()>0){
queue2.poll();
}
}
// Get the top element. You can make it more perfect just example
public int top() {
if(queue1.size()>0){
return queue1.peek();
}else if(queue2.size()>0){
return queue2.peek();
}
return 0;
}
// Return whether the stack is empty.
public boolean isEmpty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}
S1 と S2 を、キューの実装で使用する 2 つのスタックとします。
struct Stack
{ struct Queue *Q1;
struct Queue *Q2;
}
1 つのキューが常に空であることを確認します。
プッシュ操作 : 空でないキューに要素を挿入します。
Push (struct Stack *S, int data)
{
if(isEmptyQueue(S->Q1)
EnQueue(S->Q2, data);
else EnQueue(S->Q1, data);
}
時間の複雑さ: O(1)
ポップ操作: n-1 個の要素を他のキューに転送し、キューから最後に削除してポップ操作を実行します。
`
int Pop(struct Stack *S){
int i, size;
if(IsEmptyQueue(S->Q2))
{
size=size(S->Q1);
i=0;
while(i<size-1)
{ EnQueue(S->Q2, Dequeue(S->Q1)) ;
i++;
}
return DeQueue(S->Q1);
}
else{
size=size(S->Q2);
while(i<size-1)
EnQueue(S->Q1, Dequeue(S->Q2)) ;
i++;
}
return DeQueue(S->Q2);
} }
時間の複雑さ: pop 操作の実行時間は、pop が呼び出されるたびに O(n) であり、すべての要素を 1 つのキューから別のキューに転送します。
C# の完全な作業コードは次のとおりです。
シングルキューで実装されており、
押す：
1. add new element.
2. Remove elements from Queue (totalsize-1) times and add back to the Queue
ポップ：
normal remove
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace StackImplimentationUsingQueue
{
class Program
{
public class Node
{
public int data;
public Node link;
}
public class Queue
{
public Node rear;
public Node front;
public int size = 0;
public void EnQueue(int data)
{
Node n = new Node();
n.data = data;
n.link = null;
if (rear == null)
front = rear = n;
else
{
rear.link = n;
rear = n;
}
size++;
Display();
}
public Node DeQueue()
{
Node temp = new Node();
if (front == null)
Console.WriteLine("Empty");
else
{
temp = front;
front = front.link;
size--;
}
Display();
return temp;
}
public void Display()
{
if (size == 0)
Console.WriteLine("Empty");
else
{
Console.Clear();
Node n = front;
while (n != null)
{
Console.WriteLine(n.data);
n = n.link;
}
}
}
}
public class Stack
{
public Queue q;
public int size = 0;
public Node top;
public Stack()
{
q = new Queue();
}
public void Push(int data)
{
Node n = new Node();
n.data = data;
q.EnQueue(data);
size++;
int counter = size;
while (counter > 1)
{
q.EnQueue(q.DeQueue().data);
counter--;
}
}
public void Pop()
{
q.DeQueue();
size--;
}
}
static void Main(string[] args)
{
Stack s= new Stack();
for (int i = 1; i <= 3; i++)
s.Push(i);
for (int i = 1; i < 3; i++)
s.Pop();
Console.ReadKey();
}
}
}
キューを 1 つだけ使用する Python コード
class Queue(object):
def __init__(self):
self.items=[]
def enqueue(self,item):
self.items.insert(0,item)
def dequeue(self):
if(not self.isEmpty()):
return self.items.pop()
def isEmpty(self):
return self.items==[]
def size(self):
return len(self.items)
class stack(object):
def __init__(self):
self.q1= Queue()
def push(self, item):
self.q1.enqueue(item)
def pop(self):
c=self.q1.size()
while(c>1):
self.q1.enqueue(self.q1.dequeue())
c-=1
return self.q1.dequeue()
def size(self):
return self.q1.size()
def isempty(self):
if self.size > 0:
return True
else:
return False
もう1つの解決策は次のとおりです。
PUSH の場合: -キュー 1 に最初の要素を追加します。 -2 番目の要素などを追加するときは、最初にキュー 2 の要素をキューに入れ、次にすべての要素をキュー 1 からキュー 2 にコピーします。-POP の場合、最後の要素を挿入したキューから要素をデキューします。
そう、
public void push(int data){
if (queue1.isEmpty()){
queue1.enqueue(data);
} else {
queue2.enqueue(data);
while(!queue1.isEmpty())
Queue2.enqueue(queue1.dequeue());
//EXCHANGE THE NAMES OF QUEUE 1 and QUEUE2
} }
public int pop(){
int popItem=queue2.dequeue();
return popItem;
}'
キューの名前を変更する方法がわかりません。
理解しやすく実装しやすい別のアプローチは次のとおりです。
これが私の解決策です..
Concept_Behind::
push(struct Stack* S,int data)::この関数は、Q1 の最初の要素をエンキューし、Q2 に残ります
pop(struct Stack* S)::Q2 が空でない場合、すべての要素が Q1 に転送され、Q2 の最後の要素が返されます。 Q1 の最後の要素を返します
Efficiency_Behind::
push(struct Stack*S,int data)::O(1)//データごとに単一のエンキューで
あるためpop(struct Stack* S)::O(n)//ポップごとに最悪の n-1 データを転送するため。
#include<stdio.h>
#include<stdlib.h>
struct Queue{
int front;
int rear;
int *arr;
int size;
};
struct Stack {
struct Queue *Q1;
struct Queue *Q2;
};
struct Queue* Qconstructor(int capacity)
{
struct Queue *Q=malloc(sizeof(struct Queue));
Q->front=Q->rear=-1;
Q->size=capacity;
Q->arr=malloc(Q->size*sizeof(int));
return Q;
}
int isEmptyQueue(struct Queue *Q)
{
return (Q->front==-1);
}
int isFullQueue(struct Queue *Q)
{
return ((Q->rear+1) % Q->size ==Q->front);
}
void enqueue(struct Queue *Q,int data)
{
if(isFullQueue(Q))
{
printf("Queue overflow\n");
return;}
Q->rear=Q->rear+1 % Q->size;
Q->arr[Q->rear]=data;
if(Q->front==-1)
Q->front=Q->rear;
}
int dequeue(struct Queue *Q)
{
if(isEmptyQueue(Q)){
printf("Queue underflow\n");
return;
}
int data=Q->arr[Q->front];
if(Q->front==Q->rear)
Q->front=-1;
else
Q->front=Q->front+1 % Q->size;
return data;
}
///////////////////////*************main algo****************////////////////////////
struct Stack* Sconstructor(int capacity)
{
struct Stack *S=malloc(sizeof(struct Stack));
S->Q1=Qconstructor(capacity);
S->Q2=Qconstructor(capacity);
return S;
}
void push(struct Stack *S,int data)
{
if(isEmptyQueue(S->Q1))
enqueue(S->Q1,data);
else
enqueue(S->Q2,data);
}
int pop(struct Stack *S)
{
int i,tmp;
if(!isEmptyQueue(S->Q2)){
for(i=S->Q2->front;i<=S->Q2->rear;i++){
tmp=dequeue(S->Q2);
if(isEmptyQueue(S->Q2))
return tmp;
else
enqueue(S->Q1,tmp);
}
}
else{
for(i=S->Q1->front;i<=S->Q1->rear;i++){
tmp=dequeue(S->Q1);
if(isEmptyQueue(S->Q1))
return tmp;
else
enqueue(S->Q2,tmp);
}
}
}
////////////////*************end of main algo my algo************
///////////////*************push() O(1);;;;pop() O(n);;;;*******/////
main()
{
int size;
printf("Enter the number of elements in the Stack(made of 2 queue's)::\n");
scanf("%d",&size);
struct Stack *S=Sconstructor(size);
push(S,1);
push(S,2);
push(S,3);
push(S,4);
printf("%d\n",pop(S));
push(S,5);
printf("%d\n",pop(S));
printf("%d\n",pop(S));
printf("%d\n",pop(S));
printf("%d\n",pop(S));
}
#include "stdio.h"
#include "stdlib.h"
typedef struct {
int *q;
int size;
int front;
int rear;
} Queue;
typedef struct {
Queue *q1;
Queue *q2;
} Stack;
int queueIsEmpty(Queue *q) {
if (q->front == -1 && q->rear == -1) {
printf("\nQUEUE is EMPTY\n");
return 1;
}
return 0;
}
int queueIsFull(Queue *q) {
if (q->rear == q->size-1) {
return 1;
}
return 0;
}
int queueTop(Queue *q) {
if (queueIsEmpty(q)) {
return -1;
}
return q->q[q->front];
}
int queuePop(Queue *q) {
if (queueIsEmpty(q)) {
return -1;
}
int item = q->q[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
}
else {
q->front++;
}
return item;
}
void queuePush(Queue *q, int val) {
if (queueIsFull(q)) {
printf("\nQUEUE is FULL\n");
return;
}
if (queueIsEmpty(q)) {
q->front++;
q->rear++;
} else {
q->rear++;
}
q->q[q->rear] = val;
}
Queue *queueCreate(int maxSize) {
Queue *q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = -1;
q->size = maxSize;
q->q = (int*)malloc(sizeof(int)*maxSize);
return q;
}
/* Create a stack */
void stackCreate(Stack *stack, int maxSize) {
Stack **s = (Stack**) stack;
*s = (Stack*)malloc(sizeof(Stack));
(*s)->q1 = queueCreate(maxSize);
(*s)->q2 = queueCreate(maxSize);
}
/* Push element x onto stack */
void stackPush(Stack *stack, int element) {
Stack **s = (Stack**) stack;
queuePush((*s)->q2, element);
while (!queueIsEmpty((*s)->q1)) {
int item = queuePop((*s)->q1);
queuePush((*s)->q2, item);
}
Queue *tmp = (*s)->q1;
(*s)->q1 = (*s)->q2;
(*s)->q2 = tmp;
}
/* Removes the element on top of the stack */
void stackPop(Stack *stack) {
Stack **s = (Stack**) stack;
queuePop((*s)->q1);
}
/* Get the top element */
int stackTop(Stack *stack) {
Stack **s = (Stack**) stack;
if (!queueIsEmpty((*s)->q1)) {
return queueTop((*s)->q1);
}
return -1;
}
/* Return whether the stack is empty */
bool stackEmpty(Stack *stack) {
Stack **s = (Stack**) stack;
if (queueIsEmpty((*s)->q1)) {
return true;
}
return false;
}
/* Destroy the stack */
void stackDestroy(Stack *stack) {
Stack **s = (Stack**) stack;
free((*s)->q1);
free((*s)->q2);
free((*s));
}
int main()
{
Stack *s = NULL;
stackCreate((Stack*)&s, 10);
stackPush((Stack*)&s, 44);
//stackPop((Stack*)&s);
printf("\n%d", stackTop((Stack*)&s));
stackDestroy((Stack*)&s);
return 0;
}
import java.util.LinkedList;
import java.util.Queue;
public class StackQueue {
static Queue<Integer> Q1 = new LinkedList<Integer>();
static Queue<Integer> Q2 = new LinkedList<Integer>();
public static void main(String args[]) {
push(24);
push(34);
push(4);
push(10);
push(1);
push(43);
push(21);
System.out.println("Popped element is "+pop());
System.out.println("Popped element is "+pop());
System.out.println("Popped element is "+pop());
}
public static void push(int data) {
Q1.add(data);
}
public static int pop() {
if(Q1.isEmpty()) {
System.out.println("Cannot pop elements , Stack is Empty !!");
return -1;
}
else
{
while(Q1.size() > 1) {
Q2.add(Q1.remove());
}
int element = Q1.remove();
Queue<Integer> temp = new LinkedList<Integer>();
temp = Q1;
Q1 = Q2;
Q2 = temp;
return element;
}
}
}